[알고리즘]그래프2 - 구현(feat. Java)

2차원 배열

2차원 배열을 사용하여 정점에서 다른 정점으로 가는 간선의 존재유무(1 : 존재, 0 : 없음)를 알 수 있다. 2차원 배열을 사용할 경우 연결된 정점을 찾기 쉽고 구현이 쉽다는 장점이 있지만 O(n^2)의 공간 복잡도를 가진다는 단점이 있다.

그래프와 이차원 배열

 

구현 코드

public static void main(String[] args) {
		int[][] edges = new int[][] {
			{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
		};
		
		int n = 5; //정점의 개수
		
		int[][] matrix = new int[n + 1][n + 1];
		
		for(int[] edge : edges) { //무방향 그래프이기 때문에 양쪽 모두 1로 초기화
			matrix[edge[0]][edge[1]] = 1;
			matrix[edge[1]][edge[0]] = 1;
		}
		
        //출력
		for(int i = 1 ; i <= n ; i++) {
			for(int j = 1 ; j <= n ; j++) {
				System.out.print(matrix[i][j]+" ");
			}
			System.out.println();
		}
}

 

 

리스트

배열 대신 리스트를 사용하여 구현하는 것도 가능하다. 2차원 배열을 리스트로 변경한다고 생각하면 되는데 이 때에 1차원만 리스트를 사용한다면 배열 + 리스트의 조합이 되고, 모두 리스트를 사용한다면 리스트 + 리스트 조합이 되는 것이다.

 

리스트의 경우, 필요한 만큼만 공간을 사용하기 때문에 공간 낭비가 적지만 2차원 배열보다는 구현이 어렵다는 단점이 있다.

 

그래프와 리스트

 

배열 + 리스트 구현 코드

public static void main(String[] args) {
		int[][] edges = new int[][] {
			{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
		};
		
		int n = 5;
		
		ArrayList<Integer>[] list = new ArrayList[n + 1];

		for (int i = 0; i <= n; i++) list[i] = new ArrayList<>();
		
		for(int[] edge : edges) {
			list[edge[0]].add(edge[1]);
			list[edge[1]].add(edge[0]);
		}
		
        //출력
		for (int i = 1; i <= n; i++) {
			for(int j = 0 ; j < list[i].size();j++)
				System.out.print(list[i].get(j)+" ");
			System.out.println();
		}
}

 

 

리스트 + 리스트 구현 코드

public static void main(String[] args) {
		int[][] edges = new int[][] {
			{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
		};
		
		int n = 5;
		
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		
		for(int i = 0 ; i <= n ; i++) list.add(new ArrayList<>());
		
		for(int[] edge : edges) {
			list.get(edge[0]).add(edge[1]);
			list.get(edge[1]).add(edge[0]);
		}
		
        //출력
		for (int i = 1; i < list.size(); i++) {
			for(int j = 0 ; j < list.get(i).size(); j++) 
				System.out.print(list.get(i).get(j)+" ");
			System.out.println();
		}
}