[그래프] 그래프의 표현 (인접 행렬, 인접 리스트, 간선 리스트)

그래프(Graph)

• 정점 6개, 간선 8개
• 방향이 없는 그래프
• 정점 : {1, 2, 3, 4, 5, 6}
• 간선 : {(1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)}

그래프의 구현 : 인접행렬

• 정점의 개수를 V라고 했을 때
• V x V 크기의 2차원 배열을 이용
• 정점의 연결관계를 0과 1로 표현
• A[i][j] = 1(연결이 되어있을 때), 0(연결이 되어있지 않을 때)
• 양방향 그래프일 경우 A[i][j] = A[j][i]

구현 코드

import java.util.Scanner;

public class AdjacencyMatrix {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] line = sc.nextLine().split(" ");
		int n = Integer.parseInt(line[0]);
		int m = Integer.parseInt(line[1]);
		int[][] a = new int[n+1][n+1];
		
		for(int i=0; i<m; i++){
			line = sc.nextLine().split(" ");
			int u = Integer.parseInt(line[0]);
			int v = Integer.parseInt(line[1]); 
			a[u][v] = 1;
			a[v][u] = 1; // 방향 그래프일 경우는 사라짐
		}
		
		for(int i=1; i<=n; i++){
			for(int j=1; j<=n; j++){
				System.out.print(a[i][j]);
			}
			System.out.println();
		}
	}
}

그래프의 구현 : 인접 리스트

• 각각의 정점에 대하여 인접한 정점 번호를 저장
• 링크드 리스트를 이용해서 구현
• A[i] = i 와 연결된 정점을 링크드 리스트로 포함하고 있음
• 링크드 리스트는 구현하는데 시간이 오래걸리기 때문에
• 주로 vector와 같이 길이를 변경할 수 있는 배열을 이용하여 구현(C 경우)

구현 코드

import java.util.*;

public class AdjacencyList {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] line = sc.nextLine().split(" ");
		int n = Integer.parseInt(line[0]);
		int m = Integer.parseInt(line[1]);
		
		// ArrayList<Integer> 형태의 배열 선언
		ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];
		for(int i=1; i<=n; i++){
			a[i] = new ArrayList<Integer>();
		}
		for(int i=0; i<m; i++){
			line = sc.nextLine().split(" ");
			int u = Integer.parseInt(line[0]);
			int v = Integer.parseInt(line[1]); 
			a[u].add(v);
			a[v].add(u);
		}
        for (int i=1; i<=n; i++) {
            Collections.sort(a[i]);
        }       
        for(int i=1; i<=n; i++){
        	for(int j=0; j<a[i].size(); j++){
        		System.out.print(a[i].get(j));
        	}
        	System.out.println();
        }
	}
}

인접행렬, 인접리스트의 장단점

Q1. x와 y가 연결되어 있는가?

Q2. x와 연결된 정점이 모두 무엇인가?

인접행렬

장점 : x와 y의 연결 여부를 O(1)에 알 수 있음 Q1

단점 : 실제 연결된 정점 수와 관계없이 연결된 정점을 찾는데 O(n)이 걸림 Q2

         실제 간선의 개수와 관계없이 무조건 개의 칸을 써야 함 (공간 활용)

인접리스트

장점 : 연결된 정점을 모두 찾는데 필요한 만큼만 봄 Q2

         필요한 만큼만 공간을 활용함 (공간 활용)

단점 : x와 y의 연결 여부를 보려면 연결된 정점을 모두 봐야함 O(deg(v)) // degree = 차수 Q1

그래프의 구현 : 간선 리스트

• 배열을 이용해서 구현함
• 간선 리스트는 간선을 모두 저장하고 있음

• E라는 배열에 간선을 모두 저장함
• 각 간선의 앞 정점을 기준으로 개수를 셈

		for(int i=0; i<m; i++){
			cnt[e[i][0] += 1;
		}

• E배열에서 i 정점과 연결된 간선을 찾기 위해서

• i-1정점의 개수와 i 정점의 개수를 더함

		for(int i=1; i<n; i++){
			cnt[i] = cnt[i-1] + cnt[i];
		}

• i번 정점과 연결된 간선은

• E배열에서 C[i-1]~ cnt[i]-1까지임
• 3번 정점의 간선은 cnt[2]부터 cnt[3]-1, 즉 E[6]부터 E[7]까지가 3번 정점의 간선임
• 4번 정점의 간선은 cnt[3]부터 cnt[4]-1, 즉 E[8]부터 E[11]까지가 4번 정점의 간선임