幅優先探索のアルゴリズムをc++で学ぶ

幅優先探索のアルゴリズムを学びます。

幅優先探索はグラフで用いられるアルゴリズムで、深さ優先探索と対等してあげられることが多いようです。

深さ優先探索では、隣接するノードが見つかった場合、そのノードを探索しにいきますが、幅優先探索では、隣接ノードが見つかった場合でもそのノードを探索しにいこうとせず、他に隣接するノードがないかをチェックしにいきます。

幅優先探索のアルゴリズム図で学ぶ

幅優先探索のアルゴリズムを学んでいきましょう。
このグラフを幅優先探索にかけてみます。

 

1.ノード1をキューにいれる

1

2.ノード1を取り出して、ノード1に隣接している未訪問のノードをキューに入れます。

1 2

3.次にノード2を取り出して隣接しているノード3,4をキューにいれます。

1 2 3 4

4.つぎにノード3に隣接しているノードをチェックします。
ノード3はノード7に隣接しているので、7をキューに入れます。

1 2 3 4 7

5.次はノード4の隣接ノードを探索します、ノート2とノード5が隣接していますが、
ノード2は探索済みなので、キューには入れません。

1 2 3 4 7 5

6.以後、これを繰り返し、キューに入れた数(end)と、探索を開始する始点(head)が
一致した時点で探索終了です。

幅優先探索のアルゴリズムをc++で学ぶ

最後に、c++で書かれたプログラムを載せます。
ソースは上記のグラフを元にしたものです。

#include <queue>
using namespace std;

#define MAX 8
bool visited[MAX];

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

queue<int>q;

int main() {
    // queueに入れる
    q.push(0);
    visited[0] = true;
    
    do{
        int i = q.front();
        q.pop();
        for(int j = 0;j < MAX;++j){
            // 経路発見
            if(GRAPH[i][j] == 1 && !visited[j]){        
                printf("%d->%d ",i + 1,j + 1);
                q.push(j);
                visited[j] = true;
            }
        }
    }while(!q.empty());
}