[C言語]横系探索(幅優先探索)のアルゴリズムの解説とキューを用いた実装[コード付き]

どうもー
前回に引き続いてグラフの探索をやっていきましょう。
今回は横系探索です！幅優先探索とも言いますね。頑張りましょう！！

⬆︎前回の縦系探索（深さ優先探索）の記事です！！
グラフの探索や、状態遷移図、隣接行列などについてはこちらで解説しているので、まだ読んでいない方は是非読んでから続きを読むと理解しやすいと思います！

キューとは？
横系探索のアルゴリズム
コードの実装
実行した結果
全体のコード

キューとは？

まず今回のコードで使うキューについて簡単に説明します。

キューは別名待ち行列と呼ばれるデータ構造のことです。
どのような性質かというと、
先入れ先出しです。
(英語だと First In First Out で FIFOです)

図を用いて説明します。
ここではキューに要素を入れることをenqueue、取り出すことをdequeueとします。

まずキューに要素1,2,3をその順番でenqueueします

このキューに対してdequeueを行うと、最初にenqueueした1が取り出されます。

そのキューに対して要素4をenqueueするとキューの後ろに要素4がくっつきます

このキューに対してdequeueを行うと、最初に取り出した要素1の次にenqueueした要素2が取り出されます。

このように、キューに早くいれたものから早く取り出していく、というのが最大の性質です。

かなり簡単に説明したのでわかりにくかったら各自で調べてみてください！！

横系探索のアルゴリズム

とりあえずwikipediaに書いてあるアルゴリズムを紹介します

幅優先探索はグラフ理論において木構造やグラフの探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横系探索」とも言われる。

例のごとく文字だとよくわからんな…

ですよね〜
てことで今回も具体例をあげてから説明していきます。

まず今回も前回同様この迷路を探索することとします。

この状態遷移図をわかりやすいように描き直して、

このようにします。
このグラフを横系探索（幅優先探索）では以下のように探索します

みて分かる通り、分岐して平行に並ぶ要素が出てきた場合はまずその要素らを順に全て探索する。そのあとその要素の子要素たちを順に全て探索していく、、といった感じです。

横方向に探索していっているのが分かると思います。これが横系探索の横の部分です！！

どのようなアルゴリズムで動いているのかというと、

スタート地点の要素をキューに入れる
キューから要素を取り出しその要素を探索する
さらにその要素とつながっている要素を全てキューの中に入れる。(キューの中身が存在すれば２へ戻る、存在しなければ探索終了)

このような感じです。
とにかくキューに入れた順に探索して、探索中の要素につながっている要素があればとりあえずキューに入れて、あとで探索、、
といった感じですね。これだけで横系探索が実現できます！！

コードの実装

隣接行列の導入

前回と同様にグラフは隣接行列で表現します。
わからない方は前回の記事を読んでくださいね。

int a[N][N]=
{{0,1,0,0,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0},
 {0,0,0,0,0,1,0,0,0},
 {0,0,0,0,1,0,0,0,0},
 {0,1,0,1,0,1,0,1,0},
 {0,0,1,0,1,0,0,0,0},
 {0,0,0,0,0,0,0,1,0},
 {0,0,0,0,1,0,1,0,1},
 {0,0,0,0,0,0,0,1,0}};

キューの導入

最初のいろいろ

探索の関数の前にキューを導入します。
とりあえず構造体を定義します。

#define NMAX 64

typedef struct openlist{
    int queue[NMAX];
    int head;
    int tail;
}openlist;

配列queueは名の通りキューです。
headとtailがキューの先頭と末尾の添え字を表しています。

配列queueの大きさNMAXは扱う要素数より充分大きければなんでも良いです。
今回はなんとなく64にしました。

つぎはキューの初期設定です

void set_openlist(openlist *A){
    A->head = NMAX;
    A->tail = NMAX;
}

キューの構造体を受け取ってheadとtailをNMAXにします。
headとtailが同時にNMAXになることはまずあり得ません、つまりこのキューは中身が存在しないことを示すためにこの値に変更してます。

ちなみに値を変えているので引数はポインタ型にしましょう。

enqueue

次はenqueuです（要素を入れる）

void enqueue(openlist *A, int v){
    if(A->head == NMAX){
        A->head = 0;
        A->tail = 0;
        A->queue[0] = v;
    }else{
        A->tail++;
        A->queue[A->tail] = v;
    }
}

