위상 정렬 — 선행 관계를 하나의 줄로 세운다

위상 정렬(topological sort)은 “이 작업을 하려면 저 작업을 먼저 끝내야 한다”는 선행 관계가 간선으로 표현된 비순환 방향 그래프(DAG, 11편에서 역방향 간선이 없는 방향 그래프로 정의했다)에서, 모든 선행 관계를 어기지 않는 하나의 순서로 정점을 나열하는 것이다. 대학 수강 신청의 선수 과목 관계, 빌드 시스템의 파일 의존성, 프로젝트 일정의 작업 순서가 모두 이 문제로 모델링된다.

쉽게 말하면: 화살표가 “먼저 해야 할 일 → 나중에 할 일”을 뜻할 때, 모든 화살표를 왼쪽에서 오른쪽으로만 그릴 수 있도록 정점을 한 줄로 세우는 것이 위상 정렬이다.

Kahn 알고리즘 — 진입차수가 0인 것부터 차례로 뺀다

Kahn 알고리즘은 각 정점의 진입차수(in-degree, 그 정점으로 들어오는 간선의 개수)를 계산해 두고, 진입차수가 0인 정점(더 이상 기다릴 선행 작업이 없는 정점)을 큐에 넣어 하나씩 꺼내며, 그 정점에서 나가는 간선을 모두 제거(그 간선이 가리키던 정점의 진입차수를 1씩 감소)하는 과정을 반복한다.

다음 DAG로 전 과정을 추적한다(A→B, A→C, B→D, C→D, C→F, D→E).

전체 처리 순서를 표로 정리한다.

위상 정렬 결과: A, B, C, D, F, E. 이 순서에서 모든 간선은 항상 “먼저 나온 정점 → 나중에 나온 정점” 방향으로만 존재한다는 것을 각 간선(A→B, A→C, B→D, C→D, C→F, D→E)에 직접 대입해 확인할 수 있다.

위상 정렬로 사이클을 판별한다

큐가 완전히 비었는데도 아직 결과에 추가되지 못한 정점이 남아 있다면, 그 남은 정점들은 서로 진입차수를 낮춰줄 수 없는 상태, 즉 사이클을 이루고 있어서 영원히 진입차수가 0이 될 수 없는 상황이다. 예를 들어 위 그래프에 D→A라는 간선을 추가하면 A의 초기 진입차수가 1이 되어 애초에 큐에 들어갈 수 없고, Kahn 알고리즘은 몇 개의 정점만 처리한 채 큐가 비어 종료된다. 처리된 정점의 개수가 전체 정점 개수보다 적다면, 그 방향 그래프에는 사이클이 있고 위상 정렬이 불가능하다고 판정한다.

자주 틀리는 점: “위상 정렬 결과는 항상 유일하다”고 착각하면 안 된다. 위 3단계에서 진입차수가 0인 정점이 D, F 두 개가 동시에 큐에 들어왔던 것처럼, 같은 시점에 진입차수가 0인 정점이 여러 개면 그중 어느 것을 먼저 처리해도 선행 관계를 어기지 않는 올바른 위상 정렬이 된다. 즉 하나의 DAG에 대해 여러 개의 올바른 위상 정렬 순서가 있을 수 있다.

Kahn 알고리즘의 복잡도

각 정점은 큐에 정확히 한 번 들어가고 한 번 나오므로 $O(V)$이고, 각 간선은 그 간선의 출발 정점을 처리할 때 정확히 한 번씩 확인되어 진입차수를 갱신하므로(11편에서 유도한 것과 같은 논리로) $O(E)$다. 따라서 전체 복잡도는 DFS·BFS와 똑같이 $O(V+E)$다.

최소 신장 트리(MST) — 모든 정점을 가장 싸게 연결한다

신장 트리(spanning tree)는 그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프이며, 정점이 $V$개인 연결 그래프의 신장 트리는 항상 정확히 $V-1$개의 간선을 가진다. 최소 신장 트리(Minimum Spanning Tree, MST)는 간선에 가중치가 있을 때, 그 가중치의 합이 가장 작은 신장 트리를 말한다. 도시들을 도로로 모두 연결하되 총 건설 비용을 최소화하는 문제가 대표적인 예다.

