幅優先探索 Breadth First Search (BFS)

Breadth Frist Search (幅優先探索)は、グラフの全てのノードをシステマティックに訪問するためのアルゴリズムの１つで、以下の例のような様々なグラフの問題に応用されます。

• グラフの連結性（connectivity）
• グラフの連結成分（connected component）
• グラフの最短経路問題（重み無し）
• Maximum flow （最大流）
• 探索
• etc.

see-try-see

BFS は以下のようにノードを訪問します。

1.	最初に訪問するノードを決め、その番号をキュー（FIFO）に入れる
2.	キューの先頭からノード番号を取り出し、そのノードを訪問し、そのノードに隣接した未訪問である全てのノードの番号をキューに入れる。キューが空になるまで 2 を繰り返す

このアルゴリズムを実装するためには、FIFO (First In First Out)の仕組みをもつキューのデータ構造が必要であり、プログラムの雛形が以下のようになります。

void breadthFirstSearch(){
    
　　最初に訪問するノードをキューに入れる

    while ( キューが空でない間 ){
        キューの先頭からノード currentNode を取り出す

　　　　( currentNode に隣接しているノード nextNode を探す ){
        
            nextNode が未訪問ならば nextNode を訪問済みとし、
            キューに入れる

        }
    }
}

隣接行列による BFS の実装例です。

001 #define MAX 1000
002 int size;
003 int adjMatrix[ MAX ][ MAX ]; // graph structure
004 
005 void breadthFirstSearch(){
006     queue< int > Q;
007     bool visited[ MAX ];
008     for ( int i = 0; i < size; i++ ) visited[ i ] = false;
009     int currentNode = 0;
010     
011     Q.push( currentNode );
012     visited[ currentNode ] = true;
013     
014     while ( !Q.empty() ){
015         currentNode = Q.front(), Q.pop();
016         
017         cout << currentNode << endl;
018         
019         for ( int nextNode = 0; nextNode < size; nextNode++ ){
020             if ( !adjMatrix[ currentNode ][ nextNode ] ) continue;
021             if ( !visited[ nextNode ] ){
022                 visited[ nextNode ] = true;
023                 Q.push( nextNode );
024             }
025         }
026     }
027 }
028 
029 void inputGraph(){
030     cin >> size;
031     for ( int i = 0; i < size; i++ ){
032         for ( int j = 0; j < size; j++ ){
033             adjMatrix[i][j] = 0;
034         }
035     }
036     
037     int source, target;
038     for ( int i = 0; i < size; i++ ){
039         for ( int j = 0; j < size; j++ ){
040             cin >> adjMatrix[i][j];
041         }
042     }
043 }
044 
045 int main(){
046     inputGraph();
047     breadthFirstSearch();
048     
049     return 0;
050 }