まず初めて要素を入れる場合について。
この時はset_openlistでheadをNMAXにしているのでif文で判定します。
最初に要素を入れるということはhead,tailともにキューの配列の先頭を指しているので（つまり添え字0）headとtailを0に変更します。
その後queueの添え字0の要素を入れる要素の値にしておkです。

初めてでない場合はelseで判定します。
この時はtailをインクリメントして、そのtailの値を添え字とするqueueの要素に、今回入れる要素の値を代入すればおk。

dequeue

つぎはdequeueです（要素取り出し）

int dequeue(openlist *A){
    int date;
   
    date = A->queue[A->head];
    A->head++;
    return date;
}

int型でdateを用意します。
そのdateに今のキューの先頭、つまりheadを添え字とする配列queueの要素を代入します。
この時点でキューの先頭が抜けたので、headをインクリメントして先頭を次の要素にします。

returnでdateを返せばおk。簡単ですね。

横系探索の関数

int flag[N]={0};

void HrzSearch(int i){
    flag[i] = 1;
    
    printf("Search %d \n",i+1);
    
    for(int j=0; j<N; j++){
        if (a[i][j] == 1 && flag[j] == 0){
            enqueue(&X, j+1);
        }
    }
}

この関数では引数に渡された要素の探索のみを行います。
とりあえずどの要素を探索したかを明らかにするグローバル配列flagの対応する要素を1にしておきます。このflagについては縦系探索の記事で少し詳しく書いているのでそちらを参考ください。

その後、for文を用いて隣接行列を走査してその要素とつながっている要素を全てenqueueしていきます。その際にflagが0かも判定に使います。

main関数

int main(void){
    set_openlist(&X);
    
    HrzSearch(0);
    show_openlist(X);
    
    do{
        HrzSearch(dequeue(&X)-1);
        show_openlist(X);
        
    }while(X.head <= X.tail);
}

mainではまずset_openlistでキューをセッティングします。

その後まず最初の要素に対して探索を実行。（show_openlistはキューの中身を表示するだけの関数なので無視して！）

それが終わった時点でキューに要素が入っているはずなのでここからはその要素を軸に探索します。

キューの先頭の要素をdequeueで取り出して、横系探索の関数HrzSearchに渡します。（配列の添字の関係で-1してます）

この処理をキューの中身がなくなるまでやりたいのでdo while で囲って条件はheadがtail以下とします。

中身がなくなる時はtailがheadより小さくなる時なのでこれでいい具合ですね。

実行した結果

ちゃんと動いてますね。

縦系に比べてキューを使ってる分ややこしいですが、そこまで難しくないと思います。
ぜひ参考にしてください！！

もう一度前回の縦系の記事を宣伝しときます。
ではまた〜

全体のコード

int a[N][N]=
{{0,1,0,0,0,0,0,0,0},
 {1,0,0,0,1,0,0,0,0},
 {0,0,0,0,0,1,0,0,0},
 {0,0,0,0,1,0,0,0,0},
 {0,1,0,1,0,1,0,1,0},
 {0,0,1,0,1,0,0,0,0},
 {0,0,0,0,0,0,0,1,0},
 {0,0,0,0,1,0,1,0,1},
 {0,0,0,0,0,0,0,1,0}};

int flag[N]={0};

typedef struct openlist{
    int queue[NMAX];
    int head;
    int tail;
}openlist;

void set_openlist(openlist *A){
    A->head = NMAX;
    A->tail = NMAX;
}
openlist X;

void show_openlist(openlist A){
    printf("\nopenlist:");
    for(int i=A.head; i<=A.tail; i++){
        printf("%d  ",A.queue[i]);
    }
    printf("\n\n");
}

void enqueue(openlist *A, int v){
    if(A->head == NMAX){
        A->head = 0;
        A->tail = 0;
        A->queue[0] = v;
    }else{
        A->tail++;
        A->queue[A->tail] = v;
    }
}

int dequeue(openlist *A){
    int date;
    
    date = A->queue[A->head];
    A->head++;
    return date;

}

void HrzSearch(int i){
    flag[i] = 1;
    
    printf("Search %d \n",i+1);
    
    for(int j=0; j<N; j++){
        if (a[i][j] == 1 && flag[j] == 0){
            enqueue(&X, j+1);
        }
    }
}

int main(void){
    set_openlist(&X);
    
    HrzSearch(0);
    show_openlist(X);
   
    do{        
        HrzSearch(dequeue(&X)-1);
        show_openlist(X);
        
    }while(X.head <= X.tail);
}