**그래프란 어떤 상태 혹은 객체 간의 관계를 나타내는 자료구조입니다. 그래프는 정점(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가 두 지역을 오고 갈 수 있음을 의미하는 간선이 됩니다.** ![](/uploads/blog/btsG4Besp8P.jpg)![](/uploads/blog/btsG34HXE87.jpg) **이를 수학적으로 표현하면 아래와 같습니다.** **전체그래프 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로부터 인접하다 라고 표현할 수 있습니다.** ![](/uploads/blog/btsG7oLgZej.jpg)![](/uploads/blog/btsG5Tywhru.jpg) \< 양방향 그래프> \< 단방향 그래프 > **간선은 따로 이름을 주지 않더라도 부속한 두 정점으로 표현할 수 있습니다. 무방향 그래프의 경우 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) = \{\, \}** **그래프에서 쓰이는 또 다른 개념으로는 차수(degree)가 있습니다. 차수란 각 정점에 부속된 간선의 수로, 무방향 그래프에서 어떤 정점 v의 차수란 v에 부속된 간선의 개수입니다. 단방향 그래프에서 정점의 차수는 입력차수(in-degree)와 출력차수(out-degree)로 나누어집니다. 정점 v의 입력차수는 v로 들어오는 간선의 수이며 출력차수는 v에서 나가는 간선의 수와 같습니다.** **이러한 그래프를 코드로 표현하는 데에는 크게 두 가지 방법이 사용됩니다. 첫 번째는 인접 행렬(adjacency matrix)을 이용한 표현입니다. 인접 행렬이란 각 정점이 다른 정점과 연결된 상태에 관한 정보를 나타내는 정사각행렬입니다. 예를 들어, 정점 u에서 나가 정점 v로 들어오는 간선이 있다면 1, 아니면 0으로 인접 행렬을 채웁니다. 무방향 그래프의 경우, u->v간선이 v->u 간선과 동일하므로 대각선(diagonal)을 중심으로 대칭(symmetric)됩니다. 아래는 정점이 4개인 단방향 그래프의 예시입니다.** ![](/uploads/blog/btsG5F8eGMW.jpg) 인접 행렬을 이용한 단방향 그래프의 표현 **두 번째 방법은 인접 리스트(adjacency list)를 이용한 표현입니다. 인접 리스트란 한 정점과 인접한 정점들을 리스트로 표현하는 형태입니다.** **아래는 정점이 4개인 단방향 그래프에서 정점 u에서 나가 v로 들어오는 간선들의 정보를 인접 리스트로 나타낸 예시입니다.** ![](/uploads/blog/btsG36lukWJ.jpg) 인접 리스트를 이용한 단방향 그래프의 표현 **그렇다면 두 개의 표현법은 어떻게 다를까요?** **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|가 큰 그래프에서는 인접 리스트의 표현이 유리합니다.** **다음은 C++로 나타낸 코드입니다.** 더보기 ```cpp #include #include #include #define MAX 55 using namespace std; int main() { int adj_matrix[MAX][MAX], n; cin >> n; vector < list < int > > head(n + 1); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { cin >> adj_matrix[i][j]; if (adj_matrix[i][j]) head[i].push_front(j); } for (int i = 1; i <= n; i++) { cout << i << " : "; if (!head[i].empty()) for (auto x : head[i]) cout << x << " "; cout << endl; } return 0; } ``` **다음은 Java로 나타낸 코드입니다.** 더보기 ```java import java.util.*; public class Main { public static void main(String args[]) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[][] adj_matrix = new int[n + 1][n + 1]; ArrayList[] adj_list = new ArrayList[n + 1]; for (int i = 1; i <= n; i++) { adj_list[i] = new ArrayList<>(); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { adj_matrix[i][j] = scanner.nextInt(); if (adj_matrix[i][j] == 1) { adj_list[i].add(j); } } } for (int i = 1; i <= n; i++) { System.out.print(i + " : "); for (int j = 0; j < adj_list[i].size(); j++) { System.out.print(adj_list[i].get(j) + " "); } System.out.println(); } } } ``` **다음엔 리스트에 대해 알아보겠습니다.**

카테고리: 자료구조

Graph (그래프)