深さ優先探索 Depth First Search (DFS)

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

• グラフの連結性（connectivity）
• グラフの連結成分（connected component）
• グラフの強連結成分（storongly connected component）
• グラフの関節点（ariticulation points）
• グラフの brideges
• etc.

see-try-see

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

1.	最初に訪問するノードを決める（任意のノード）
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;
}