Graphs and Graph Traversals — 그래프 표현과 DFS, BFS, 강연결요소

항공 노선, 순서도, 컴퓨터 네트워크, “$x$는 $y$의 진약수다” 같은 이항 관계. 이들은 전부 개체와 개체 사이의 연결이라는 같은 구조를 가진다. 이 구조를 추상화한 것이 그래프(graph)다. 그래프 위에서 도는 대부분의 알고리즘은 결국 정점과 간선을 빠짐없이 한 번씩 훑는 일로 환원되고, 그 훑는 방식이 DFS와 BFS다. 이 글은 그래프의 정의와 표현에서 출발해 두 순회 전략, 그리고 그 응용으로 강연결요소(SCC)를 찾는 알고리즘까지 다룬다.

그래프의 정의

방향 그래프(Directed Graph)

방향 그래프, 줄여서 digraph는 쌍 $G = (V, E)$다.

• $V$는 정점(vertex, 노드(node)라고도 한다)의 집합이다.
• $E$는 $V$ 원소들의 순서 있는 쌍(ordered pair) 의 집합이다. 즉 간선에 방향이 있다.

$E$의 원소를 간선(edge), 방향 간선(directed edge), 또는 호(arc)라고 부른다. 방향 간선 $(v, w)$에서 $v$를 꼬리(tail), $w$를 머리(head)라 하고, 다이어그램에서는 화살표 $v \rightarrow w$로 그린다. 간단히 $vw$로도 쓴다. 표기는 (origin, destination), (start, end), (tail, head) 등 문맥에 따라 다양하게 쓰인다.

자기 자신으로 가는 간선 $(v, v)$를 자기 루프(self-loop) 라 하며, 방향 그래프에서는 허용된다.

차수(degree). 정점 $v$에 대해 들어오는 간선 수를 진입 차수 $\text{indeg}(v)$, 나가는 간선 수를 진출 차수 $\text{outdeg}(v)$라 한다. 전체 차수는 둘의 합이다.

예를 들어 들어오는 간선 1개, 나가는 간선 3개인 정점은 $\text{indeg}(v) = 1$, $\text{outdeg}(v) = 3$, $\deg(v) = 4$다. 자기 루프는 차수를 2로 센다(들어오면서 동시에 나가므로).

무방향 그래프(Undirected Graph)

무방향 그래프도 쌍 $G = (V, E)$지만, $E$가 서로 다른 두 정점의 순서 없는 쌍(unordered pair) 의 집합이라는 점이 다르다. 각 간선은 정점 두 개를 원소로 갖는 부분집합으로 볼 수 있고, ${v, w}$로 표기한다. 다이어그램에서는 화살표 없는 선 $v - w$로 그린다.

순서가 없으므로 $vw$와 $wv$는 같은 간선이고, 중복 원소가 없어야 하므로 무방향 그래프에는 자기 루프가 없다.

두 개념을 구분해 둘 필요가 있다.

• incident: 정점과 간선이 맞닿아 있는 관계. 간선 $vw$는 정점 $v$, $w$에 incident하다.
• adjacent: 두 정점이 하나의 간선으로 연결된 관계. $v$와 $w$가 인접(adjacent)하다.

가중 그래프(Weighted Graph)

가중 그래프는 삼중쌍 $(V, E, W)$다. $(V, E)$는 (방향이든 무방향이든) 그래프이고, $W$는 $E$에서 실수 $\mathbb{R}$로 가는 함수다. 간선 $e$에 대해 $W(e)$를 $e$의 가중치(weight)라 한다. 항공 노선에서 도시 간 거리, 네트워크에서 링크 비용 등이 가중치로 들어간다.

그래프 표현

인접 행렬(Adjacency Matrix)

$n \times n$ 행렬 $A$로 표현한다. 무방향 그래프에서는 $v_i$와 $v_j$가 인접하면 $A[i][j] = 1$, 아니면 $0$이다. 무방향이므로 행렬은 주대각선에 대해 대칭이다.

예를 들어 정점 7개짜리 무방향 그래프

1 — 2        간선: {1,2} {1,3} {2,3} {2,4}
|  X |              {3,4} {3,6} {4,6}
3 — 4              {5,6} {6,7}
5 — 6 — 7

의 인접 행렬은 다음과 같다.

가중 방향 그래프라면 1/0 대신 가중치를 넣는다. 이때 자기 자신은 $0$, 간선이 없는 칸은 $\infty$로 둔다(최단 경로 계산 등에서 “도달 비용 무한”을 뜻한다). 방향 그래프이므로 더 이상 대칭이 아니고, $A[i][j]$는 $v_i$에서 $v_j$로 가는 나가는 간선(outgoing edge) 의 가중치를 의미한다.

인접 리스트(Adjacency List)

정점마다 인접한 정점들의 연결 리스트를 두고, 그 리스트들을 배열로 묶는다. 위 무방향 그래프의 인접 리스트는 이렇게 된다.

adjVertices
1 → 2 → 3
2 → 1 → 3 → 4
3 → 1 → 2 → 4 → 6
4 → 2 → 3 → 6
5 → 6
6 → 3 → 4 → 5 → 7
7 → 6

