[Algorithm]그래프 - 2. 그래프의 구현

이전 글

[Algorithm]그래프 - 1. 그래프의 개념

 

그래프 구현

• 프로그래밍 언어로 그래프를 구현하는 방식에는 인접 행렬(adjacency matrix)을 이용한 방법과 인접 리스트(adjacency list)를 이용하는 방법이 있다.

인접 행렬

• 2차원 배열을 이용한 방법이다.
• 2차원 배열의 열의 Index가 출발 노드 이고 행의 Index가 도착 노드, 행의 값을 가중치로 한다. 따라서 노드의 개수에 맞춰 배열의 크기를 지정해 주어야 한다.(노드의 개수가 4라면 int[4][4] 크기의 배열이 필요함.)

< 가중치가 있는 방향 그래프A >

• 위의 그래프를 JAVA에서 인접 행렬로 나타내면 다음과 같다.

// Node의 개수가 4개 이기 때문에 배열의 크기=int[4][4]
int[][] graph = {
                {-1, 1, 2, -1},
                {-1, -1, -1, 3},
                {-1, -1, -1, 4},
                {-1, 2, -1, -1}
        };

int weight2_3 = graph[2][3]; // = 4(2->3의 가중치)

• 갈수 없는 곳은 코드에서 처럼 -1 값을 주거나 무한대의 값을 주어도 된다.

인접 리스트

• 노드(vertex)와 가중치(weight)를 묶어서 관리하는 방법이다.
• 2차원 리스트(배열)와 노드와 가중치를 묶을 데이터셋(배열, 구조체, 클래스 튜플 등)이 필요 하다. 데이터셋은 구현자가 편한대로 구현하면 된다.
• 2차원 리스트의 첫번째의 Index를 출발 노드로 사용한다. 즉, 첫번째 열의 Index를 출발 노드로 사용하는 점은 인접 행렬과 같다.
• 2차원 리스트의 두번째에 노드와 가중치를 묶은 데이터셋을 추가 한다.

< 인접 리스트 시각화 >

• 가중치가 있는 방향 그래프A를 JAVA에서 인접 리스트로 나타내면 다음과 같다.

ArrayList<ArrayList<Node>> graph = new ArrayList<>();
// 노드의 개수만큼 for문을 돌며 각 노드를 초기화.
for(int i = 0; i < 4; i++) {
    graph.add(new ArrayList<Node>());
}

// 0노드 초기화
// 0 -> 1, 가중치는 1
graph.get(0).add(new Node(1, 1));
// 0 -> 2, 가중치는 2
graph.get(0).add(new Node(2, 2));
// 1 -> 3, 가중치는 3
graph.get(1).add(new Node(3, 3));
// 2 -> 3, 가중치는 4
graph.get(2).add(new Node(3, 4));
// 3 -> 2, 가중치는 2
graph.get(3).add(new Node(2, 2));

class Node { // 노드와 가중치를 묶을 데이터 셋
    int num; // 도착 노드 번호
    int weight; // 가중치

    Node(int num, int weight) {
        this.num = num;
        this.weight = weight;
    }

}

 

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

• 노드 수에 비해 간선 수가 아주 적은 그래프를 희소 그래프라고 한다. 인접 행렬을 이용해 희소 그래프를 표현하는 경우 불필요하게 메모리를 많이 차지 한다.
  • 인접 행렬은 배열의 index 자체를 노드의 값으로 사용하기 때문에 간선이 없어 값을 -1로 표현하더라도 노드의 개수만큼 배열의 길이를 정해야한다. 따라서 -1은 불필요한 메모리 공간을 차지하게 된다. 따라서 인접 행렬로 그래프를 표현하면 공간 복잡도는 간선의 수와 상관없이 무조건 O(V^2)이다.
  • 반면 인접 리스트는 배열의 index 대신 도착 노드의 번호를 데이터 셋에 가중치 정보와 함께 저장 하기 때문에 노드의 개수만큼 index를 생성할 필요가 없다. 따라서 인접 리스트로 그래프를 표현하면 공간 복잡도는 O(E + V)가 된다.
• 인접 행렬은 노드의 값이 순차적이지 않고 1, 2, 100, 9999 처럼 간격이 큰 경우도 불필요한 메모리를 많이 차지 한다.
  • 이 경우도 배열의 index를 노드의 값으로 사용하기 때문에 생기는 문제 이다. 9999를 표현하기 위해서는 9999번 index를 만들어야 됨으로 배열의 크기를 10000으로 잡아야 한다. 따라서 노드의 개수는 4개 인데 배열의 크기는 10000개가 되고 공간 복잡도는 10000^2 =100,000,000가 된다.
• 인접 행렬은 O(1)의 시간 복잡도로 특정 경로의 가중치를 알 수 있지만 특정 노드의 모든 경로의 가중치를 탐색하기 위해서는 V번을 반복하여야 한다.
  • 인접 행렬의 경우 배열의 index가 곧 노드 이기 때문에 graph[2][3] 과 같은 방식으로 2에서 3으로 가는 경로의 가중치를 한번에 알 수 있지만 모든 경로를 탐색 해야 될 경우 노드의 개수만큼 반복되어야 한다.
  • 인접 리스트의 경우 2에서 3으로 가는 경로를 한번에 찾을 수 없다. 따라서 2번노드 안에 저장된 데이터셋을 순회하면서 3번 노드를 찾은 뒤 가중치를 알 수 있다.
  • 인접 행렬의 경우 특정 노드 안의 경로 데이터가 노드 수만큼 있지만 인접 리스트의 경우 해당 노드가 이동할 수 있는 경로 데이터만 있기 때문에 모든 경로 탐색에 서는 인접 리스트의 탐색속도가 빠르다.

	공간 복잡도	시간 복잡도 (특정 노드의 간선을 찾을 때)	시간 복잡도 (모든 정점에 대한 간선 탐색)
인접 행렬	O(V^2)	O(1)	O(E^2)
인접 리스트	O(E + V)	O(E), ⍬(E/V)	O(V+E)

 

다음글

[Algorithm]그래프 - 3. 깊이 우선 탐색(DFS) - Stack