グラフの深さ優先探索をc言語で学ぶ

グラフを探索する方法の一つに深さ優先探索(DFS:Depth-First-Search)があります。

探索方法をグラフの解説で使用したグラフを例に解説すると、

 

まず、ノード1に隣接するノードを走査します。

ノード1にノード2が隣接するのでノード2を走査しに行きますが、
この時にノード1に隣接する他のノードの探索を行う前に、
ノード2に隣接するすべてのノードの探索を行います。

ノード2でもノード1と同様に探索を行いノード3を見つけます。

ノード3を見つけたら、ノード4は探索せずに、ノード3の探索を行います。

これを続けていき、隣接ノードが見つからない場合前のノードに戻り、
これを繰り返し、すべての探索が終わったら探索を終了します。

この時にループ処理に陥らないように、一度訪れたノードに対してフラグをもたせます。

では、cで書かれた深さ優先探索を行うコードを見て見ます。
このコードは、上記のグラフを例にしています。

#include 
using namespace std;

#define MAX 8
bool visited[MAX];

void visit(int i);

int GRAPH[MAX][MAX] = {
    {0,1,0,0,0,0,0,0},
    {1,0,1,1,0,0,0,0},
    {0,1,0,0,0,0,1,0},
    {0,1,0,0,0,0,0,0},
    {0,0,0,1,0,1,0,0},
    {0,0,0,0,1,0,1,1},
    {0,0,1,0,0,1,0,1},
    {0,0,0,0,0,1,1,0}
};

int main() {
    visit(0);
    return 0;
}

void visit(int i){
    visited[i] = true;
    for(int j = 0;j < MAX;++j){
        if(GRAPH[i][j] == 1 && !visited[j]){
            printf("%d->%d ",i + 1,j + 1);
            visit(j);
        }
    }
}

実行結果

1->2 2->3 3->7 7->6 6->5 5->4 6->8

ポイントは、一度訪れたノードに対してフラグを持つことです。