C++로 주어진 간선 개수만큼 방향성 비순환 그래프(DAG)를 생성하는 프로그램

이 글에서는 주어진 간선 수 e에 대해 무작위 방향성 비순환 그래프(DAG, Directed Acyclic Graph)를 생성하는 C++ 프로그램을 살펴봅니다. 방향성 비순환 그래프란 간선에 방향이 부여되어 있으면서, 어떤 정점에서 출발하더라도 다시 자기 자신에게 돌아오는 경로(사이클)가 하나도 존재하지 않는 그래프를 의미합니다. 본 프로그램의 시간 복잡도는 O(e·v·e)입니다.

알고리즘

시작
   GenerateRandomGraphs() 함수는 인자로 간선의 개수 'e'를 전달받습니다.
   두 개의 무작위 정점 사이에 연결을 생성합니다. 간단한 예제를 위해 정점의 개수는 20개로 제한합니다.
   CheckAcyclic() 함수를 사용하여 그래프에 사이클이 발생하는지 검사합니다.
   false를 반환하면 해당 간선을 버립니다.
      true를 반환하면 해당 간선을 그래프에 유지합니다.
   각 정점의 모든 방향 연결 정보를 출력합니다.
   어떤 정점의 (진입 차수 + 진출 차수)가 0이면 그 정점을 고립 정점(isolated vertex)으로 출력합니다.
종료

핵심 동작 원리

• Checkcyclic() : 새 간선이 추가될 때마다 DFS와 유사한 방식으로 경로를 따라가며 사이클 발생 여부를 재귀적으로 검사합니다. 이미 방문한 정점을 다시 만나게 되면 사이클이 존재한다는 뜻이므로 false를 반환합니다.
• GenerateRandomGraphs() : 유효한 간선이 e개가 모일 때까지 무작위 간선을 계속 생성하며, 사이클을 만들어내는 간선은 폐기합니다.
• 출력 단계 : 인접 리스트 형태로 각 정점이 향하는 정점들을 나열하고, 연결된 간선이 하나도 없는 정점은 고립 정점으로 표시합니다.

예제 코드

#include<iostream>
#include<stdlib.h>
#define N 10
using namespace std;

// 새 간선을 추가할 때 사이클이 생기는지 검사하는 함수
bool Checkcyclic(int ed[][2], int edge, bool check[], int v) {
   int i;
   // 현재 정점을 이미 방문했다면 그래프에는 사이클이 존재합니다.
   if(check[v] == true) {
      return false;
   } else {
      check[v] = true;
      // 각 정점에 대해 그 정점과 연결된 모든 정점을 탐색합니다.
      for(i = edge; i >= 0; i--) {
         if(ed[i][0] == v) {
            return Checkcyclic(ed, edge, check, ed[i][1]);
         }
      }
   }
   // 경로가 끝나면 해당 경로에서 방문했던 정점들을 다시 false로 되돌립니다.
   check[v] = false;
   if(i == 0)
      return true;
}

void GenerateRandomGraphs(int e) {
   int i, j, ed[e][2], count;
   bool c[11];
   i = 0;
   while(i < e) {
      ed[i][0] = rand()%N+1;
      ed[i][1] = rand()%N+1;
      for(j = 1; j <= 10; j++)
         c[j] = false;
      if(Checkcyclic(ed, i, c, ed[i][0]) == true)
         i++;
   }
   cout<<"\nThe generated random graph is: ";
   for(i = 0; i < N; i++) {
      count = 0;
      cout<<"\n\t"<<i+1<<"-> { ";
      for(j = 0; j < e; j++) {
         if(ed[j][0] == i+1) {
            cout<<ed[j][1]<<" ";
            count++;
         } else if(ed[j][1] == i+1) {
            count++;
         } else if(j == e-1 && count == 0)
            cout<<"Isolated Vertex!";
      }
      cout<<" }";
   }
}

int main() {
   int e;
   cout<<"Enter the number of edges for the random graphs: ";
   cin>>e;
   GenerateRandomGraphs(e);
}

코드 상단의 N 값(정점의 개수)을 변경하면 더 큰 그래프도 생성할 수 있습니다. 다만 정점 수가 늘어날수록 사이클 검사에 필요한 탐색 비용이 커지므로 실행 시간이 길어질 수 있다는 점에 유의하세요.

실행 결과

Enter the number of edges for the random graphs: 4
The generated random graph is:
1-> { }
2-> { 8 }
3-> { 5 }
4-> { Isolated Vertex! }
5-> { 1 }
6-> { Isolated Vertex! }
7-> { Isolated Vertex! }
8-> { }
9-> { Isolated Vertex! }
10-> { 5 }

위 실행 결과에서 실제로 생성된 간선은 4개(2→8, 3→5, 5→1, 10→5)이며, 4번, 6번, 7번, 9번 정점은 어떤 간선과도 연결되지 않은 고립 정점임을 확인할 수 있습니다. 결과는 매 실행마다 달라지는데, 이는 rand() 함수가 무작위 값을 반환하기 때문입니다.