[C++] Kahn 알고리즘으로 위상 정렬 구현하기

Kahn 알고리즘으로 위상 정렬 구현하기

위상 정렬이란?

위상 정렬(Topological Sort)은 순환하지 않는 방향 그래프(DAG)에서 노드의 순서를 정하는 알고리즘이다.
주로 작업의 선후 관계가 있는 문제(예: 선수 과목, 건설 순서 등)에 사용된다.

예를 들어, D 건물을 짓기 위해 B와 C를 먼저 지어야 하고, B는 A를 필요로 한다면 가능한 건설 순서는:

• A → B → C → D
• A → C → B → D
• C → A → B → D

하지만 B → A → C → D는 B가 A보다 앞에 나오므로 잘못된 순서다.

---

Kahn 알고리즘

Kahn 알고리즘은 위상 정렬을 BFS 기반으로 수행하는 대표적인 방법이다.

🔧 핵심 아이디어

• 진입 차수(indegree): 각 노드로 들어오는 간선의 수
• 진입 차수가 0인 노드(들어오는 간선이 없는 가장 앞의 수들)를 큐에 넣고, 하나씩 꺼내면서 연결된 노드들의 진입 차수를 감소시킨다
• 진입 차수가 0이 된 노드를 다시 큐에 넣는다
• 모든 노드를 처리하면 정렬된 결과가 나온다

---

🧠 알고리즘 순서

1. 모든 노드의 진입 차수를 구한다.
2. 진입 차수가 0인 노드를 큐에 넣는다.
3. 큐에서 하나씩 꺼내면서 결과 리스트에 추가한다.
4. 꺼낸 노드와 연결된 노드들의 진입 차수를 1씩 줄인다.
5. 새로 진입 차수가 0이 된 노드는 큐에 추가한다.
6. 큐가 빌 때까지 반복한다.

---

💻 C++ 코드 예제

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m; // n: 노드 개수, m: 간선 개수
    cin >> n >> m;

    vector<vector<int>> graph(n + 1);
    vector<int> indegree(n + 1, 0);

    // 간선 입력
    for (int i = 0; i < m; i++) {
        int from, to;
        cin >> from >> to;
        graph[from].push_back(to);
        indegree[to]++;
    }

    queue<int> q;
    vector<int> result;

    // 초기: 진입 차수가 0인 노드 큐에 넣기
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) q.push(i);
    }

    // 위상 정렬 수행
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        result.push_back(cur);

        for (int next : graph[cur]) {
            indegree[next]--;
            if (indegree[next] == 0) q.push(next);
        }
    }

    // 결과 출력
    if (result.size() == n) {
        for (int x : result) cout << x << " ";
    } else {
        cout << "사이클이 존재합니다. 위상 정렬 불가.";
    }

    return 0;
}

📊 시간 복잡도

• O(V + E)
  • V: 노드 수, E: 간선 수
  • 큐에 각 노드를 한 번씩 넣고, 모든 간선을 한 번씩 탐색하기 때문