다음 가중치 그래프로 크루스칼과 프림 두 알고리즘을 각각 추적한다.

크루스칼 알고리즘 — 가장 싼 간선부터 사이클 없이 채운다

크루스칼(Kruskal) 알고리즘은 모든 간선을 가중치 오름차순으로 정렬한 뒤, 가장 싼 간선부터 순서대로 확인하면서 그 간선을 넣어도 사이클이 생기지 않으면 채택하고, 사이클이 생기면 버리는 방식이다. 사이클이 생기는지는 유니온-파인드(union-find, 서로소 집합 자료구조)로, 두 정점이 이미 같은 그룹(같은 신장 트리 조각)에 속해 있는지를 확인해 판정한다.

가중치 오름차순 간선 목록: B–C(1), A–C(2), D–E(2), E–F(3), A–B(4), B–D(5), D–F(6), C–D(8), C–E(10).

정점이 6개이므로 신장 트리는 간선 $V-1=5$개가 필요하다. 위 표에서 정확히 5개의 간선(B–C, A–C, D–E, E–F, B–D)이 채택되는 순간 전체 정점이 하나의 그룹으로 합쳐졌으므로 즉시 종료한다(4단계 A–B는 사이클을 만들어 버려졌다는 점이 “탐욕이지만 무조건 받아들이지는 않는다”는 것을 보여주는 핵심 지점이다).

프림 알고리즘 — 이미 연결된 덩어리에서 가장 싼 다리를 놓는다

프림(Prim) 알고리즘은 정렬된 전체 간선 목록을 보는 대신, 이미 신장 트리에 포함된 정점들의 집합(방문 집합)에서 바깥으로 나가는 간선 중 가장 싼 것을 매번 골라 그 간선이 가리키는 새 정점을 방문 집합에 추가하는 방식이다. A에서 시작해 추적한다.

두 알고리즘이 서로 다른 순서로 간선을 살펴봤지만(크루스칼은 전체 간선을 가중치순으로, 프림은 방문 집합 경계에서만) 최종적으로 채택한 간선 집합({A–C, B–C, B–D, D–E, E–F})과 총 가중치(13)가 완전히 같다는 것을 확인할 수 있다.

왜 탐욕적 선택이 항상 최적인가 — 컷 성질

크루스칼과 프림 모두 “지금 당장 가장 싼 것을 고른다”는 탐욕(greedy) 전략을 쓰는데, 매 순간의 최선이 어떻게 전체 최적(전체 가중치 최소)을 보장하는지 의문이 들 수 있다. 이를 뒷받침하는 것이 컷 성질(cut property)이다.

그래프의 정점 집합을 두 그룹으로 나누는 것을 컷(cut)이라 부른다. 컷 성질은 다음과 같이 말한다.

어떤 컷에서, 그 컷을 가로지르는(양쪽 그룹을 잇는) 간선 중 가중치가 가장 작은 간선은 항상 어떤 최소 신장 트리에도 포함될 수 있다.

