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) | ↑ページトップ |




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

2006.04.21 00:01  グラフ 探索

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


see-try-see

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) | ↑ページトップ |




隣接リスト

2006.04.21 00:00  グラフ

各ノードが、そのノードに隣接するノードの番号のリストを持ちます。重みつきグラフの場合は、番号だけではなく重みもリストの要素に追加されます。リストの最後に番兵を設置しておくと便利です。

有向グラフ
DUList.gif


重みつき有向グラフ
DWList.gif


隣接リスト表現の特徴
  • エッジの数に比例したメモリしか必要としない
  • ノード u とノード v の関係を調べるには、リストを探索しなければならない
  • エッジの追加・削除の操作が難しく、効率的に行えない
  • 実装がやや難しい

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




隣接行列

2006.04.21 00:00  グラフ

行列という名の通り、グラフを2次元配列で表現します。配列のインデックスが各ノードの番号に対応します。例えば、この2次元配列を M とすると、M[i][j] がノード i とノード j の関係を表します。


無向グラフ
ノード i とノード j の間にエッジがある場合、M[i][j]M[j][i] の値を 1 とします。エッジがない場合は 0 とします。隣接行列は右上と左下が対照になります。

UUMatrix.gif


有向グラフ
ノード i からノード j へ向かってエッジがある場合、M[i][j] の値を 1 とします。エッジがない場合は 0 とします。

DUMatrix.gif


重みつき無向グラフ
ノード i とノード j の間に重さ w のエッジがある場合、M[i][j]M[j][i] の値を w とします。エッジがない場合は、問題上有り得ない値に設定します。例ではとしていますが、プログラムでは非常に大きな値に設定しておくと便利な場合が多いです。

UWMatrix.gif


重みつき有向グラフ
ノード i からノード j へ向かって重さ w のエッジがある場合、M[i][j] の値を w とします。エッジがない場合は、非常に大きな値に設定します。
DWMatrix.gif


隣接行列表現の特徴
  • M[u][v] でエッジを参照できるので、ノード u とノード v の関係を定数時間でチェックすることができる
  • エッジの追加や削除が簡単かつ効率的(定数時間)
  • ノードの数が増えるとメモリをかなり消費する。ノード数を n とすると、n^2 のスペースが必要

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