위상 정렬(Topological Sort) 완벽 가이드: 개념부터 C++ 구현까지

위상 정렬이란?

위상 정렬(Topological Sorting)은 방향 비순환 그래프(DAG, Directed Acyclic Graph)의 정점들을 선형 순서로 나열하는 알고리즘입니다. 핵심 규칙은 간단합니다. 방향 그래프의 모든 간선 U → V에 대해, 정렬 결과에서 반드시 정점 U가 정점 V보다 앞에 위치해야 한다는 것입니다.

위상 정렬에서는 시작 정점(출발점)이 도착 정점보다 뒤에 오게 되므로, 이전에 방문한 노드들을 저장하기 위해 스택(Stack) 자료구조를 활용합니다. 모든 노드의 탐색을 마친 후에는 스택에서 요소를 하나씩 꺼내면서 출력하기만 하면 됩니다.

위상 정렬은 작업 스케줄링, 빌드 시스템의 의존성 관리, 강의 이수 순서 결정 등 선행 관계가 있는 문제를 해결할 때 널리 사용됩니다.

입력 및 출력 예시

입력:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 1 0 0 0 0
1 1 0 0 0 0
1 0 1 0 0 0

출력:
Nodes after topological sorted order: 5 4 2 3 1 0

입력은 인접 행렬 형태로 주어지며, graph[i][j]가 1이면 정점 i에서 정점 j로 가는 간선이 존재한다는 의미입니다.

알고리즘

1. topoSort(u, visited, stack)

입력 − 시작 정점 u, 방문 여부를 추적하는 배열, 노드를 저장할 스택
출력 − 위상 순서대로 정점들이 스택에 정렬되어 저장됩니다.

Begin
    mark u as visited
    for all vertices v which is adjacent with u, do
        if v is not visited, then
            topoSort(v, visited, stack)
    done

    push u into a stack
End

2. performTopologicalSorting(Graph)

입력 − 주어진 방향 비순환 그래프(DAG)
출력 − 위상 정렬된 노드의 순서

Begin
    initially mark all nodes as unvisited
    for all nodes v of the graph, do
        if v is not visited, then
            topoSort(i, visited, stack)
    done
    pop and print all elements from the stack
End.

동작 원리 요약

1. 모든 노드를 미방문 상태로 초기화합니다.
2. 방문하지 않은 각 노드에 대해 DFS(깊이 우선 탐색) 기반의 topoSort를 호출합니다.
3. topoSort는 현재 정점을 방문 처리한 뒤, 인접한 미방문 정점들을 재귀적으로 탐색합니다.
4. 해당 정점에서 갈 수 있는 모든 정점 탐색이 끝나면, 그 정점을 스택에 push합니다.
5. 모든 정점 처리 후 스택에서 pop하며 출력하면 위상 정렬된 순서를 얻습니다.

C++ 구현 예제

#include<iostream>
#include<stack>
#define NODE 6
using namespace std;

int graph[NODE][NODE] = {
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0},
    {0, 0, 0, 1, 0, 0},
    {0, 1, 0, 0, 0, 0},
    {1, 1, 0, 0, 0, 0},
    {1, 0, 1, 0, 0, 0}
};

void topoSort(int u, bool visited[], stack<int>&stk) {
    visited[u] = true;                    // 해당 노드를 방문 처리

    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]) {                 // u에 인접한 모든 정점 v 확인
            if(!visited[v])
                topoSort(v, visited, stk);
        }
    }
    stk.push(u);      // 시작 정점을 스택에 push
}

void performTopologicalSort() {
    stack<int> stk;
    bool vis[NODE];

    for(int i = 0; i<NODE; i++)
        vis[i] = false;                   // 처음에 모든 노드는 미방문 상태

    for(int i = 0; i<NODE; i++)
        if(!vis[i])                       // 아직 방문하지 않은 노드라면
            topoSort(i, vis, stk);

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

main() {
    cout << "Nodes after topological sorted order: ";
    performTopologicalSort();
}

실행 결과

Nodes after topological sorted order: 5 4 2 3 1 0

마무리

위상 정렬은 DFS와 스택만으로 간단하게 구현할 수 있으며, 시간 복잡도는 O(V + E)입니다. 단, 그래프에 사이클이 존재하면 위상 정렬이 불가능하다는 점을 기억해야 합니다. 따라서 실무에서는 위상 정렬 전에 그래프가 유효한 DAG인지 확인하는 과정이 필요할 수 있습니다.