[자료구조] 인접리스트 구현 : LinkedList (Java)

인접리스트는 노드의 인접된 노드를 아래와 같이 연결시키는것이다.

 

따라서 인접리스트로 그래프를 구현하게 되면 아래와 같은 장점이 발생한다.

 

장점

 

실제 연결된 노드 들끼리만 저장하기 때문에 모든 정점들의 원소의 합이 간선의 개수와 같다.

따라서 간선의 개수에 비례하는 메모리만 차지한다 O(E)

(E는 간선을 뜻함)

 

단점

 

특정 노드와 연결된 노드가 몇번인지 확인하기 위해 모든 노드들을 확인해야 한다.

따라서 O(V)만큼의 시간 복잡도를 지닌다.

 

 

 

인접리스트로 그래프 구현하는것의 특징에 대해서 알아봤으니 이제 실제로 소스를 어떻게 구현했는지를 알아보자.

일단 아는 LinkedList를 활용하여서 인접리스트를 구현하였다.

 

LinkedList에 대해 잘 모르시는 분들은 아래링크 참조하시면 될것 같다.

https://wpioneer.tistory.com/125

[Java] LinkedList 란?

 

일단 소스부터 보자.

 

AdjacencyList Class

public class AdjacencyList {

	private LinkedList<Integer>[] adj; // 인접리스트 생성
	private int v; // 정점개수
	
	
	public AdjacencyList(int v) {
		super();
		this.v = v; //이걸로 정점 개수 초기화
		adj = new LinkedList[v+1]; //그래프가 1부터시작한다고 했을때 0의 자리는 비워둠
		
		for(int i = 0; i< v+1; i++) {
			adj[i] = new LinkedList();
		}
	}
	
	//정점끼리 연결시키기
	public void addEdge(int v1, int v2) {
		adj[v1].add(v2);
		adj[v2].add(v1);
	}
	
	public void printG() {
		for(int i = 1; i<adj.length;i++) {
			System.out.println("node "+i+" 와 인접 노드 : "+ adj[i]);
		}
	}
}

Main 함수

public class PreTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		PreTest p = new PreTest();
		
		int n = 5;
		
		AdjacencyList aj = new AdjacencyList(n);
		
		aj.addEdge(1, 2);
		aj.addEdge(1, 3);
		aj.addEdge(3, 4);
		aj.addEdge(3, 5);
		
		aj.printG();
	}

}

 

나는 위 소스에서 중요하다고 생각되는 점이 

AdjacencyList Class 에서 

	private LinkedList<Integer>[] adj; // 인접리스트 생성
	private int v; // 정점개수
	
	
	public AdjacencyList(int v) {
		super();
		this.v = v; //이걸로 정점 개수 초기화
		adj = new LinkedList[v+1]; //그래프가 1부터시작한다고 했을때 0의 자리는 비워둠
		
		for(int i = 0; i< v+1; i++) {
			adj[i] = new LinkedList();
		}
	}

이 부분인것 같다. 

 

인접리스트에선 각 정점(노드)마다 인접될 노드를 연결시킬 LinkedList가 필요하다.

따라서 정점개수만큼의 LinkedList를 담을 LinkedList를 생성시키는 부분을 해당 클래스의 생성자에 담았다.

 

따라서 생성자로 정점의 개수만큼의 LinkedList를 담았다.

 

그리고 

	public void addEdge(int v1, int v2) {
		adj[v1].add(v2);
		adj[v2].add(v1);
	}

위 소스로 출발 정점의 LinkedList에 도착정점을 add하여 인접노드를 연결 시켰다.

 

 

그래서 위 인접리스트를 출력하게 되면 아래와 같은결과가 나온다.

 

결과

node 1 와 인접 노드 : [2, 3]
node 2 와 인접 노드 : [1]
node 3 와 인접 노드 : [1, 4, 5]
node 4 와 인접 노드 : [3]
node 5 와 인접 노드 : [3]

 

 

 

 

참고자료 : https://mr-dan.tistory.com/30

트리 구현 - 인접행렬, 인접리스트