深さ優先探索 Depth First Search (DFS)
2006.04.21 00:01 グラフ 探索
Depth Frist Search (深さ優先探索)は、グラフの全てのノードをシステマティックに訪問するための、最も自然で基本的なアルゴリズムです。DFS は以下の例のような様々なグラフの問題に応用されます。
- グラフの連結性(connectivity)
- グラフの連結成分(connected component)
- グラフの強連結成分(storongly connected component)
- グラフの関節点(ariticulation points)
- グラフの brideges
- etc.
DFS は以下のようにノードを訪問します。
1. | 最初に訪問するノードを決める(任意のノード) |
2. | ノードを訪問した後、以下のようにして次に訪問するノードを探す |
そのノードに隣接した未訪問のノードがあれば、そのノードのどれか(任意のノードでよい)を訪問し、2 の処理へ
未訪問のノードがなければ、今訪問しているノードの前のノードに引き返して、2の処理の続きを行う(つまり、前のノードにおいて、次に訪問するノード探しの続きを行う) |
このアルゴリズムを実装するために必要なプログラミングテクニックが「再帰」であり、プログラムの雛形が以下のようになります。
void depthFirstSearch( int currentNode ){ currentNode を訪問済みとする ( currentNode に隣接しているノード nextNode を探す ){ nextNode が未訪問ならば depthFirstSearch( nextNode ); } }
隣接行列による DFS の実装例です。
001 #define MAX 1000 002 int size; 003 int adjMatrix[MAX][MAX]; // graph structure 004 bool visited[MAX]; 005 006 void dfs( int currentNode ){ 007 visited[ currentNode ] = true; 008 009 // perform some activities here 010 011 for ( int nextNode = 0; nextNode < size; nextNode++ ){ 012 if ( !adjMatrix[ currentNode ][ nextNode ] ) continue; 013 if ( !visited[ nextNode ] ){ 014 dfs( nextNode ); 015 } 016 } 017 } 018 019 void depthFirstSearch(){ 020 for ( int i = 0; i < size; i++ ) visited[ i ] = false; 021 int startNode = 0; 022 023 dfs( startNode ); 024 } 025 026 void inputGraph(){ 027 cin >> size; 028 029 for ( int i = 0; i < size; i++ ){ 030 for ( int j = 0; j < size; j++ ){ 031 adjMatrix[i][j] = 0; 032 } 033 } 034 035 int source, target; 036 // input based on adjMatrix 037 for ( int source = 0; source < size; source++ ){ 038 for ( int target = 0; target < size; target++ ){ 039 cin >> adjMatrix[source][target]; 040 } 041 } 042 } 043 044 int main(){ 045 inputGraph(); 046 depthFirstSearch(); 047 048 return 0; 049 }
隣接リストによる DFS の実装例です。
class Graph{ private: vector<vector<int> > adjList; vector<vector<int>::iterator> pos; public: static const int END = -1; Graph(){} Graph( int n ) { resize(n); } void resize( int n ){ adjList.resize(n), pos.resize(n); for ( int i = 0; i < n; i++ ){ adjList[i].clear(); } } int size(){ return adjList.size(); } void insert( int source, int target ){ adjList[source].push_back( target ); } int next( int source ){ if ( pos[source] == adjList[source].end() ) return END; return *pos[source]++; } void reset( int i ){ pos[i] = adjList[i].begin(); } void reset(){ for ( int i = 0; i < size(); i++ ) reset(i); } }; Graph graph = Graph( SIZE ); // graph structure bool visited[ SIZE ]; void dfs( int currentNode ){ visited[ currentNode ] = true; int nextNode; while ( (nextNode = graph.next( currentNode )) != graph.END ){ if ( visited[ nextNode ] ) continue; dfs( nextNode ); } } void depthFirstSearchScheme(){ for ( int i = 0; i < SIZE; i++ ) visited[ i ] = false; int startNode = 0; graph.reset(); dfs( startNode ); } void inputGraph(){ int source, target; // input based on adjList cout << "input edges: "; while (1){ cin >> source >> target; if ( source == -1 && target == -1 ) break; graph.insert( source, target ); graph.insert( target, source ); } } int main(){ inputGraph(); depthFirstSearchScheme(); return 0; }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |