トポロジカルソートを使ってグラフのサイクル(閉路)を検出するC++プログラム

トポロジカルソートとは

有向非巡回グラフ(DAG:Directed Acyclic Graph)では、トポロジカルソートを利用してすべての頂点を線形の順序に並べ替えることができます。トポロジカルソートは有向非巡回グラフに対してのみ適用できる手法であり、1つのDAGに対して複数の妥当な並び順が存在する場合もあります。

本記事では、トポロジカルソートを応用して、グラフの中にサイクル(閉路)が存在するかどうかを判定するC++プログラムを紹介します。

サイクル検出の基本的な考え方

まず、深さ優先探索(DFS)によって各頂点の「発見時刻(S_Time)」と「完了時刻(L_Time)」を記録しながらトポロジカルソートを実行します。続いて、隣接行列を転置したグラフ(転置グラフ)上でもう一度探索を行い、訪問した頂点を順にリストから削除していきます。この処理の過程で削除対象の頂点が見つからなくなったかどうかをもとに、サイクルの有無を判定するのが本プログラムの仕組みです。

例

アルゴリズム

トポロジカルソート部分の流れは、次の擬似コードのとおりです。

トポロジカルソート:
開始
    topo_sort(int *v, int T_S[][5], int i) 関数を宣言する
        a = 新しい NodeInfo を生成
        a->n = i
        a->S_Time = cn
        push_node(a) を呼び出してスタックに挿入
        v[i] = 1(訪問済みにする)
        for (int j = 0; j < 5; j++)
            T_S[i][j] == 0、または(T_S[i][j] == 1 かつ v[j] == 1)の場合
                continue(スキップして次へ)
            それ以外で T_S[i][j] == 1 かつ v[j] == 0 の場合
                cn++
                topo_sort(v, T_S, j) を再帰的に呼び出す
        cn++
        a = pop()
        a->L_Time = cn
        Store_Node(a) でノードを保存
終了。

C++による実装

以下が完全なサンプルコードです。頂点数は5個に固定されており、ユーザーから5本の辺(始点と終点)を入力として受け取り、サイクルの有無を出力します。

#include<iostream>
#include<conio.h>
using namespace std;
struct NodeInfo {
    int n;
    int L_Time, S_Time;
}
*a = NULL;
struct Node {
    NodeInfo *ptr;
    Node *nxt;
}
*t = NULL, *b = NULL, *npt = NULL;
struct Node_Link {
    Node_Link *lk;
    NodeInfo *ptr1;
}
*hd = NULL, *m = NULL, *n = NULL, *npt1 = NULL;
int cn = 0;
bool flag = false;
void push_node(NodeInfo *pt) { // データを挿入
    npt = new Node;
    npt->ptr = pt;
    npt->nxt = NULL;
    if (t == NULL) {
        t = npt;
    } else {
        npt->nxt = t;
        t = npt;
    }
}
NodeInfo *pop() {
    if (t == NULL) {
        cout<<"underflow\n";
    } else {
        b = t;
        t = t->nxt;
        return(b->ptr);
        delete(b);
    }
}
void Store_Node(NodeInfo *pt1) { // データを保存
    npt1 = new Node_Link;
    npt1->ptr1 = pt1;
    npt1->lk = NULL;
    if (cn == 0) {
        hd = npt1;
        m = hd;
        m->lk = NULL;
        cn++;
    } else {
        m = hd;
        npt1->lk = m;
        hd = npt1;
    }
}
void delete_node(int x) { // ノードを削除
    m = hd;
    if ((m->ptr1)->n == x) {
        hd = hd->lk;
        delete(m);
    } else {
        while ((m->ptr1)->n != x && m->lk != NULL) {
            n = m;
            m = m->lk;
        }
        if ((m->ptr1)->n == x) {
            n->lk = m->lk;
            delete(m);
        } else if (m->lk == NULL) {
            flag = true;
            cout<<"このグラフにサイクルは存在しません\n";
        }
    }
}
void topo_sort(int *v, int T_S[][5], int i) { // トポロジカルソートを実行
    a = new NodeInfo;
    a->n = i;
    a->S_Time = cn;
    push_node(a);
    v[i] = 1;
    for (int j = 0; j < 5; j++) {
        if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1))
            continue;
        else if(T_S[i][j] == 1 && v[j] == 0) {
            cn++;
            topo_sort(v,T_S,j);
        }
    }
    cn++;
    a = pop();
    a->L_Time = cn;
    Store_Node(a);
    return;
}
void topologic_sort(int *v, int T_S[][5], int i) {
    v[i] = 1;
    delete_node(i);
    for (int j = 0; j < 5; j++) {
        if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1)) {
            continue;
        } else if(T_S[i][j] == 1 && v[j] == 0) {
            topologic_sort(v, T_S, j);
        }
    }
    return;
}
void Insert_Edge(int T_S[][5], int source, int destination) { // 辺の値を挿入
    T_S[source][destination] = 1;
    return;
}
int main() {
    int v[5], T_S[5][5], T_S_N[5][5], cn = 0, a, b;
    for (int i = 0; i < 5; i++) {
        v[i] = 0;
    }
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            T_S[i][j] = 0;
        }
    }
    while (cn < 5) {
        cout<<"始点を入力してください: ";
        cin>>a;
        cout<<"終点を入力してください: ";
        cin>>b;
        cout<<endl;
        Insert_Edge(T_S, a, b);
        cn++;
    }
    topo_sort(v, T_S, 0);
    for (int i = 0; i < 5; i++) {
        v[i] = 0;
        for (int j = 0; j < 5; j++) {
            T_S_N[j][i] = T_S[i][j];
        }
    }
    if (hd != NULL) {
        topologic_sort(v, T_S_N, (hd->ptr1)->n);
        if (flag == false) {
            cout<<"このグラフにはサイクルが存在します...\n";
        }
    }
    getch();
}

コードのポイント

• push_node / pop:頂点番号・開始時刻・完了時刻を持つNodeInfoを格納する、スタックの基本操作です。
• Store_Node:popで取り出したノードを、完了時刻の新しい順に連結リストへ保存します。
• delete_node:指定した頂点番号のノードをリストから削除します。見つからなかった場合はflagをtrueにし、「サイクルなし」と判定します。
• topo_sort:DFSで開始時刻と完了時刻を記録しながらトポロジカルソートを行う本体部分です。
• topologic_sort:転置グラフ上で探索を行いながら頂点を削除し、サイクルの有無を判定します。
• Insert_Edge:隣接行列T_Sに辺(始点→終点)を登録します。

実行結果

0→1→2→3→4→0 のように、最後の辺が起点へ戻る入力を与えると、グラフにサイクルが存在すると判定されます。

始点を入力してください: 0
終点を入力してください: 1

始点を入力してください: 1
終点を入力してください: 2

始点を入力してください: 2
終点を入力してください: 3

始点を入力してください: 3
終点を入力してください: 4

始点を入力してください: 4
終点を入力してください: 0

このグラフにはサイクルが存在します...