가중 방향 그래프라면 리스트 노드에 (인접 정점, 가중치) 쌍을 저장하고, 방향 그래프이므로 나가는 간선만 리스트에 담는다.

복잡도 비교

두 표현은 연산별로 비용이 다르다. 무방향 그래프 기준으로 정리하면 다음과 같다.

어느 쪽이 유리한지는 그래프의 밀도에 달려 있다.

• 밀집(dense) 그래프: 간선 수 $m$이 $\Theta(n^2)$에 가까운 경우. 인접 행렬이 유리하다.
• 희소(sparse) 그래프: 간선 수 $m$이 $O(n)$에 가까운 경우. 인접 리스트가 유리하다.

밀집/희소의 경계는 엄밀한 정의라기보다 주관적인 구분이다. 무방향 그래프의 연결성과 간선 수 사이에는 다음 관계가 있다.

• 연결(connected) 그래프: $m \geq n - 1$
• 트리(tree): $m = n - 1$
• 숲(forest): $m \leq n - 1$

더 많은 정의

빈 그래프 $G = (\emptyset, \emptyset)$는 모든 그래프의 부분그래프다. 아래 정의는 단순 그래프(self-loop·중복 간선 없는 그래프)를 전제로 한다.

• 부분그래프(subgraph): $V’ \subseteq V$, $E’ \subseteq E$를 만족하는 $G’ = (V’, E’)$.
• 완전 그래프(complete graph): 모든 정점 쌍 사이에 간선이 존재하는 그래프. 간선 수는 $m = \dfrac{n(n-1)}{2}$이고, $m \in O(n^2)$이므로 가장 밀집한 경우다.
• 인접 관계(adjacency relation): 두 정점이 하나의 간선으로 연결된 관계.

• 경로(path): 정점들의 나열 $P = \langle v_1, v_2, \dots, v_k \rangle$이며, 인접한 정점 사이에 간선이 있어야 한다. 경로 길이 $

  P

  $는 간선의 수다. 단순 경로(simple path) 는 정점이 모두 서로 다른 경로다. $v$에서 $w$로 가는 경로가 존재하면 $w$는 $v$로부터 도달 가능(reachable) 하다.

• 연결(connected) / 강연결(strongly connected): “어떤 조건을 만족해 그래프가 한 덩어리인가”를 나타낸다. connected는 무방향 그래프에, strongly connected는 방향 그래프에 쓰며, 모든 정점이 서로 도달 가능할 때 성립한다.
• 사이클(cycle) / 단순 사이클(simple cycle): 시작과 끝이 같은 경로. 사이클이 없으면 비순환(acyclic) 이다.
• 숲·자유 트리·루트 트리: 무방향 숲(undirected forest), 자유 트리(free tree, 루트가 지정되지 않은 무방향 트리), 루트 트리(rooted tree).
• 연결 요소(connected component): $G$의 극대(maximal) 연결 부분그래프. 더 이상 정점을 추가해 연결 상태를 유지할 수 없는 가장 큰 덩어리를 말한다.

그래프 순회

그래프 문제를 푸는 대부분의 알고리즘은 각 정점과 각 간선을 검사하거나 처리한다. 그 기반이 되는 두 순회 전략이 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이고, 둘 다 모든 정점과 간선을 정확히 한 번씩 방문하는 효율적인 방법을 제공한다. 그래프의 입력 크기가 $n + m$이고 순회도 정점과 간선을 한 번씩 보므로, 두 순회 모두 시간 복잡도는 다음과 같다.

깊이 우선 탐색(DFS)

방향 그래프에서의 DFS 전략은 이렇다.

1. 시작 정점을 고르고 거리 $d = 0$으로 둔다(예제에서는 key 값이 작은 쪽부터 접근한다고 가정).
2. 거리 $d$의 정점에서 나가는 간선 하나를 따라 인접한 거리 $d+1$ 정점으로 간다.
3. 다시 거리 $d+1$ 정점에서 간선 하나를 따라 $d+2$로 가고, 이를 반복한다.
4. 새 정점이 더 이상 없거나 막다른 길(dead end, 더 갈 곳 없는 finished 정점)에 도달하면 한 단계 백트랙(backtrack) 해서 다른 간선을 시도한다.
5. 최종적으로 시작 정점까지 백트랙하고 더 발견할 정점이 없으면 끝난다.

핵심은 “갈 수 있는 데까지 깊이 들어갔다가 막히면 되돌아온다”는 것이다.

정점과 간선의 상태

DFS 진행 중 정점은 세 가지 상태(색)를 가진다.

• unexplored / white: 아직 발견 전.
• visited / grey: 발견됐고 아직 처리 중(자손을 탐색 중).
• finished / black: 자손까지 모두 탐색을 마침.

간선도 상태를 가진다. 아직 안 본 간선은 unexplored, 처음 따라가 새 정점을 발견하면 discovery 간선, 따라갔더니 도착 정점이 이미 visited 상태면 back 간선이다.

