C++로 그래프가 DAG(방향 비순환 그래프)인지 확인하는 방법

DAG(Directed Acyclic Graph, 방향 비순환 그래프)는 간선에 방향이 존재하면서도 사이클(cycle)을 형성하지 않는 그래프를 의미합니다. 즉, 모든 간선은 한 방향으로만 진행되며, 어떤 정점에서 출발해도 다시 자기 자신으로 돌아오는 경로가 존재하지 않습니다. 이 글에서는 주어진 그래프가 DAG인지 판별하는 C++ 프로그램을 소개합니다.

알고리즘

핵심 아이디어는 다음과 같습니다. 인접 리스트를 순회하면서 나가는 간선(outgoing edge)이 없는 정점을 찾고, 해당 정점을 발견할 때마다 카운트를 증가시킵니다. 전체 정점 수보다 하나 적은 개수만큼 카운트가 도달하면 그래프는 DAG로 판단할 수 있습니다.

Begin
Function checkDAG(int n):
    count = 0으로 초기화
    size = n - 1로 초기화
    for i = 0 to n-1
        if (count == size)
            return 1
        done
        if (arr[i].ptr == NULL)
            count 증가
            for j = 0 to n-1
                while (arr[j].ptr != NULL)
                    if ((arr[j].ptr)->d == (arr[i].ptr)->d)
                        (arr[j].ptr)->d = -1
                    done
                    arr[i].ptr = (arr[i].ptr)->next
                done
            done
        done
    done
    return 0
End

예제 코드

아래 코드는 인접 리스트 구조체를 활용해 그래프를 표현하고, 간선 추가 함수와 역방향 간선 추가 함수, 그리고 DAG 여부를 검사하는 함수로 구성되어 있습니다.

#include<iostream>
using namespace std;
int c = 0;
struct ad_list { // 인접 리스트 노드 구조체
    int d;
    ad_list *next;
}
*np = NULL, *np1 = NULL, *p = NULL, *q = NULL;
struct Gr { // 그래프 정점 구조체
    int v;
    ad_list *ptr;
}
arr[6];
void addRevEdge(int s, int d) { // 그래프에 역방향 간선을 추가하는 함수
    np1 = new ad_list;
    np1->d = s;
    np1->next = NULL;
    if (arr[d].ptr == NULL) {
        arr[d].ptr = np1;
        q = arr[d].ptr;
        q->next = NULL;
    } else {
        q = arr[d].ptr;
        while (q->next != NULL) {
            q = q->next;
        }
        q->next = np1;
    }
}
void addEdge(int s, int d) { // 그래프에 간선을 추가하는 함수
    np = new ad_list;
    np->d = d;
    np->next = NULL;
    if (arr[s].ptr == NULL) {
        arr[s].ptr = np;
        p = arr[s].ptr;
        p->next = NULL;
    } else {
        p = arr[s].ptr;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = np;
    }
}
void print_g(int n) {
    for (int i = 0; i < n; i++) {
        cout << "Adjacency List of " << arr[i].v << ": ";
        while (arr[i].ptr != NULL) {
            cout << (arr[i].ptr)->d<< " ";
            arr[i].ptr = (arr[i].ptr)->next;
        }
        cout << endl;
    }
}
int checkDAG(int n) {
    int count = 0;
    int size = n - 1;
    for (int i = 0; i < n; i++) {
        if (count == size) {
            return 1;
        }
        if (arr[i].ptr == NULL) {
            count++;
            for (int j = 0; j < n; j++) {
                while (arr[j].ptr != NULL) {
                    if ((arr[j].ptr)->d == (arr[i].ptr)->d) {
                        (arr[j].ptr)->d = -1;
                    }
                    arr[i].ptr = (arr[i].ptr)->next;
                }
            }
        }
    }
    return 0;
}
int main() {
    int v = 4;
    cout << "Number of vertices: " << v << endl;
    for (int i = 0; i < v; i++) {
        arr[i].v = i;
        arr[i].ptr = NULL;
    }
    addEdge(1, 0);
    addEdge(3, 1);
    addEdge(2, 1);
    addEdge(0, 3);
    addEdge(4, 1);
    print_g(v);
    cout << "The given graph is 'Directed Acyclic Graph' :";
    if (checkDAG(v) == 1)
        cout << " yes";
    else
        cout << " no";
}

실행 결과

위 프로그램을 실행하면 각 정점의 인접 리스트가 출력되고, 마지막으로 해당 그래프가 DAG인지 여부가 표시됩니다.

Number of vertices: 4
Adjacency List of 0: 3
Adjacency List of 1: 0
Adjacency List of 2: 1
Adjacency List of 3: 1
The given graph is 'Directed Acyclic Graph' : yes

실행 결과에서 확인할 수 있듯이, 예제 그래프는 사이클을 포함하지 않으므로 프로그램은 'yes'를 출력하여 이 그래프가 유효한 방향 비순환 그래프임을 알려줍니다.