[자료구조] 인접행렬로 구현한 그래프 (Java)

그래프는 인접행렬을 통해서도 구현이 가능하다. 

 

인접행렬을 통한 그래프의 특성과 장단점부터 살펴보자.

 

인접행렬 특성

인접 행렬은 그래프와의 연결관계를 이차원 배열로 나타내는방식이다.

 

 

인접행렬의 장단점

 

 

장점

 

1. 구현이 쉽다.

 

2. 노드 i와 j가 연결되어 있는지 확인하고 싶을때 index로 바로 확인이 가능하기 때문에

시간복잡도 O(1)을 가진다.

 

단점 

 

1. 전체 노드의 개수가 V개 일때 어떤 특정 노드의 연결된 노드를 확일하고 싶을때 

해당 노드와 연결된 노드가 있는지 배열로 일일히 체크 해야하기 때문에 O(V)의 시간이 걸린다.

 

2. 노드개수만큼의 이차원 배열을 만들어야 하기 때문에 메모리를 O(V^2)의 메모리 복잡도를 가진다.

따라서 노드의 수에 비해 간선의 수가 적은 그래프에는 적절하지 않다.

 

 

 

그럼 이제는 인접행렬로 그래프를 구현하는 방법에 대해서 알아보자.

 

나는 이차원 배열을 생성하고 

클래스의 생성자로 노드의 수를 받아 노드의 수만큼 이차원배열을 생성한다음 

해당 배열에 값을 입력하는 방식으로 했다.

 

소스를 살펴보자.

 

AdjMatrix Class

public class AdjMatrix {
	private int[][] adjGraph; //정점에 대한 그래프
	private int vertax; //정점
	
	
	public AdjMatrix(int vertax) {
		super();
		this.vertax = vertax;
		this.adjGraph = new int[vertax][vertax];
	}
	
	public void addEdge(int v1, int v2) {
		adjGraph[v1-1][v2-1] = 1;
		adjGraph[v2-1][v1-1] = 1;
	}
	
	public void printGraph() {
		for(int i = 0; i<vertax;i++) {
			System.out.print((i+1)+" : ");
			for(int j = 0; j<vertax; j++) {
				System.out.print(adjGraph[i][j]+" ");
			}
			System.out.println();
		}
	}
}

 

Main 함수

public class PreTest {

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

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

}