C++でグラフ内のすべてのフォワードエッジ（前向き辺）を検出するプログラム

この記事では、深さ優先探索（DFS）を利用して、有向グラフ内のすべてのフォワードエッジ（前向き辺）を検出するC++プログラムを解説します。

フォワードエッジとは？

DFSでグラフを探索する際、各頂点に「発見時刻（S_Time）」と「完了時刻（L_Time）」を記録すると、グラフのエッジは次の4種類に分類できます。

• 木エッジ（Tree Edge）：DFSの探索木を構成する辺
• 後退エッジ（Back Edge）：祖先の頂点へ戻る辺（サイクルの存在を示します）
• フォワードエッジ（Forward Edge）：子孫の頂点へ向かうものの、探索木には含まれない辺
• 交差エッジ（Cross Edge）：上記のいずれにも該当しない辺

本プログラムは隣接行列を受け取り、DFSを実行しながら各頂点の時刻を記録します。訪問済みかつスタック上に存在しない頂点への辺については、現在の発見時刻と相手の完了時刻を比較することで、フォワードエッジかどうかを判定します。

アルゴリズム

topo関数の処理の流れ

開始
　　関数 topo() を宣言する
　　　　整数型のポインタ v、二次元配列 m[][5]、変数 i を宣言する
　　　　x = new Node_Inf
　　　　x->n = i を設定
　　　　x->S_Time = c を設定
　　　　関数 Push_Node(x) を呼び出す
　　　　v[i] = 1 を設定
　　　　for (int j = 0; j < 5; j++)
　　　　　　if (m[i][j] == 0) の場合は
　　　　　　　　continue;
　　　　　　else if (m[i][j] == 1 && v[j] == 1 && !Exist_in_Stack(j)) の場合は
　　　　　　　　if (x->S_Time < srch_Node(j)) の場合は
　　　　　　　　　　「Forward Edge is between」を出力する
　　　　　　　　　　フォワードエッジの値を出力する
　　　　　　　　continue;
　　　　　　else if (m[i][j] == 1 && v[j] == 0) の場合は
　　　　　　　　c++ を実行
　　　　　　　　「Forward Edge is between」を出力する
　　　　　　　　フォワードエッジの値を出力する
　　　　　　　　関数 topo(v,m,j) を呼び出す
　　　　c++ を実行
　　　　x = pop()
　　　　x->L_Time = c を設定
　　　　値をノードに格納するために関数 Store_Node(x) を呼び出す
　　Return.
終了

C++での実装例

#include<iostream>
#include<conio.h>
using namespace std;
struct Node_Inf {
    int n;
    int L_Time, S_Time;
}
*x = NULL, *y = NULL;
struct Node_1 {
    Node_Inf *ptn;
    Node_1 *nxt;
}
*tp = NULL, *p = NULL, *npr = NULL;
struct Node_2 {
    Node_2 *lnk;
    Node_Inf *ptn1;

}
*hd = NULL, *m = NULL, *n = NULL, *npr1 = NULL;
int c = 0;
void Push_Node(Node_Inf *ptr) {
    npr = new Node_1;
    npr->ptn = ptr;
    npr->nxt = NULL;
    if (tp == NULL) {
        tp = npr;
    } else {
        npr->nxt = tp;
        tp = npr;
    }
}
Node_Inf *pop() {
    if (tp == NULL) {
        cout<<"underflow\n";
    } else {
        p = tp;
        tp = tp->nxt;
        return(p->ptn);
        delete(p);
    }
}
void Store_Node(Node_Inf *ptr1) {
    npr1 = new Node_2;
    npr1->ptn1 = ptr1;
    npr1->lnk = NULL;
    if (c == 0) {
        hd = npr1;
        m = hd;
        m->lnk = NULL;
        c++;
    } else {
        m = hd;
        npr1->lnk = m;
        hd = npr1;
    }
}
int srch_Node(int j) {
    Node_2 *t = hd;
    while (t != NULL) {
        if ((t->ptn1)->n == j)
        {
            break;
        } else {
            t = t->lnk;
            continue;
        }
    }
    return (t->ptn1)->L_Time;
}
int Exist_in_Stack(int j) {
    int flag = 0;
    p = tp;
    while (p != NULL) {
        if ((p->ptn)->n == j) {
            flag = 1;
            return flag;
        }
        p = p->nxt;
    }
    return flag;
}
void topo(int *v, int m[][5], int i) {
    x = new Node_Inf;
    x->n = i;
    x->S_Time = c;
    Push_Node(x);
    v[i] = 1;
    for (int j = 0; j < 5; j++) {
        if (m[i][j] == 0)
            continue;
        else if (m[i][j] == 1 && v[j] == 1 && !Exist_in_Stack(j)) {
            if (x->S_Time < srch_Node(j)) {
                cout<<"\nForward Edge is between "<<i<<" and "<<j<<endl;
            }
            continue;
        } else if (m[i][j] == 1 && v[j] == 0) {
            c++;
            cout<<"\nForward Edge is between "<<i<<" and "<<j<<endl;
            topo(v,m,j);
        }
    }
    c++;
    x = pop();
    x->L_Time = c;
    Store_Node(x);
    return;
}
int main() {
    int v[5],m[5][5];
    for (int i = 0; i < 5; i++)
    v[i] = 0;
    for (int i = 0; i < 5; i++) {
        cout<<" Enter the values of matrix::"<<i + 1<<endl;
        for(int j = 0; j < 5; j++) {
            cin>>m[i][j];
        }
    }
    topo(v,m,0);
    getch();
}

※ conio.h や getch() はBorland系など古いコンパイラ向けの機能です。GCCやClangなどの最新の開発環境では、これらを削除するか、標準入力待ちの別の方法に置き換えてご利用ください。

出力例

Enter the values of matrix:1
0
1
0
1
0
Enter the values of matrix:2
1
0
0
1
0
Enter the values of matrix:3
1
0
0
0
1
Enter the values of matrix:4
0
1
1
0
0
Enter the values of matrix:5
1
1
0
0
0

Forward Edge is between 0 and 1

Forward Edge is between 1 and 3

Forward Edge is between 3 and 2

Forward Edge is between 2 and 4

Forward Edge is between 0 and 3

まとめ

このように、DFSで各頂点の発見時刻と完了時刻を記録しておけば、時刻の大小関係を比較するだけでフォワードエッジを効率よく検出できます。サイクル検出やトポロジカルソートなど、DFSの応用テクニックを学ぶ上でも役立つプログラムなので、ぜひ手を動かして試してみてください。