[Data Structure] Graph (그래프)

* Graph (그래프)

그래프란 어떤 상태 혹은 객체 간의 관계를 나타내는 자료구조입니다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성됩니다.
정점이란 어떠한 상태 혹은 객체를 나타냅니다. 간선은 그러한 정점 간의 관계, 그중에서도 연결성을 표현하는 요소입니다.

아래 그림은 그래프의 개념이 퍼지기 시작한 '쾨니히스베르크의 다리 건너기 문제'의 쾨니히스베르크의 다리를 도식화한 두 그림입니다.
A, B, C, D로 나눠진 4개의 구역과 각 구역을 잇는 a, b, c, d, e, f, g 7개의 다리가 있습니다. 왼쪽이 일반적으로 사용되는 그림이며, 이를 그래프 형태로 나타낸 것이 오른쪽의 그림입니다.
여기서 원으로 표현된 A, B, C, D가 정점이며 이 정점들을 연결하는 실선 a, b, c, d, e, f, g가 두 지역을 오고 갈 수 있음을 의미하는 간선이 됩니다.

<쾨니히스베르크의 다리 1>

 

<쾨니히스베르크의 다리 2>

이를 수학적으로 표현하면 아래와 같습니다.

전체그래프 G = (V, E)
정점 집합 V(G) = {A, B, C, D}
간선 집합 E(G) = {a, b, c, d, e, f, g}

이러한 정점과 간선의 관계를 표현하는 말로 인접(adjacent)과 부속(incident)이 있습니다. 정점 u, v가 있고 이 두 정점을 잇는 간선 e가 있다고 가정합시다. 이때 정점 u, v는 e로 인해 서로 인접합니다. 같은 상황에서 간선 e는 정점 u, v에 부속합니다.

그래프에는 크게 무방향 그래프(undirected graph, 무향 그래프)와 단방향 그래프(directed graph, 유향 그래프)가 있습니다.
무방향 그래프란 위의 쾨니히스베르크의 다리와 같이 모든 간선이 양방향으로 연결된 그래프입니다. 정점 u, v에 대해 무방향 그래프에서는 u->v라면 v->u이며, u->v가 불가능하다면 v->u 역시 불가능합니다.
반면 단방향 그래프는 각 간선이 방향을 가집니다. 따라서 정점 u에서 정점 v로 가는 간선 e가 있다면 이는 u->v를 의미할 뿐, v->u를 의미하는 것은 아닙니다.
단방향 그래프에서 u->v를 연결하는 간선이 있을 때 u는 v에 인접한다, v는 u로부터 인접하다 라고 표현할 수 있습니다.

<무방향 그래프>

 

<단방향 그래프>

간선은 따로 이름을 주지 않더라도 부속한 두 정점으로 표현할 수 있습니다. 무방향 그래프의 경우 u와 v를 연결하는 간선은 (u, v)와 같이 표현합니다. 단방향 그래프의 경우 u에서 나가 v로 들어오는 간선을 로 표현합니다.
따라서 위의 무방향 그래프 G1과 단방향 그래프 G2를 아래와 같이 표현할 수 있습니다.

G1 = (V, E)
V(G1) = {A, B, C}
E(G1) = {(A, B), (B, C)}

 

G2 = (V, E)
V(G2) = {A, B, C}
E(G2) = {<A, B>, <B, C>}

그래프에서 쓰이는 또 다른 개념으로는 차수(degree)가 있습니다. 차수란 각 정점에 부속된 간선의 수로, 무방향 그래프에서 어떤 정점 v의 차수란 v에 부속된 간선의 개수입니다. 단방향 그래프에서 정점의 차수는 입력차수(in-degree)와 출력차수(out-degree)로 나누어집니다. 정점 v의 입력차수는 v로 들어오는 간선의 수이며 출력차수는 v에서 나가는 간선의 수와 같습니다.

이러한 그래프를 코드로 표현하는 데에는 크게 두 가지 방법이 사용됩니다. 첫 번째는 인접 행렬(adjacency matrix)을 이용한 표현입니다. 인접 행렬이란 각 정점이 다른 정점과 연결된 상태에 관한 정보를 나타내는 정사각행렬입니다. 예를 들어, 정점 u에서 나가 정점 v로 들어오는 간선이 있다면 1, 아니면 0으로 인접 행렬을 채웁니다. 무방향 그래프의 경우, u->v간선이 v->u 간선과 동일하므로 대각선(diagonal)을 중심으로 대칭(symmetric)됩니다. 아래는 정점이 4개인 단방향 그래프의 예시입니다.

<인접 행렬을 이용한 단방향 그래프의 표현>

두 번째 방법은 인접 리스트(adjacency list)를 이용한 표현입니다. 인접 리스트란 한 정점과 인접한 정점들을 리스트로 표현하는 형태입니다.
아래는 정점이 4개인 단방향 그래프에서 정점 u에서 나가 v로 들어오는 간선들의 정보를 인접 리스트로 나타낸 예시입니다.

<인접 리스트를 이용한 단방향 그래프의 표현>

그렇다면 두 개의 표현법은 어떻게 다를까요?
2차원 인접 행렬의 이름을 adj_matrix, 인접 리스트의 이름을 adj_list라고 할 때 두 표현법은 아래와 같은 장단점을 가집니다. 
두 정점 u, v가 인접한지를 확인하는 연산을 생각해봅시다. 인접 행렬의 경우 이 연산은 adj_matrix[u][v]의 값을 참조하기만 하면 됩니다. 즉 O(1)의 시간복잡도를 가집니다. 
하지만 인접 리스트는 adj_list[u]에 연결된 원소들을 순회하며 v가 존재하는지 확인해야 합니다. 최악의 경우 이 연산은 O(|V|)의 시간복잡도를 가집니다. 
반면 정점 u에 연결된 모든 정점을 탐색하는 상황을 생각해봅시다. 인접 행렬의 경우 어떤 정점들이 연결되어있는지 알기 위해서 모든 adj_matrix[u][i]를 참조해야 합니다. 따라서 O(|V|)의 시간이 걸립니다. 
하지만 인접 리스트의 경우에는 adj_list[u]에 연결된 정점의 개수만큼만 걸립니다. 물론 최악의 경우 O(|V|)지만 이 탐색이 전체 그래프로 확장된다면 달라집니다. 
인접 행렬의 경우에는 O(|V|^2)을 모두 돌아야 하지만, 인접 리스트의 경우 O(|E| + |V|)가 됩니다. 이는 각 표현에 사용된 모든 값을 참조하기 때문인데, 인접 행렬의 공간복잡도는 O(|V|^2)이며 인접 리스트의 공간복잡도는 O(|E|)입니다. 
따라서 각 정점 간의 연결관계 참조가 잦다면 인접 행렬 표현이, 순회가 잦거나 |V|가 큰 그래프에서는 인접 리스트의 표현이 유리합니다.

* 출처 & 참고 링크

Samsung CodeGround

BFS & DFS

최소 신장 트리(MST, Minimum Spanning Tree)