C++로 DAG(방향 비순환 그래프)의 무작위 선형 확장 생성하기

이 글에서는 방향 비순환 그래프(Directed Acyclic Graph, DAG)의 무작위 선형 확장(Random Linear Extension)을 생성하는 C++ 프로그램 작성 방법을 알아봅니다. 선형 확장이란 곧 DAG의 위상 정렬(topological sorting)을 의미하며, 하나의 그래프라도 탐색 순서에 따라 여러 가지 유효한 정렬 결과가 나올 수 있습니다. 아래와 같은 그래프를 예로 들어 살펴보겠습니다.

위상 정렬이란?

방향 비순환 그래프의 위상 정렬은 모든 정점을 한 줄로 나열한 순서를 말합니다. 핵심 조건은 간단합니다. 방향 그래프의 모든 간선 u-v에 대해, 정렬된 순서에서 정점 u는 반드시 정점 v보다 앞에 위치해야 합니다.

구현에는 깊이 우선 탐색(DFS)과 스택(stack)을 활용합니다. DFS로 그래프를 순회할 때 어떤 정점에서 뻗어 나가는 모든 인접 정점을 먼저 처리한 뒤에 해당 정점을 스택에 삽입하면, 마지막에 스택에서 요소를 꺼내는 순서가 곧 올바른 위상 순서가 됩니다.

입력

위 행렬은 그래프의 인접 행렬(adjacency matrix) 표현입니다. graph[u][v]의 값이 1이면 정점 u에서 정점 v로 향하는 간선이 존재함을 의미합니다.

출력

위상 정렬 후 노드 순서 − 5 4 2 3 1 0

알고리즘

topoSort(u, visited, stack)

입력 − 시작 정점 u, 각 노드의 방문 여부를 기록하는 배열, 노드를 저장할 스택

출력 − 정점들을 위상 순서에 맞게 스택에 쌓음

Begin
    u를 방문 처리
    u와 인접한 모든 정점 v에 대해
        if v를 아직 방문하지 않았다면
            topoSort(v, visited, stack)
    u를 스택에 push
End

performTopologicalSorting(Graph)

입력 − 주어진 방향 비순환 그래프

출력 − 위상 정렬된 노드의 순서

Begin
    모든 노드를 미방문 상태로 초기화
    그래프의 모든 노드 i에 대해
        if i를 아직 방문하지 않았다면
            topoSort(i, visited, stack)
    스택이 빌 때까지 요소를 pop하며 순서대로 출력
End

그래프가 서로 연결되어 있지 않을 수도 있으므로, 모든 정점을 대상으로 방문 여부를 확인하며 DFS를 시작해야 한다는 점에 유의하세요. 또한 이 알고리즘은 그래프를 한 번만 순회하므로 시간 복잡도는 정점 수 V와 간선 수 E에 대해 O(V + E)입니다.

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; //노드 u를 방문 처리
    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]) //아직 방문하지 않은 노드에서 DFS 시작
            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