fc2ブログ



幅優先探索 Breadth First Search (BFS)

2006.04.21 00:01  グラフ 探索

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

  • グラフの連結性(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 }
スポンサーサイト



| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