왜 그런지 반증법으로 확인해 본다. 어떤 컷을 가로지르는 최소 가중치 간선을 $e$라 하고, $e$를 포함하지 않는 최소 신장 트리 $T$가 있다고 가정한다. $T$는 신장 트리이므로 컷의 양쪽을 잇는 경로가 반드시 존재하고, 그 경로에는 컷을 가로지르는 간선 $e'$이 적어도 하나 있다. $e$는 컷을 가로지르는 간선 중 가중치가 최소이므로 $w(e) \leq w(e')$이다. 이제 $T$에서 $e'$을 빼고 대신 $e$를 넣으면, 여전히 모든 정점을 연결하는 신장 트리이면서 가중치는 $w(T) - w(e') + w(e) \leq w(T)$로 줄어들거나 같다. $T$가 최소였다는 가정과 모순되지 않으려면 $w(e) = w(e')$이어야 하고, 이 경우 $e$를 포함한 신장 트리도 똑같이 최소가 된다. 즉 $e$를 포함하는 최소 신장 트리가 항상 존재한다.

• 크루스칼에서 매번 “아직 연결되지 않은 두 그룹(정점 하나하나가 처음엔 모두 별개의 그룹)을 가르는 컷”을 놓고 그 컷을 가로지르는 가장 싼 간선(정렬되어 있으므로 항상 지금 확인하는 간선이 후보가 된다)을 고르는 것이 바로 이 컷 성질을 반복 적용하는 것이다.
• 프림에서는 “방문 집합과 나머지”라는 하나의 컷을 고정해 두고, 그 컷을 가로지르는 가장 싼 간선을 매번 고르는 것이 컷 성질의 직접적인 적용이다.

이 증명이 바로 16편에서 다룰 “탐욕 알고리즘이 항상 최적해를 주는 것은 아니지만, 문제가 특정 성질(교환 논증으로 반증 가능한 구조)을 만족하면 탐욕이 최적임을 증명할 수 있다” 는 원칙의 구체적인 사례다. MST 문제는 컷 성질 덕분에 탐욕이 최적임이 수학적으로 보장되는 몇 안 되는 문제 중 하나다.

자주 틀리는 점: “탐욕 알고리즘은 근사해만 준다”고 일반화하면 안 된다. 배낭 문제(0/1)처럼 탐욕이 최적을 보장하지 못하는 문제도 있지만, MST처럼 컷 성질이 성립하는 문제에서는 탐욕이 항상 정확한 최적해를 준다. “이 문제에 탐욕을 써도 되는가”는 문제마다 별도로 증명해야 하는 성질이지, 탐욕이라는 접근법 자체의 일반적인 한계가 아니다.

자주 틀리는 점

• Kahn 알고리즘에서 큐가 빈 채로 종료됐는데 처리된 정점이 전체보다 적은 경우를 놓치는 실수: 이는 사이클이 있다는 신호이며, 위상 정렬이 불가능하다고 판정해야 한다.
• 위상 정렬 결과가 유일하다고 착각하는 실수: 같은 시점에 진입차수가 0인 정점이 여러 개면 처리 순서에 따라 서로 다른 올바른 위상 정렬이 나올 수 있다.
• 크루스칼에서 사이클을 만드는 간선도 무조건 채택한다고 착각하는 실수: 가중치가 아무리 작아도 사이클을 만드는 간선은 반드시 버려야 한다.
• 프림의 후보 간선을 그래프 전체 간선으로 착각하는 실수: 프림은 오직 방문 집합에서 바깥으로 나가는 간선만 후보로 고려한다.
• 탐욕 알고리즘이 항상 최적이라고(또는 항상 최적이 아니라고) 일반화하는 실수: MST처럼 컷 성질이 성립하는 문제에서만 탐욕의 최적성이 보장되며, 이는 문제별로 증명이 필요하다.

핵심 정리

• Kahn 알고리즘은 진입차수가 0인 정점을 큐에 넣고 하나씩 꺼내며 나가는 간선을 제거하는 과정을 반복해 위상 정렬을 구하고, 큐가 빈 뒤 처리되지 못한 정점이 남으면 사이클이 있다는 뜻이다.
• 크루스칼은 전체 간선을 가중치순으로 정렬해 사이클을 만들지 않는 것만 채택하고, 프림은 방문 집합의 경계에서 가장 싼 간선만 골라 나가며, 두 방식 모두 같은 MST 총 가중치에 도달한다.
• 탐욕적 간선 선택이 항상 최적임은 컷 성질(어떤 컷을 가로지르는 최소 가중치 간선은 항상 어떤 MST에도 포함될 수 있다)의 교환 논증으로 증명된다.
• 탐욕이 최적을 보장하는 것은 문제의 구조(컷 성질 같은)에 달려 있으며, 모든 문제에 탐욕이 통하는 것은 아니다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제  — 알고리즘 과목 출제기준·평가영역 확인용 공식 안내.
• GeeksforGeeks — Kruskal’s Minimum Spanning Tree Algorithm  — 크루스칼·프림 알고리즘과 MST 성질 참고 자료.