설명

• 위상정렬
• 비순환 그래프의 모든 노드를 순서대로 나열하는 정렬 방법
• Kahn의 알고리즘 방식, DFS 기반으로 한 방식 두 가지
• 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘
• 사이클이 없는 방향 그래프여야 함

Kahn 알고리즘 방식 예제

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void addEdge(vector<vector<int>>& adj, int v, int w) {
    adj[v].push_back(w);
}

void topologicalSort(vector<vector<int>>& adj, int V) {
    vector<int> in_degree(V, 0);

    for (int u = 0; u < V; u++) {
        for (int v : adj[u]) {
            in_degree[v]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < V; i++) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    int cnt = 0;
    vector<int> top_order;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        top_order.push_back(u);

        
        for (int v : adj[u]) {
            if (--in_degree[v] == 0) {
                q.push(v);
            }
        }

        cnt++;
    }

    if (cnt != V) {
        // 그래프에 사이클이 존재합니다. 위상 정렬이 불가능합니다.
        return;
    }

    for (int i : top_order) {
        cout << i << " ";
    }
    cout << endl;
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);

    addEdge(adj, 5, 2);
    addEdge(adj, 5, 0);
    addEdge(adj, 4, 0);
    addEdge(adj, 4, 1);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 1);

    // 위상 정렬 결과
    topologicalSort(adj, V);

    return 0;
}

설명

1. 각 정점의 진입 차수 계산
2. 시작 정점을 큐에 삽입
3. 정점을 하나씩 꺼내고, 인접 정점들의 진입 차수를 감소
4. 진입 차수가 0이 된 정점을 다시 큐에 삽입
5. 그래프에 사이클 존재시, 불가능 처리

DFS 방식 예제

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

void addEdge(vector<vector<int>>& adj, int v, int w) {
    adj[v].push_back(w);
}

void DFS(int v, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& stk) {
    visited[v] = true;

    for (int i : adj[v]) {
        if (!visited[i]) {
            DFS(i, adj, visited, stk);
        }
    }

    stk.push(v);
}

void topologicalSort(vector<vector<int>>& adj, int V) {
    stack<int> stk;
    vector<bool> visited(V, false);

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            DFS(i, adj, visited, stk);
        }
    }

    while (!stk.empty()) {
        cout << stk.top() << " ";
        stk.pop();
    }

    cout << "\n";
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);

    addEdge(adj, 5, 2);
    addEdge(adj, 5, 0);
    addEdge(adj, 4, 0);
    addEdge(adj, 4, 1);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 1);

    // 위상 정렬 결과
    topologicalSort(adj, V);

    return 0;
}

설명

1. 정점 v에 대해 dfs 수행하고, 모든 인접 정점 방문 후에 정점을 스택에 삽입
2. dfs 완료되면 해당 정점을 스택에 삽입
3. 최종적으로 스택에 쌓인 정점을 꺼내서 위상 정렬 결과 출력