C++로 그래프의 위상 정렬(Topological Sort) 수행하기

위상 정렬(Topological Sort)이란?

방향 비순환 그래프(Directed Acyclic Graph, DAG)에서는 위상 정렬을 이용해 모든 정점을 선형 순서로 나열할 수 있습니다. 위상 정렬은 선행 관계가 있는 작업들의 실행 순서를 결정할 때 유용하게 사용됩니다.

단, 위상 정렬은 오직 방향 비순환 그래프(DAG)에만 적용할 수 있습니다. 그래프에 사이클이 존재하면 위상 정렬은 불가능합니다. 또한 하나의 DAG에는 두 가지 이상의 올바른 위상 정렬 결과가 존재할 수 있다는 점도 기억해야 합니다.

다음 C++ 프로그램은 깊이 우선 탐색(DFS) 기반의 재귀 함수를 활용해 위상 정렬을 수행하며, 이를 응용하면 그래프에 사이클이 존재하는지 여부도 확인할 수 있습니다.

알고리즘

Topo_Sort 함수

시작
    Topo_Sort() 함수를 정의한다
        정수형 변수 x, 불리언 배열 vstd[], 스택 Stack을 매개변수로 전달받는다
        vstd[x] = true로 설정하여 현재 노드를 방문 처리한다
        반복자 i를 선언한다
        for (i = a[x].begin(); i != a[x].end(); ++i)
            if (!vstd[*i]) then
                Topo_Sort(*i, vstd, Stack) 함수를 재귀 호출한다
        push() 함수를 호출하여 현재 정점을 스택에 삽입한다
끝

동작 원리

이 알고리즘은 DFS를 수행하면서 특정 정점에서 도달 가능한 모든 인접 정점들을 먼저 방문한 뒤, 해당 정점을 스택에 푸시(push)합니다. 모든 정점에 대한 탐색이 끝난 후 스택에서 팝(pop)하면, 의존성 순서를 만족하는 위상 정렬 결과를 얻을 수 있습니다. 시간 복잡도는 정점의 개수를 V, 간선의 개수를 E라 할 때 O(V + E)입니다.

예제 코드

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

class grph { // 그래프를 표현하는 클래스
    int ver;
    list<int> *a; // 인접 리스트 배열을 가리키는 포인터
    void Topo_Sort(int x, bool vstd[], stack<int> &Stack); // 위상 정렬 내부에서 사용되는 함수
public:
    grph(int ver); // 생성자
    void Insert_Edge(int x, int y); // 그래프에 간선을 삽입하는 함수
    void Topol_Sort(); // 전체 그래프의 위상 정렬 결과를 출력하는 함수
};

grph::grph(int ver) {
    this->ver = ver;
    a = new list<int>[ver];
}

void grph::Insert_Edge(int x, int y) {
    a[x].push_back(y); // x의 인접 리스트에 y를 추가
}

// Topol_Sort에서 호출되는 재귀 함수
void grph::Topo_Sort(int x, bool vstd[], stack<int> &Stack) {
    vstd[x] = true; // 현재 노드를 방문 처리
    list<int>::iterator i;
    for (i = a[x].begin(); i != a[x].end(); ++i)
        if (!vstd[*i])
            Topo_Sort(*i, vstd, Stack);
    // 현재 정점을 결과를 저장하는 스택에 푸시
    Stack.push(x);
}

void grph::Topol_Sort() {
    stack<int> Stack;
    // 모든 정점을 미방문 상태로 초기화
    bool *vstd = new bool[ver];
    for (int i = 0; i < ver; i++)
        vstd[i] = false;
    for (int i = 0; i < ver; i++)
        if (vstd[i] == false)
            Topo_Sort(i, vstd, Stack);
    // 스택이 빌 때까지 팝하며 출력
    while (Stack.empty() == false) {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}

int main() {
    grph g(6); // 예제 그래프 생성
    g.Insert_Edge(5, 2);
    g.Insert_Edge(5, 0);
    g.Insert_Edge(4, 0);
    g.Insert_Edge(4, 1);
    g.Insert_Edge(2, 3);
    g.Insert_Edge(3, 1);
    cout << "그래프의 위상 정렬 결과: \n";
    g.Topol_Sort();
    return 0;
}

실행 결과

그래프의 위상 정렬 결과:
5 4 2 3 1 0

출력 결과를 보면 정점 5와 4가 가장 앞에 위치하고, 정점 0이 마지막에 위치하는 것을 확인할 수 있습니다. 이는 모든 간선의 방향(u → v)에서 u가 항상 v보다 앞에 오는 조건을 만족하는 올바른 위상 정렬 순서입니다.