[c++] 위상 정렬 알고리즘

08 Dec 2023

위상 정렬은 방향 그래프 내의 모든 노드가 간선의 방향을 지키면서 나열되는 순서를 찾는 알고리즘이다. 위상 정렬 알고리즘은 주로 작업이 의존 관계에 있는 경우나 일련의 작업들을 순서대로 처리해야 할 때 활용된다.

알고리즘 개요

진입 차수 초기화: 모든 노드의 진입 차수를 계산한다. 진입 차수란 해당 노드로 들어오는 간선의 개수를 의미한다.
진입 차수가 0인 노드 찾기: 진입 차수가 0인 노드를 큐에 넣는다.
노드 방문 및 간선 제거: 큐에서 노드를 꺼내면서 해당 노드를 방문하고, 이와 연결된 간선을 제거한다.
진입 차수 갱신: 간선 제거로 인해 진입 차수가 0이 된 노드를 큐에 넣는다.
반복 수행: 큐가 빌 때까지 2~4단계를 반복한다.

C++ 코드 예시

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

using namespace std;

vector<int> topologicalSort(vector<vector<int>>& graph, vector<int>& inDegree) {
    int n = graph.size();
    vector<int> result;
    queue<int> q;
  
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        result.push_back(node);
        
        for (int& neighbor : graph[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    return result;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> graph(n);
    vector<int> inDegree(n, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        inDegree[v]++;
    }

    vector<int> result = topologicalSort(graph, inDegree);

    if (result.size() < n) {
        cout << "그래프에 순환 경로가 존재합니다." << endl;
    } else {
        for (int& node : result) {
            cout << node << " ";
        }
        cout << endl;
    }

    return 0;
}

위 코드는 위상 정렬을 수행하는 C++ 예시 코드이다. 과제나 작업 스케줄링 등에서 활용될 수 있는 유용한 알고리즘이므로 구현 방법을 숙지하는 것이 중요하다.

알고리즘 개요

C++ 코드 예시

참고 자료