1. 그래프(Graph)란?
■ 그래프는 연결되어 있는 객체 간의 관계를 표현하는 자료구조로, 객체들이 서로 복잡하게 연결되어 있는 구조를 표현할 수 있다.
■ 그리고 그래프는 가장 일반화된 자료구조이다.
- 선형 자료구조들, 트리 등은 모두 그래프로 표현할 수 있으므로 그래프의 한 종류로 볼 수 있기 때문이다.
■ 그래프는 V와 E로 구성된다. 여기서 V는 정점(vertex) 또는 노드, E는 간선(edge) 또는 링크(link)를 의미하며, 정점은 객체를 표현한 것이고 간선은 정점(객체)들 간의 관계를 표현한 것으로 정점 \( V_1, V_2 \)를 연결하는 간선은 \( (V_1, V_2) \), 정점의 쌍으로 표현한다.
■ 그래프 G는 (V, E)로 나타낸다. G = (V, E)로 표현하는데, V(G)는 정점들의 집합, E(G)는 그래프 G의 간선들의 집합이다. 따라서 집합 V와 E가 정의되어야 그래프 하나가 정의된다고 볼 수 있다.
■ 이렇게 그래프 G는 집합 V와 집합 E로 구성된 것이기 때문에, 시각적으로는 서로 다른 그래프로 보이지만, 실제로는 동일한 그래프일 수 있다.
■ 예를 들어 다음 두 그래프 A, B는 시각적으로 서로 다른 그래프처럼 보이지만, 두 그래프는 같은 객체들을 가지며 객체들 사이의 관계도 동일하기 때문에 같은 그래프이다.
2 그래프의 종류
■ 그래프의 종류는 무방향 그래프, 방향 그래프, 가중치 그래프, 부분 그래프가 있다.
2.1 무방향 그래프(undirected graph)
■ 무방향 그래프는 '간선에 방향이 표시되지 않은 그래프'이다. 따라서 하나의 간선은 특정한 방향이 없으므로 양방향으로 갈 수 있는 길을 의미한다.
■ 예를 들어 그래프 \( G_1 \)에 정점 A, B가 있을 때 A에서 B로 가는 간선을 (A, B), B에서 A로 가는 간선을 (B, A)라고 한다면, 간선 (A, B)와 간선 (B, A)는 동일한 간선이다.
■ 무방향 그래프는 모든 정점들이 서로 연결되어 있을 때, 최대 간선 수는 \( \dfrac{n(n - 1)}{2} \)이다.
- 무방향 그래프에서는 두 정점 쌍 사이에 한 개의 간선만 존재할 수 있다.
- 따라서 \( n \)개의 정점이 있을 때, 첫 번째 정점은 \( n - 1 \) 개의 정점과 연결될 수 있고, 두 번째 정점은 첫 번째 정점과 이미 연결되어 있으므로 \( n - 2 \) 개의 정점과 연결될 수 있다. 세 번째 정점은 이미 첫 번째와 두 번째 정점과 연결되어 있으므로 나머지 \( n - 3 \) 개의 정점과 연결될 수 있다. \( n - 1 \) 번 째 정점은 남은 한 개의 정점과 연결할 수 있고 마지막 \( n \) 번째 정점은 이미 모든 정점과 연결되었으니 더 이상 연결할 수 있는 정점이 존재하지 않는다.
■ 즉 무방향 그래프는 모든 정점들이 서로 연결되어 있을 때, 첫 번째 정점부터 \( n - 1 \) 정점까지 간선을 가질 수 있으며, 각 정점에서 가질 수 있는 간선의 수를 모두 더하면 최대 간선 수는 \( (n - 1) + (n -2) + (n - 3) + \ldots + 1 = \dfrac{n(n - 1)}{2} \) 개가 되는 것이다.
2.2 방향 그래프(directed graph)
■ 방향 그래프는 '간선에 방향이 존재하는 그래프'이다. 방향을 나타내기 위해 간선을 화살표로 나타내는데, 여기서 간선은 무방향 그래프와 다르게 한쪽 방향으로만 갈 수 있다.
■ 예를 들어 그래프 \( G_1 \)에 정점 A, B가 있을 때, A에서 B로 가는 간선을 <A, B>, B에서 A로 가는 간선을 <B, A>라고 한다면, 간선 <A, B>는 정점 A에서 B로만 갈 수 있는 간선을 의미하며, 간선 <B, A>는 정점 B에서 A로만 갈 수 있는 간선을 의미하기 때문에 <A, B>와 <B, A>는 서로 다른 간선이다.
■ 이렇게 방향 그래프는 각 정점 쌍 사이에 두 방향의 간선이 모두 존재할 수 있다.
■ 따라서 정점이 \( n \)개 있을 때, 각 정점에서 \( n - 1 \)개의 정점으로 향하는 간선이 가능하기 때문에 가능한 최대 간선 수는 \( n(n - 1) \)이다.
2.3 가중치 그래프(weighted graph)
■ 가중치 그래프는 '간선에 비용이나 가중치가 할당된 그래프'이며, 네트워크(network)라고도 한다.
■ 따라서 두 정점 간의 연결 유무뿐만 아니라, 간선 위에 두 정점 사이에 어떤 비용, 가중치를 나타낼 수 있으므로 더 복잡한 관계를 표현할 수 있다.
2.4 부분 그래프(subgraph)
■ 부분 그래프는 '원래의 그래프에서 일부 정점이나 간선을 제외하며 만든 그래프'이다.
■ G = (V, E)에서 V의 부분 집합을 V', E의 부분 집합을 E'라고 했을 때, 부분 집합 V'과 E'로 이루어진 그래프 G' = (V', E')를 G의 부분 그래프라고 한다.
3 그래프 관련 용어
3.1 인접 정점(adjacent vertex)
■ 인접 정점은 '간선에 의해 직접 연결된 정점'이다.
■ 예를 들어 다음 그래프에서 정점 B의 인접 정점은 A와 C이다.
3.2 정점의 차수(degree)
■ 차수는 '정점에 연결된 간선의 수'이다.
■ 무방향 그래프에서 정점의 차수는 '정점에 인접한 정점의 수'가 된다. 이는 무방향 그래프에서 두 개의 정점을 연결한 하나의 간선은 양방향으로 갈 수 있기 때문이다.
■ 이러한 무방향 그래프의 특성 때문에 무방향 그래프에서 모든 정점의 차수의 합은 간선의 수의 2배가 된다.
■ 예를 들어 위의 무방향 그래프 \( G_1 \)에서 A의 차수는 3인데, 이는 'A의 인접 정점 개수 == 정점 A에 연결된 간선의 수'와 동일하다. 따라서 A의 차수는 3, B의 차수는 2, C의 차수는 3, D으이 차수는 2이므로 모든 정점의 차수의 합은 10인데, 정확히 간선의 수 5의 2배이다.
■ 방향 그래프에서는 정점의 차수가 두 가지로 나누어진다.
- ① 진입 차수(in-degree): 외부에서 오는 간선의 수
- ② 진출 차수(out-degree): 정점에서 외부로 향하는 간선의 수
■ 방향 그래프에서 모든 진입(진출) 차수의 합은 간선의 수이다. 즉, 방향 그래프는 '모든 진출 차수의 합 == 간선의 개수 == 모든 진입 차수의 합'이 성립한다.
■ 예를 들어 다음과 같은 방향 그래프가 있을 때,
- 정점 A의 진출 차수는 A에서 나가는 간선의 수, A의 진입 차수는 A에 들어오는 간선의 수이므로 A의 진출 차수는 1, 진입 차수는 1이다.
- 정점 B는 A에서 오는 간선 1개, A와 C로 나가는 간서이 2개이므로 진출 차수는 2, 진입 차수는 1이다.
- 정점 C는 진출 차수는 0, 진입 차수는 1이다.
- 이때, '전체 진출 차수의 합(3) == 간선의 개수(3) == 전체 진입 차수의 합(3)'이 성립하는 것을 볼 수 있다.
3.3 그래프의 경로(path)와 경로의 길이(length)
■ 경로는 '어떤 정점에서부터 어떤 정점까지 간선을 따라 갈 수 있는 길을 의미하며, 방향 그래프에서는 방향을 고려해서 경로를 생각해야 한다.
■ 예를 들어 다음과 같은 무방향 그래프는 방향이 없으므로 정점 A에서 D까지 간선을 따라 이동할 수 있다.
- 정점 A에서 D까지 이동하는 경로를 'A \( \rightarrow \) D'라고 했을 때,
- A \( \rightarrow \) D = (A, B), (B, C), (C, D) = A, B, C, D (A에서 D까지 가는 경로로서 A, B, C, D가 있다는 것을 의미)
- 한 가지 주의할 점은 A, B, D, C는 경로가 아니다. 정점 B와 D 사이에 간선 (B, D)가 없기 때문이다.
■ 즉, 정점 \( s \)에서 \( e \)까지의 정점들이 \( 's, V_1, V_2, \ldots, V_k, e' \) 라면, 두 정점 사이에 반드시 간선 \( (s, V_1), (V_1, V_2), \ldots, (V_k, e) \)가 존재해야지만 경로 \( 's, V_1, V_2, \ldots, V_k, e' \)가 존재한다고 할 수 있다.
■ 이 점은 방향 그래프에서도 마찬가지이다. 두 정점 사이에 반드시 간선 \( <s, V_1>, <V_1, V_2>, \ldots, <V_k, e> \)가 존재해야 경로 \( 's, V_1, V_2, \ldots, V_k, e' \)가 존재한다고 할 수 있다.
■ 예를 들어 다음과 같은 방향 그래프가 있을 때,
- 경로 'A \( \rightarrow \) D'는 존재하지 않는다. 왜냐하면, 정점 D에서 나가는 간선만 존재하고 D로 들어가는 간선이 없기 때문이다. 따라서 이 예시에서 가능한 경로는 'A \( \rightarrow \) C'이고, A \( \rightarrow \) C = <A, B>, <B, C> = A, B, C 이다.
■ 경로의 길이는 '경로를 구성하는데 사용된 간선의 수'이다.
■ 예를 들어 위의 무방향 그래프에서 경로 'A \( \rightarrow \) D'를 구성하는데 사용된 간선의 수는 3이다. 따라서 경로의 길이는 3이고, 방향 그래프에서 경로 'A \( \rightarrow \) C'의 길이는 2이다.
3.4 단순 경로(simple path)
■ '경로 중 반복되는 간선이 없는 경로'를 단순 경로라고 한다. 즉 '정점이 중복되지 않는 경로'를 의미한다.
■ 단순 경로의 '시작 정점과 종료 정점이 같은 경로'를 사이클이라 한다.
■ 예를 들어 다음과 같은 그래프가 있을 때
경로 A \( \rightarrow \) D에는 A, B, C, D / A, B, E, C, D / A, B, E, C, D / A, B, C, B, E, C, D, ... 등이 있을 것이다.
- 경로 중 경로 A, B, C, D와 A, B, E, C, D가 단순 경로이고, 나머지 경로들은 한 번 지나갔던 간선을 다시 지나가므로(= 한 번 방문했던 정점을 재방문하므로) 단순 경로가 아니다.
- 또한 B, E, C만 보면 경로 B, E, C, B는 사이클이 되는 것을 알 수 있다.
3.5 연결 그래프(Connected Graph)
■ 모든 정점들 사이에 경로가 존재하는 그래프, 즉 모든 정점들이 연결된 그래프를 연결 그래프라고 한다.
cf) 모든 정점들이 연결되어 있지 않은 그래프는 비연결 그래프라고 한다.
■ 예를 들어 다음과 같은 그래프는 모든 정점들 사이에 경로가 존재하므로 연결 그래프이다.
■ 이때, 정점 F와 G를 다음과 같이 추가하면 기존의 어떠한 정점(A ~ E)들 중에서도 F나 G에 도달할 수 있는 정점이 없다. 즉, 모든 정점들이 연결되어 있지 않으므로 비연결 그래프이다.
■ 비연결 그래프라도 그래프의 부분 집합이 connected graph라면, 그 부분 집합을 connected component라고 부른다.
■ 예를 들어 위의 그래프에서 전체 그래프를 H, A, B, C, D, E가 연결된 그래프를 \( h_1 \), F와 G를 간선으로 연결한 그래프를 \( h_2 \)라고 할 때
- 정점 F와 G가 연결되어도 전체 그래프는 비연결 그래프이지만, 그래프 H의 부분 집합(A, B, C, D, E가 연결된 그래프, F와 G가 연결된 그래프)이 connected graph임을 볼 수 있다. 이 부분 집합을 \( h_1, h_2 \)라 했을 때, \( h_1 \)과 \( h_2 \)를 connected component라고 부른다.
3.6 트리(tree)
■ 트리는 '사이클을 가지지 않는 연결 그래프'이다.
■ 연결 그래프에서 사이클이 없으면 두 정점을 연결하는 간선은 하나뿐이므로 트리 모양이 된다.
■ 예를 들어 사이클이 없는 연결 그래프를 만들면 트리 형태가 되지만, 두 개의 경로가 존재하면 사이클이 형성되어 트리 형태가 되지 않는다.
■ 즉, 어떠한 노드 s에서 임의의 노드 e로 가는 단순 경로 (s \(rightarrow \) e)가 1개만 존재할 때, 그런 그래프를 tree라고 한다.
■ 예를 들어 위의 트리에서는 A \( \rightarrow \) C, A \( \rightarrow \) D, A \( \rightarrow \) E, ... 등 어떤 노드에서 임의의 노드로 가는 단순 경로가 1개만 존재한다. 그러나 오른쪽처럼 사이클이 형성되어 있는 경우, A에서 B로 가는 단순 경로가 A, B, D와 A, C, D로 2개가 존재한다.
3.7 완전 그래프(complete graph)
■ 완전 그래프는 '모든 정점 사이에 간선이 존재하는 그래프'이다.
■ 무방향 완전 그래프의 정점의 개수가 \( n \)개 라면, 간선의 수 = \( \dfrac{n(n-1)}{2} \)이다.
4. 그래프의 표현
■ 그래프는 다양한 방법으로 표현할 수 있으며, 어떻게 그래프 G = (V, E)를 표현하느냐에 따라 그래프의 연산을 위한 시간 복잡도가 달라질 수 있다.
■ 특히, G = (V, E)에서 E를 어떻게 표현하느냐가 그래프 표현에서 중요하다.
4.1 인접 행렬(adjacency matrix)을 이용한 표현
■ 그래프를 표현하는 간단한 방법은 행렬을 사용하는 것이며, 정점들의 연결 관계를 표현한 행렬을 인접 행렬이라 한다.
■ 정점의 개수가 \( n \)개 라면, 인접 행렬은 \( n \times n \)의 정방 행렬로 표현된다.
■ 인접 행렬로 표현하는 방법은 다음과 같다.
- 인접 행렬을 M이라 했을 때, 그래프에서 간선 (i, j) 가 있으면 M[i][j] = 1 또는 True 값을 넣어준다.
- 간선이 없으면 M[i][j]에 0 또는 False 또는 None 값을 넣어준다.
- 그리고 자신에서 출발해 자기 자신으로 들어오는 간선을 허용하지 않는다면, 인접 행렬의 대각선은 모두 0이 된다. 따라서 대각선에도 0 또는 False 또는 None 값을 넣어준다.
■ 무방향 그래프를 인접 행렬로 표현하면, 인접 행렬은 대칭 행렬이 된다. 이는 무방향 그래프의 간선이 양방향으로 갈 수 있기 때문이다.
- 예를 들어 무방향 그래프에서 간선 \( (v_1, v_2) \)는 정점 \( v_1 \)에서 \( v_2 \)로의 연결뿐만 아니라, 정점 \( v_2 \)에서 \( v_1 \)으로의 연결을 동시에 의미하기 때문에 \( n \times n \) 행렬로 나타내면 대칭 행렬이 된다.
■ 예를 들어 다음과 같은 (무방향) 가중치 그래프를 인접 행렬로 표현한다면, 인접 행렬에 1, 0이 아닌 가중치 값을 표시하면 된다.
- index 0에 해당하는 정점 A에서 index 1에 해당하는 정점 B로 가는 간선이 존재 \( \rightarrow \) M[0][1] = d
index 0에 해당하는 정점 A에서 index 2에 해당하는 정점 C로 가는 간선이 존재 \( \rightarrow \) M[0][2] = e, .... 이런 식으로 무방향 그래프를 인접 행렬로 표현하면 인접 행렬은 대칭 행렬이 된다.
■ 이렇게 무방향 그래프는 대칭 행렬이 되기 때문에 상삼각 행렬 또는 하삼각 행렬 영역만 저장해 메모리를 절약할 수 있다.
■ 반면, 방향 그래프의 인접 행렬은 일반적으로 대칭이 아니다.
4.2 인접 리스트(adjacency list)를 이용한 표현
■ 각 정점과 인접한 정점들을 리스트로 표현할 수 있다. 이런 리스트를 인접 리스트라고 한다.
- 이때, 리스트로 배열 구조인 파이썬 리스트를 사용할 수도 있고, 링크드 리스트를 사용할 수도 있다.
■ 예를 들어 다음과 같은 그래프를 파이썬 리스트를 사용해 인접 리스트로 표현한다면,
■ 링크드 리스트를 사용할 경우 정점 삽입 시, 제한을 받지 않고 정점의 번호만 알면 인접 정점에 쉽게 접근할 수 있다.
■ 이렇게 방향 그래프에 간선 하나를 추가하면 전체 연결 리스트에 노드 2개가 추가된다. 따라서 인접 리스트에서 만들어지는 '인접 리스트의 노드의 수 = 2 × 간선의 수'이다.
■ 또한 이렇게 노드를 추가할 경우 인접 정점들의 순서가 달라질 수 있지만, 이런 순서는 중요하지 않다.
■ 방향 그래프도 파이썬 리스트나 링크드 리스트를 사용해 인접 리스트로 표현할 수 있다.
■ 링크드 리스트를 사용할 경우 인접 리스트의 노드의 수는 간선의 수와 동일하다.
■ 예를 들어 다음과 같은 방향 그래프를 파이썬, 리스트, 링크드 리스트를 사용해 인접 리스트로 표현하면,
- 파이썬 리스트를 사용할 시, 정점 C는 어떤 간선을 통해서 다른 정점으로 이동할 수 없다. 이렇게 C로 들어오는 간선만 있고 다른 정점으로 나가는 간선이 없으면 C의 인접 리스트는 공백 리스트가 된다.
- 링크드 리스트에서도 마찬가지로 정점 C의 연결 리스트에는 추가할 노드가 없다.
4.3 시간 복잡도 - 인접 행렬 vs 인접 리스트
■ 정점의 수가 \( n \) 개, 간선의 수가 \( e \) 개인 무방향 그래프에서 메모리 공간의 경우,
- 인접 행렬은 노드가 \( n \) 개이면 인접 행렬은 \( n \times n \)이므로, 간선의 수와 무관하게 항상 \( n^2 \)의 메모리 공간이 필요하다. 이런 점 때문에 정점의 개수에 비해 간선의 수가 매우 많은 조밀 그래프(dense graph)에서 효율적이다.
- 인접 리스트는 노드가 \( n \) 개 이면 \( n \) 개의 연결 리스트가 필요하고, 예를 들어 간선 (A, B)이면 노드 A의 연결 리스트에는 B가, B의 연결 리스트에는 A가 들어간다. 즉, 무방향 그래프에서는 한 간선 당 노드 2개의 저장이 필요하므로 간선 \( e \) 개이면, \( 2e \) 개의 노드가 필요하다. 따라서 \( n + 2e \) 개의 메모리 공간이 필요하다. 이런 점 때문에 인접 리스트는 정점의 개수에 비해 간선의 개수가 매우 적은 희소 그래프(sparse graph)에서 효과적이다.
■ 어떤 정점 i에서 다른 정점 j에 연결된 간선을 반환하는 연산은
- 인접 행렬의 경우 M[i][j]를 확인하면 된다. i, j가 주어지면 M[i][j]의 메모리 주소에 직접 접근하여 값을 바로 가져올 수 있으므로 상수 시간 내에 수행될 수 있다. 따라서 이 접근 시간은 입력 크기와 무관하게 항상 일정하며 \( O(1) \) 시간 복잡도를 갖는다.
- 반면, 인접 리스트는 정점 i의 연결 리스트 전체를 조사해야 한다. 즉 정점 i와 연결된 정점을 모두 조사해야 한다. 차수는 정점에 연결된 간선의 수이므로, 정점 i의 차수가 \( d_i \)라면, \( d_i \) 번의 조사가 필요하다. 따라서 시간 복잡도는 \( O(d_i) \)이다.
■ 정점의 차수를 구하는 연산은
- 인접 행렬의 경우, 예를 들어 무방향 그래프에서 정점 i의 차수를 구하고 싶다. 그러면 인접 행렬은 \( n \times n \)으로 정점 i와 연결된 정점은 각 행 또는 열에 '1'로 기록 되어 있으므로 \( n \) 개의 행 또는 열을 조사하면 된다. 따라서 시간 복잡도는 \( O(n) \)이다.
- 인접 리스트는 정점 \( i \) 연결 리스트의 길이만 반환하면 된다. i가 \( d_i \) 개 정점 만큼 연결되어 있다면 정점 i의 연결 리스트에서 \( d_i \) 개의 노드를 세므로 시간 복잡도는 \( O(d_i) \)이다.
■ 정점의 인접 정점을 구하는 연산은
- 인접 행렬의 경우 행 또는 열의 모든 요소를 조사해야 하므로 시간 복잡도는 \( O(n) \)이다.
- 인접 리스트는 정점 i에 간선으로 직접 연결된 모든 정점을 구하는 연산도 정점 i 연결 리스트에서 \( d_i \) 개 노드를 방문해야 하므로 \( O(d_i) \)이다.
■ 그래프의 모든 간선의 수를 계산하는 연산은
- 인접 행렬의 경우 인접 행렬 전체를 조사해야 하므로 \( n \times n \), \( n^2 \) 번의 조사가 필요하다. 따라서 시간 복잡도는 \( O(n^2) \)
- 인접 리스트는 정점 연결 리스트의 헤더 노드 \( n \) 개를 포함해 모든 인접 리스트를 조사해야 한다. 간선의 수가 \( e \) 개라면 헤더 노드를 제외한 각 정점 연결 리스트의 인접 정점을 가리키는 화살표는 \( e \) 개이므로 \( O(n + e) \)의 시간 복잡도를 갖게 된다.
5. 그래프 구현
5.1 파이썬을 이용한 인접 행렬 구현
■ 파이썬 리스트를 사용하면 정점과의 관계를 표현하는 인접 행렬 구현은 간단하다. 각 정점 간의 간선이 존재하면 1, 그렇지 않은 경우 0의 값을 가지는 2차원 배열만 만들면 되기 때문이다.
■ 단, 주의할 점은 인접 행렬의 행과 열의 순서가 정점의 순서와 정확히 일치해야 한다.
■ 예를 들어 다음과 같이 정점 A, B, C, D를 갖는 무방향 그래프가 있을 때
정점 A, B, C, D 순서대로 index = 0, 1, 2, 3 이라 하자. 이를 파이썬 2차원 배열을 사용해 인접 행렬로 나타내면 다음과 같다.
vertex = ['A', 'B', 'C', 'D']
adj_matrix = [[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 0],
[0, 1, 0, 0]]
import numpy as np
adj_matrix = np.array(
[[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 0],
[0, 1, 0, 0]]
)
adj_matrix.shape
```#결과#```
(4, 4)
````````````■ 가중치 그래프를 인접 행렬로 표현한다면 인접 행렬에는 '1'이 아닌 가중치, '0'에는 None을 넣으면 된다.
vertex = ['A', 'B', 'C', 'D']
adj_matrix_2 = [[0, 100, 10, 0],
[100, 0, 1000, 10000],
[10, 1000, 0, 0],
[0, 10000, 0, 0]]
5.2 파이썬을 이용한 인접 리스트 구현
■ 파이썬의 리스트, 튜플, 딕셔너리, 집합 등 다양한 방법으로 인접 리스트를 표현할 수 있다.
■ 연결 리스트로도 표현할 수 있지만, 인접 리스트 구현 역시 많은 자료형 중에서 리스트를 사용하는 것이 가장 간단하다.
vertex_2 = ['A', 'B', 'C', 'D', 'E']
adj_list = [[1, 2], # A의 인접 정점 인덱스
[0, 2, 3], # B의 ''
[0, 1], # C의 ''
[1], # D의 ''
[]] # E의 ''이렇게 인덱스로 표현하면 관계를 바로 파악하기 어렵기 때문에 각 정점을 직접적으로 나타내도 된다. 예를 들어 A의 인접 정점 인덱스 [1, 2] 대신 ['B', 'C']
■ 튜플로 구현할 경우, 튜플의 특성 때문에 추후 정점이나 간선의 삽입, 삭제가 불가능 하다는 점이 있다. 단, 추후 변경이 필요 없는 경우 리스트보다 튜플을 사용하는 것이 더 효율적이다.
■ 또한, 다음과 같이 정점과 그 정점의 인접 리스트를 묶어 그래프의 모든 관계를 나타낼 수 있다.
## 리스트
graph_list = [
['A', ['B','C']],
['B', ['A', 'C', 'D']],
['C', ['A','B']],
['D', ['B']]
]
graph_list
```#결과#```
[['A', ['B', 'C']], ['B', ['A', 'C', 'D']], ['C', ['A', 'B']], ['D', ['B']]]
````````````
## 튜플
graph_tuple = [
('A', ['B','C']),
('B', ['A', 'C', 'D']),
('C', ['A','B']),
('D', ['B'])
]
graph_tuple
```#결과#```
[('A', ['B', 'C']), ('B', ['A', 'C', 'D']), ('C', ['A', 'B']), ('D', ['B'])]
````````````
B_vertex, D_vertex = graph_tuple[1][0], graph_tuple[-1][0]
print(B_vertex); print(D_vertex)
```#결과#```
B
D
````````````
A_edge, C_edge = graph_tuple[0][1], graph_tuple[2][1]
print(A_edge); print(C_edge); # A와 C의 인접 정점
```#결과#```
['B', 'C']
['A', 'B']
````````````■ 그래프는 선형 자료구조가 아니기 때문에 정점들의 순서는 의미가 없다. 따라서 딕셔너리나 집합을 이용해서 인접 리스트로 표현할 수 있다.
## 딕셔너리
graph_dict = {
'A' : ['B','C'],
'B' : ['A', 'C', 'D'],
'C' : ['A','B'],
'D' : ['B']
}
graph_dict
```#결과#```
{'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B'], 'D': ['B']}
````````````
print(graph_dict['A']) # A의 인접 정점
print(graph_dict.get('B')) # B의 인접 정점
```#결과#```
['B', 'C']
['A', 'C', 'D']
`````````````■ 또한 인접 정점을 나타낼 때 반드시 리스트 형태일 필요는 없다. 인접 정점들 사이에 별도의 순서가 필요하지 않으며 어떤 정점들이 인접 정점인지가 중요하기 때문이다. 따라서 인접 리스트를 다음과 같이 집합으로 표현할 수 있다.
## 집합
graph_dict_set = {
'A' : set(['B','C']),
'B' : set(['A', 'C', 'D']),
'C' : set(['A','B']),
'D' : set(['B'])
}
graph_dict_set
```#결과#```
{'A': {'B', 'C'}, 'B': {'A', 'C', 'D'}, 'C': {'A', 'B'}, 'D': {'B'}}
````````````
# C의 인접 정점
for v in graph_dict_set['C']:
print(v)
```#결과#```
A
B
````````````■ 그리고 만약, 인접 정점 리스트의 변경이 필요하지 않는 경우 튜플을 사용해 인접 정점 리스트를 만드는 것이 적합하다.
6. 그래프의 탐색
■ 그래프 탐색은 가장 기본적인 연산으로 시작 정점부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 연산이다.
■ 기본적인 탐색 방법으로 깊이 우선 탐색과 너비 우선 탐색이 있다.
6.1 깊이 우선 탐색(Depth First Search, DFS)
■ 깊이 우선 탐색은 한 방향으로 끝까지 가다가 더 이상 이동할 수 없으면 가장 가까운 분기 지점으로 돌아와서 다른 방향으로 다시 깊이 우선 탐색을 진행한다.
■ 따라서 재귀적인 형태로 구현하는 것이 적합하며, 재귀를 사용할 수 없는 경우 스택을 이용하면 된다.
■ 스택은 마지막에 추가된 항목이 먼저 제거되는 후입선출 구조이다. DFS에서 더 이상 한 방향으로 탐색할 수 없을 때, 다시 가장 최근에 탐색한 노드로 돌아가야 하는데, 스택의 특성이 이 DFS의 동작 방식과 일치한다.
■ 예를 들어 다음과 같은 그래프가 있을 때, 스택을 사용하면
- 1) 스택에 시작 노드 A를 삽입한다. # 스택 상태: [A]
- 2) 스택에서 A를 꺼내 방문한다. # 스택 상태: [ ], 방문 순서: A
- 3) 그다음, A의 인접 노드 B를 스택에 추가한다. # 스택 상태: [B], 방문 순서: A
- 4) 스택에서 B를 꺼내 방문한다. # 스택 상태: [ ], 방문 순서: A \( \rightarrow \) B
- 5) B의 인접 노드 C와 D를 D, C 순으로 스택에 추가한다. # 스택 상태: [D, C], 방문 순서: A \( \rightarrow \) B
- 6) 스택이므로 마지막에 추가된 C가 먼저 나가게 된다. 즉, 스택에서 C를 꺼내 방문한다. # 스택 상태: [D], 방문 순서: A \( \rightarrow \) B \( \rightarrow \) C
- 7) 그다음, C의 인접 노드가 없으므로 스택에서 D를 꺼내 방문한다. # 스택 상태: [ ], 방문 순서: A \( \rightarrow \) B \( \rightarrow \) C \( \rightarrow \) D
- 8) D의 인접 노드 E를 스택에 추가한다. # 스택 상태: [E], 방문 순서: A \( \rightarrow \) B \( \rightarrow \) C \( \rightarrow \) D
- 9) 스택에서 E를 꺼내 방문한다. # 스택 상태: [ ], 방문 순서: A \( \rightarrow \) B \( \rightarrow \) C \( \rightarrow \) D \( \rightarrow \) E
- 10) E의 인접 노드가 없고, 스택이 비었으므로 탐색을 종료한다.
■ 이렇게 그래프의 탐색 과정은 한 번 방문했던 정점은 다시 탐색하지 않아야 하므로 이미 방문한 정점을 저장할 집합 또는 리스트가 필요하다.
- 집합을 사용할 경우 차집합으로 현재 정점의 인접 정점 집합에서 방문한 정점의 집합을 빼면, 아직 방문하지 않은 정점들을 추려낼 수 있다.
■ 예를 들어 다음과 같은 그래프를 정점 'A'에서부터 깊이 우선 탐색을 한다면
- 먼저 A를 방문하고 A의 인접 정점을 방문한다. A 방문 후 C를 방문한다면 다시 C의 인접 정점 중 방문하지 않은 정점을 방문한다. 따라서 C에서는 D나 E를 방문할 수 있다.
- C에서 D를 방문한다면, D에서는 B나 F를 방문할 수 있다. 만약 C \( \rightarrow \) D \( \rightarrow \) F 순으로 방문한다면, 더 이상 F에서 방문할 정점이 없으므로 더 방문할 수 있는 방향이 있을 때까지 온 순서대로 되돌아간다.
D, C, A 순으로 되돌아 가면 A에서 가지 않은 B가 있으니 B를 방문한다.
- 이제 B에서 더 방문할 수 있는 정점이 없으니 다시 방문할 수 있는 정점이 나올 때까지 B로 온 B, A, C 순으로 되돌아가고 C에서 E로, 더 방문할 수 있는 방향이 있으므로
- E에서 G, H 순으로 정점을 방문하면 H에서 더 방문할 수 있는 정점이 없으니 다시 온 순서대로 되돌아가 방문할 수 있는 정점을 찾지만, 모든 정점을 한 번씩 방문했으므로 더 이상 방문할 정점이 없다. 즉, 탐색을 완료한 것이다.
def DFS(graph, start, visited = set(), path = []): # path는 방문 경로를 기록할 리스트
if start not in visited:
print(f'탐색 시작 정점: {start}')
visited.add(start)
path.append(start)
print(f'방문한 정점: {visited}')
print(f'현재 정점의 인접 정점{graph[start]}')
nbr = graph[start] - visited # graph[start]는 정점 start의 인접 정점. 따라서 nbr은 아직 방문하지 않은 인접 정점
print(f'아직 방문하지 않은 정점: {nbr}\n')
for v in nbr:
DFS(graph, v, visited, path)graph = {
'A':{'B','C'},
'B':{'A','D'},
'C':{'A','D','E'},
'D':{'B','C','F'},
'E':{'C','G','H'},
'F':{'D'},
'G':{'E','H'},
'H':{'E','G'}
}
path = []
DFS(graph, 'A', path = path)
print(f'방문 경로: '+' -> '.join(path))
```#결과#```
탐색 시작 정점: A
방문한 정점: {'A'}
현재 정점의 인접 정점{'C', 'B'}
아직 방문하지 않은 정점: {'C', 'B'}
탐색 시작 정점: C
방문한 정점: {'A', 'C'}
현재 정점의 인접 정점{'A', 'D', 'E'}
아직 방문하지 않은 정점: {'D', 'E'}
탐색 시작 정점: D
방문한 정점: {'A', 'D', 'C'}
현재 정점의 인접 정점{'F', 'C', 'B'}
아직 방문하지 않은 정점: {'F', 'B'}
탐색 시작 정점: F
방문한 정점: {'A', 'D', 'F', 'C'}
현재 정점의 인접 정점{'D'}
아직 방문하지 않은 정점: set()
탐색 시작 정점: B
방문한 정점: {'C', 'B', 'F', 'D', 'A'}
현재 정점의 인접 정점{'A', 'D'}
아직 방문하지 않은 정점: set()
탐색 시작 정점: E
방문한 정점: {'E', 'C', 'B', 'F', 'D', 'A'}
현재 정점의 인접 정점{'H', 'C', 'G'}
아직 방문하지 않은 정점: {'H', 'G'}
탐색 시작 정점: H
방문한 정점: {'E', 'C', 'B', 'F', 'D', 'H', 'A'}
현재 정점의 인접 정점{'E', 'G'}
아직 방문하지 않은 정점: {'G'}
탐색 시작 정점: G
방문한 정점: {'E', 'C', 'B', 'F', 'D', 'H', 'A', 'G'}
현재 정점의 인접 정점{'E', 'H'}
아직 방문하지 않은 정점: set()
방문 경로: A -> C -> D -> F -> B -> E -> H -> G
``````````````■ 깊이 우선 탐색은 탐색 그리고 다시 되돌아 가는 과정에서 그래프의 모든 간선을 조사한다. 따라서 노드가 \( n \)개이고 간선이 \( e \)개라면, 인접 리스트로 표현할 경우 탐색 연산의 시간 복잡도는 \( O(n + e) \)이고, 인접 행렬로 표현할 경우 \( O(n^2) \)이다.
6.2 너비 우선 탐색(Breadth First Search, BFS)
■ 너비 우선 탐색은 시작 정점에서부터 인접한 모든 정점을 탐색한 후, 그 다음 레벨의 정점들을 차례로 탐색하는 방법으로 깊이 보다는 너비를 우선하여 탐색하기 때문에 시작 정점으로부터 가까운 정점들이 먼저 모두 탐색하고 시작 정점으로부터 멀리 떨어져 있는 정점들을 탐색한다.
■ 예를 들어 다음과 같은 그래프가 있을 때, 너비 우선 탐색을 할 경우
방문 경로는 A \( \rightarrow \) B \( \rightarrow \) C \( \rightarrow \) D \( \rightarrow \) E 가 된다.
■ 이렇게 너비 우선 탐색은 정점들을 발견한 순서대로 저장하고, 그 순서대로 처리하기 때문에 선입선출 특성을 가진 '큐'가 사용된다.
■ 큐는 먼저 들어온 순서대로 나가는 구조이므로, 발견한 정점을 먼저 방문하는 BFS에 적합한 자료구조이다.
■ 큐를 사용할 경우, 정점을 방문할 때마다 큐에 인접 정점을 삽입한다. 더 이상 방문할 인접 정점이 없으면, 큐의 맨 앞부터 정점을 꺼내 차례대로 방문한다. 즉 큐를 사용할 경우 너비 우선 탐색은 큐가 공백이 될 때까지 탐색을 진행한다.
■ 예를 들어 다음과 같은 그래프를 정점 'A'에서부터 너비 우선 탐색을 한다면
- 시작 정점이 A라면 초기 큐에는 A가 저장되어 있다. # 큐 상태: [A]
- 그다음, A를 꺼내서 A의 인접 정점을 방문한다. 이때 B와 C 중 무엇을 먼저 탐색하든지 상관없다. # 큐 상태: [C, B]
- 큐에 들어 있는 정점 순서대로 탐색해야 하므로 C부터 꺼내야 한다.
- C를 거내고 C의 인접 정점들을 방문한다. # 큐 상태 [B, D, E]
- 큐에 들어 있는 순서대로 B를 꺼내고 B의 인접 정점들을 방문한다. B의 인접 정점은 A와 D인데, A와 D는 이미 큐에 들어 있었거나 들어가 있는 정점들이다. 즉, 큐에 삽입할 새로운 정점은 없다. # 큐 상태 [D, E]
- 그다음 D를 꺼내고 D의 인접 정점들을 방문한다. D의 인접 정점은 C와 F. # 큐 상태 [E, F]
- 그다음 E를 꺼내고 E의 인접 정점들을 방문한다. D의 인접 정점은 G와 H. # 큐 상태 [F, G, H]
- 그다음 F를 꺼내는데 F의 인접 정점들을 모두 방문했으므로 더 이상 삽입할 정점이 없다. # 큐 상태 [G, H]
- 큐에 남아 있는 G와 H도 F와 마찬가지이다. # 큐 상태 [ ]
- 따라서 큐는 공백 상태가 되므로 탐색 완료이다. 방문 순서는 큐에서 꺼낸 A, C, B, D, E, F, G, H 순서가 된다.
■ 너비 우선 탐색을 구현하기 위해 큐 모듈이나 원형 큐를 사용할 수 있다. 단, 큐를 사용할 경우 전단과 후단에서 삽입과 삭제 연산을 분담해서 진행하기 때문에 효율성이 떨어진다.
■ 따라서 큐의 전단과 후단 모두에서 삽입, 삭제가 가능한 큐인 덱을 큐처럼 사용한다면 너비 우선 탐색을 효율적으로 진행할 수 있다.
덱(Deque)
1. 덱■ 덱은 double ended queue의 줄임말로, 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐이다.■ 즉, 덱의 구조는 다음 그림과 같이, 큐이지만 스택과 큐의 성질을 모두 가지고 있
hyeon-jae.tistory.com
■ 파이썬 collections 모듈은 deque를 지원하는데, 일반적인 리스트는 양 끝의 요소에 접근해 삽입, 삭제 연산을 수행하여 \( O(n) \)의 시간 복잡도를 가지지만, deque는 \( O(1) \)로 접근이 가능하다.
■ 단, 주의할 점은 deque 는 전단, 후단아 아닌 왼쪽, 오른쪽 개념을 사용한다.
■ deque의 삽입, 삭제 함수로 append( ) / pop( ), appendleft( ) / popleft( )가 있는데
- deque.append(item)은 덱의 오른쪽 끝에 item을 삽입하고
- deque.pop( )은 덱의 오른쪽 끝의 요소를 가져오는 동시에 요소를 덱에서 삭제한다.
- deque.appendleft(item)은 덱의 왼쪽 끝에 item을 삽입.
- deque.popleft( )는 덱의 왼쪽 끝의 요소를 가져오는 동시에 요소를 덱에서 삭제한다.
■ 덱을 큐처럼 사용하기 위해선 우측 삽입 append ( ) (= 후단), 좌측 삭제 popleft( ) (= 전단)를 사용하면 된다.
from collections import deque
def BFS(graph, start, path = []): # path는 방문 경로를 기록할 리스트
visited = set([start]) # 초기 start만 방문한 정점
queue = deque([start]) # 덱 객체 생성. 덱을 큐처럼 사용
path.append(start) # 우측 삽입
while queue: # popleft 함수를 사용하기 때문에 while queue의 의미는 덱이 공백 상태가 될 때까지 반복한다는 의미이다.
vertex = queue.popleft() # 좌측 삭제. 삭제하는 요소를 vertex에 반환.
nbr = graph[vertex] - visited
for v in nbr:
visited.add(v) # nbr에 있는 정점들 방문
path.append(v)
queue.append(v) # 우측 삽입path = []
BFS(graph, 'A', path = path)
print(f'방문 경로: '+' -> '.join(path))
```#결과#```
방문 경로: A -> C -> B -> E -> D -> G -> H -> F
```````````■ 너비 우선 탐색은 시작 정점으로부터 가장 가까운 정점 순으로 탐색을 진행한다. 이 거리가 \( d \)라면 ,먼저 거리가 \( d \)인 정점들을 모두 방문한 다음, \( d + 1 \) 거리에 있는 정점들을 모두 탐색한다.
- 트리를 예로 들면 이 거리는 트리의 레벨이라 생각하면 된다. level 1의 노드를 방문한 다음 level 2에 있는 모든 노드를 방문하고, 그다음 level 3, level 4, ... 순으로 각 레벨에 있는 모든 노드들을 방문한다.
■ 너비 우선 탐색도 인접 리스트로 표현되어 있으면 \( O(n + e) \), 인접 행렬로 표현되어 있으면 \( O(n^2) \) 시간만큼 탐색을 수행한다.
6.3 연결 성분(Connected Components) 검사
■ 연결 성분이란 최대로 연결된 부분 그래프를 의미하며, 연결 성분 검사는 최대로 연결된 부분 그래프들을 계산하는 연산이다.
■ 연결 성분을 찾기 위해서 DFS나 BFS를 이용한다.
- 임의의 정점에 DFS/BFS를 적용해서 연결되어 있는 모든 정점들을 방문한다.
- 단, 그래프의 형태가 connected graph가 아니면 한 번의 탐색으로 모든 정점들을 방문할 수 없으므로 DFS/BFS를 반복적으로 수행해야 한다.
- DFS/BFS 반복 횟수는 그래프 안에 있는 connected graph의 개수이다. 이 개수만큼 반복해야 전체 그래프에 있는 모든 정점들을 방문할 수 있기 때문이다.
■ 예를 들어 다음과 같이 G라는 그래프가 2개의 connected graph로 구성된 경우
graph G는 connected graph가 아니므로 한 번의 탐색만으로는 모든 정점들을 방문할 수 없다. 따라서 이 예에서는 graph G가 2개의 connected graph로 구성되어 있으므로 DFS나 BFS를 2번 실행해야 한다.
## DFS
def dfs_connected_component(graph):
visited = set() # 방문한 정점
components = [] # 부분 그래프들을 저장할 리스트
for vertex in graph: # 그래프의 모든 정점들에 대해
if vertex not in visited: # 아직 방문하지 않은 정점이 있다면
component = dfs_cc(graph, [], vertex, visited) # vertex와 연결된 모든 vertex 리스트를
components.append(component) # 부분 그래프들을 저장할 리스트에 추가
print(len(components)); print(components)
def dfs_cc(graph, component, vertex, visited):
if vertex not in visited:
visited.add(vertex)
component.append(vertex)
nbr = graph[vertex] - visited
for v in nbr:
dfs_cc(graph, component, v, visited)
return component## BFS
def bfs_connected_component(graph):
visited = set()
components = []
for vertex in graph:
if vertex not in visited:
component = bfs_cc(graph, vertex, visited)
components.append(component)
print(len(components)); print(components)
from collections import deque
def bfs_cc(graph, start, visited):
queue = deque([start]) # start는 시작 정점. deque([])으로 초기화
visited.add(start)
component = [start] # 연결 요소에 시작 정점을 추가
while queue:
vertex = queue.popleft()
nbr = graph[vertex] - visited
for v in nbr: # 인접 정점 중 아직 방문하지 않은 정점들을
visited.add(v)
component.append(v) # 연결 요소에 추가
queue.append(v)
return componentgraph2 = {
'A': {'B', 'C'},
'B': {'A', 'D'},
'C': {'A'},
'D': {'B'},
'E': {'F'},
'F': {'E'},
'G': set() # Single isolated vertex
}
dfs_connected_component(graph)
```#결과#```
1
[['A', 'C', 'D', 'F', 'B', 'E', 'H', 'G']]
````````````
dfs_connected_component(graph2)
```#결과#```
3
[['A', 'C', 'B', 'D'], ['E', 'F'], ['G']]
````````````
bfs_connected_component(graph)
```#결과#```
1
[['A', 'C', 'B', 'D', 'E', 'F', 'H', 'G']]
````````````
bfs_connected_component(graph2)
```#결과#```
3
[['A', 'C', 'B', 'D'], ['E', 'F'], ['G']]
````````````■ 첫 번째 graph에 DFS를 이용해 연결 성분을 검사하면
- 처음에는 정점 'A', visited는 공집합이며 component를 구하기 위해 dfs_cc 함수를 호출한다.
- dfs_cc에서 visited와 component에 vertex 'A'를 추가한다. nbr은 'A'의 인접 정점의 집합과 visited 집합에 대한 차집합이므로 nbr은 정점 'B', 'C'이다.
- 정점 'C'부터 'C'와 연결된 정점들을 방문하기 위해 다시 dfs_cc 함수를 호출한다. # 현재 component: ['A'], vertex: 'C', visited = {'A'D;
- 'C'도 visited에 없으므로 'c'를 visited와 component에 삽입한다. 'C'의 nbr을 구하면 'D', 'E'이고 다시 'D'에 대해 'D'의 인접 접 정점들을 방문하기 위해 dfs_cc 함수를 호출한다.
- graph는 connected_graph이기 때문에 모든 정점들을 방문해서 component 리스트에 모든 정점들을 모두 채우고 더 이상 추가할 정점이 있는지 없는지 확인할 때까지 dfs_cc가 재귀적으로 호출된다.
- component에 graph의 모든 정점들이 채워지면, components에 component를 저장하고 다시 정점 'B'부터 dfs_cc를 호출하여 'B'의 component를 탐색한다. # 현재 vertex: 'B', component: ['A', 'C', 'D', 'F', 'B', 'E', 'G', 'H']
- 이 graph는 connected graph이므로 이미 한 번의 연결 성분 검사만으로 components를 구했기 때문에 for vertex in graph: if vertex not in visited: component = dfs_cc( ) 과정에서 정점 'B'부터 마지막 정점까지 더 이상 components에 저장될 component가 없다.
■ BFS를 이용해 연결 성분을 검사하는 방법도 이와 같은 구조를 이용해 연결 성분을 검사한다.
7. 신장 트리(Spanning Tree)
■ 신장 트리는 '그래프 내의 모든 정점을 포함하는 트리'이다.
- 신장 트리는 트리이기 때문에 사이클이 없어야 하고
- 모든 정점들이 연결되어 있어야 한다. 즉 정점의 개수가 \( n \) 개라면, \( n - 1 \) 개의 간선이 필요하다.
■ 즉, 신장 트리는 사이클 없이 연결 그래프의 모든 정점을 포함하는 부분 그래프이다. 따라서 하나의 그래프에 여러 개의 신장 트리가 존재할 수 있으며, 이런 신장 트리를 찾기 위해 DFS나 BFS를 이용할 수 있다.
■ 예를 들어 다음과 같은 사이클이 존재하는 그래프가 있을 때, DFS와 BFS를 이용해서 신장 트리를 찾을 수 있다.
이 외에도 다른 형태의 신장 트리를 찾을 수 있다.
■ 이렇게 신장 트리는 DFS나 BFS 도중에 사용된 간선들만 모으면 된다.
def bfs_spanning_tree(graph, start):
visited = set([start]) # 초기는 start만 방문한 정점
queue = deque([start]) # 덱 초기화
while queue:
vertex = queue.popleft()
nbr = graph[vertex] - visited
for v in nbr:
print(f'{(vertex, v)}', end = ' ')
visited.add(v)
queue.append(v)
bfs_spanning_tree(graph, 'A')
```#결과#```
('A', 'C') ('A', 'B') ('C', 'D') ('C', 'E') ('D', 'F') ('E', 'H') ('E', 'G')
````````````
8. 위상 정렬(Topological Sort)
■ 위상 정렬은 '선형 순서에 맞게 방향 그래프의 모든 정점을 나열한 것'을 말한다.
■ 만약, 그래프에 사이클이 존재한다면 위상 정렬이 불가능하다.
■ 예를 들어 다음과 같은 순서를 가지는 그래프가 있을 때
- A와 B는 먼저 선행되어야 하는 정점이 없지만 C는 A, E는 B가 먼저 선행되어야 하고 D는 A, B, C가 F는 C, D, E가 먼저 선행되어야 한다.
- 예를 들어 정점 A와 C에는 간선 <A, C>가 있는데, 방향 그래프이므로 <A, C>는 '정점 A는 정점 C를 선행한다'고 관계를 해석할 수 있다. D 역시 간선 <A, D>, <B, D>, <C, D>가 있으므로 '정점 A는 정점 D를 선행한다', '정점 B는 정점 D를 선행한다', '정점 C는 정점 D를 선행한다'. 따라서 'D'는 A, B, C가 선행되야 한다는 관계를 간선으로 파악할 수 있다.
- 따라서 <A, B, C, D, E, F>, <A, C, B, E, D, F>, ... 등은 위상 정렬로 가능하나 <E, A, C, B, D, E, F>는 <B, E>라는 선행 순서를 지키지 않는 경우로서 위상 정렬 불가능하다.
■ 방향 그래프의 위상 알고리즘은 진입 차수를 이용한다.
- 먼저, 진입 차수가 0인 선행 정점이 없는 정점을 하나 선택하고, 선택된 정점과 연결된 간선을 모두 제거한다. 이는 해당 정점이 수행되었음을 의미한다.
- 간선이 삭제되면, 삭제된 간선과 연결된 정점들의 진입 차수도 변경되어야 한다.
- 이 과정을 반복하면 선후수 관계에 맞게 모든 정점들이 삭제된다. 정점들이 삭제되는 순서가 위상 순서가 되는 것이다.
■ 만약, 삭제를 진행하는 과정에서 그래프에 남아 있는 정점들 중 진입 차수가 0인 정점이 하나도 없다면, 이는 그래프에 사이클이 존재하기 때문이다. 따라서 위상 정렬은 불가능하다.
■ 예를 들어 다음과 같이 B와 E, C와 F에 사이클이 존재한다면, 진입 차수가 0인 정점 A를 삭제하여 남아 있는 정점들이 진입 차수가 변경되었을 때, 사이클이 존재하여 남은 정점들 중에 진입 차수가 0인 정점이 존재하지 않는다.
■ 반면 위상 정렬이 가능한 예시의 과정을 보면 다음과 같이 선후수 관계에 맞게 위상 정렬이 되는 것을 볼 수 있다.
def topological_sort(graph, vertex):
n = len(vertex)
in_degree = [0] * n # 각 정점의 진입 차수 리스트
# 모든 정점의 진입 차수 계산
for i in range(n):
for j in range(n):
if graph[i][j] > 0: # 간선이 존재하는지 확인
in_degree[j] += 1 # 각 정점의 진입 차수 기록
# result = []
zero_in_degree = [] # 진입 차수가 0인 정점을 저장할 리스트
# 진입 차수가 0인 정점은 zero_in_degree에 저장
for i in range(n):
if in_degree[i] == 0:
zero_in_degree.append(i)
# 진입 차수가 0인 정점들을 처리
while len(zero_in_degree) > 0:
v = zero_in_degree.pop() # zero_in_degree에서 진입 차수가 0인 정점 반환 & 제거
# result.append(vertex[v])
# 인접한 정점들의 진입 차수 감소
for u in range(n):
if graph[v][u] > 0: # 간선이 존재하는지 확인
in_degree[u] -= 1 # 정점 v에서 정점 u로의 간선을 제거하므로, 정점 u의 진입 차수를 1 감소시킴
if in_degree[u] == 0: # 간선을 제거해서 정점 u의 진입 차수가 0이면
zero_in_degree.append(u) # 진입 차수가 0인 정점을 저장한 리스트에 추가
# print('위상 정렬 과정: ' + ' -> '.join(result))vertex = ['A', 'B', 'C', 'D', 'E', 'F']
# 그래프를 인접 행렬로 표현
graph = [[0, 0, 1, 1, 0, 0], # A7
[0, 0, 0, 1, 1, 0], # B
[0, 0, 0, 1, 0, 1], # C
[0, 0, 0, 0, 0 ,1], # D
[0, 0, 0, 0, 0, 1], # E
[0, 0, 0, 0, 0, 0]] # Ftopological_sort(graph, vertex)
```#결과#```
위상 정렬 과정: B -> E -> A -> C -> D -> F
````````````
- graph와 vertex에 대한 정보를 받아 모든 정점의 진입 차수를 저장한다.
- 이 예에서는 진입 차수 리스트가 정점의 수에 맞춰 [0, 0, 0, 0, 0, 0]으로 초기화 된다. 여기에 그래프를 순회하면서 각 정점의 진입 차수를 기록하면 A, B, C, D, E, F의 진입 차수 in-degree 리스트는 [0, 0, 1, 3, 1, 3]이 저장된다.
- 이 리스트 값이 0인 위치는 진입 차수가 0인, 삭제할 (선행) 노드의 위치를 가리킨다. 초기 zero_in_degree에는 0, 1 즉 정점 A, B가 저장된다.
- 따라서 진입 차수가 0인 A, B 중 하나를 삭제하고, 삭제 후 삭제한 노드와 연결된 정점들의 진입 차수를 갱신해야 한다. 따라서 다시 한 번 모든 정점들에 대해 순회해야 한다. 이 과정을 반복해서 모든 정점들을 삭제했을 때, 삭제되는 순서가 위상 순서가 된다.