DFS 트리와 간선 분류

DFS가 따라간 discovery 간선들만 모으면 DFS 트리가 된다. 방향 그래프의 모든 간선은 이 트리를 기준으로 네 종류로 분류된다.

예를 들어 시작 정점 $A$에서 DFS를 돌리면 방문 순서와 종료 순서가 각각 따로 기록된다. 어떤 그래프에서 방문(visited) 순서가 $A, B, C, D, F, E, G$이고 종료(finished) 순서가 $C, D, B, F, A, G, E$ 식으로 나오는데, 두 순서가 다르다는 점이 중요하다. 종료 순서는 뒤에서 강연결요소 알고리즘의 핵심 재료로 쓰인다.

너비 우선 탐색(BFS)

방향 그래프에서의 BFS 전략은 DFS와 거의 같은 문장으로 시작하지만 결정적으로 다르다.

1. 시작 정점을 고르고 $d = 0$으로 둔다.
2. 거리 $d$ 정점들에서 나가는 모든 간선을 검사해 인접한 거리 $d+1$ 정점을 전부 발견한다.
3. 그다음 거리 $d+1$ 정점들에서 나가는 모든 간선을 검사해 $d+2$ 정점을 발견하고, 이를 반복한다.
4. 새 정점이 더 이상 없으면 끝난다.

DFS가 “한 간선만 따라 깊이” 들어갔다면, BFS는 “한 거리의 정점을 전부” 처리하고 다음 거리로 넘어간다. 즉 시작 정점으로부터 거리(레벨) 순으로 정점을 방문한다. 이 동작을 구현하려면 먼저 발견한 정점을 먼저 처리하는 큐(queue) 가 필요하다.

거리 순으로 방문하기 때문에 BFS는 가중치 없는 그래프에서 최단 경로(shortest path) 를 계산할 수 있다. 각 정점에 자신을 발견한 정점(predecessor/parent)을 기록해 두면, 시작점에서 임의 정점까지의 최단 경로를 역추적할 수 있다. DFS와 달리 BFS는 finished 상태를 따로 표시할 필요가 없다.

예를 들어 정점 $A$에서 BFS를 시작하면 $d = 1$에서 $B, C, F$를 방문하고 $d = 2$에서 $D$를 방문하는 식으로, 큐에 A | B C F | D 처럼 거리 경계가 구분되어 쌓인다. predecessor 배열을 함께 채우면 그것이 곧 BFS 트리다.

강연결요소(Strongly Connected Components)

방향 그래프 $G$가 강연결(strongly connected) 이라는 것은, 임의의 두 정점 $v$, $w$에 대해 $v$에서 $w$로 가는 경로가 존재한다는 뜻이다. 강연결요소(SCC) 는 $G$의 극대 강연결 부분그래프다. 방향 그래프를 SCC 단위로 쪼개면 각 덩어리 안에서는 모든 정점이 서로 오갈 수 있다.

알고리즘 — 두 번의 DFS

인접 리스트로 표현된 그래프에서 SCC는 DFS를 두 번 돌려 찾는다(코사라주(Kosaraju) 알고리즘).

Phase 1. $G$에 대해 표준 DFS를 수행하면서, 정점이 finished될 때마다 스택에 넣는다. 이 단계는 finished 스택을 만드는 일이고 $O(n)$ 수준이다. 끝나면 스택의 top에는 가장 늦게 끝난 정점이 온다.

Phase 2. 전치 그래프(transpose graph) $G^T$에 대해 DFS를 수행한다. $G^T$는 원래 그래프의 모든 간선 방향을 뒤집은 그래프다. 탐색을 시작할 정점은 Phase 1에서 만든 스택을 pop해서 정한다. 한 번의 DFS로 도달되는 정점들이 하나의 SCC를 이루며, 그 SCC는 탐색을 시작한 정점의 이름으로 식별한다. 이 시작 정점을 리더(leader) 라 부른다.

전체 시간은 두 번의 DFS이므로 $O(n + m)$이다.

왜 두 단계로 나누는가

직관은 이렇다. Phase 1의 종료 순서(finished 스택)는 “가장 바깥 SCC(다른 SCC로 나가기만 하는 덩어리)”의 정점을 스택 위쪽에 모아 준다. 간선을 뒤집은 $G^T$에서 그 정점부터 탐색을 시작하면, 원래 그래프에서 나가기만 하던 방향이 막혀서 자기 SCC 안에서만 돌게 된다. 그 결과 한 번의 DFS가 정확히 하나의 SCC만 긁어낸다. 스택을 pop하며 이를 반복하면 그래프 전체가 SCC 단위로 분해된다.

예를 들어 정점 $A$~$G$짜리 그래프에서 Phase 1의 finished 스택이 (top에서 bottom 순으로) $E, G, A, F, B, D, C$로 쌓였다면, $G^T$에서 $E$부터 pop해 가며 DFS를 돌려 ${A, B, D, F}$, ${C}$, ${E, G}$ 같은 SCC들로 나뉘는 식이다. 각 정점에는 자신이 속한 SCC의 리더가 기록된다.