グラフがDAG（有向非巡回グラフ）であるかどうかを判定するC++プログラム

DAG（有向非巡回グラフ）とは

有向非巡回グラフ（DAG：Directed Acyclic Graph）とは、辺に向きが定義された有向グラフであり、かつグラフ内にサイクル（閉路）が存在しないグラフのことです。すべての辺は一方向のみに向かっており、どの頂点から出発しても同じ頂点へ戻ってくる経路は存在しません。DAGは、タスクのスケジューリング、依存関係の解決、トポロジカルソートなど、さまざまな分野で活用されています。

本記事では、与えられたグラフがDAGであるかどうかを判定するC++プログラムを紹介します。

アルゴリズム

このアルゴリズムでは、出次数が0（隣接リストが空）の頂点を順に取り除いていくことで、グラフがDAGであるかを判定します。すべての頂点を取り除くことができればDAGであり、途中で取り除ける頂点がなくなればサイクルが存在すると判断できます。

Begin
Function checkDAG(int n):
    intialize count = 0
    intialize size = n - 1
    for i = 0 to n-1
       if (count == size)
          return 1
       done
       if (arr[i].ptr == NULL)
          increment 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であるかどうかを判定するC++のサンプルコードです。グラフは隣接リスト形式で表現されています。

#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";
}

実行結果

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

この実行結果から、与えられたグラフはDAG（有向非巡回グラフ）であることが確認できます。