幅優先探索 Breadth First Search (BFS)
2006.04.21 00:01 グラフ 探索
Breadth Frist Search (幅優先探索)は、グラフの全てのノードをシステマティックに訪問するためのアルゴリズムの1つで、以下の例のような様々なグラフの問題に応用されます。
see-try-see
隣接行列による BFS の実装例です。
- グラフの連結性(connectivity)
- グラフの連結成分(connected component)
- グラフの最短経路問題(重み無し)
- Maximum flow (最大流)
- 探索
- etc.
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) | ↑ページトップ |