fc2ブログ



連結成分 Connected Components

2007.03.07 18:08  グラフ 探索

connectedComponents.gif


001 #define MAX 1000
002 int size;
003 int adjMatrix[MAX][MAX]; // graph structure
004 bool visited[MAX];
005 int group[MAX];
006 
007 void visit( int currentNode, int id ){
008     visited[currentNode] = true;
009     group[currentNode] = id;
010     
011     for ( int nextNode = 0; nextNode < size; nextNode++ ){
012         if ( !adjMatrix[currentNode][nextNode] ) continue;
013         if ( !visited[nextNode] ){
014             visit( nextNode, id );
015         }
016     }
017 }
018 
019 void depthFirstSearch(){
020     for ( int i = 0; i < size; i++ ) visited[ i ] = false;
021     int number = 1;
022     for ( int startNode = 0; startNode < size; startNode++ ){
023         if ( !visited[startNode] ) visit( startNode, number++ );
024     }
025 }
026 
027 void inputGraph(){
028     cin >> size;
029     
030     for ( int i = 0; i < size; i++ ){
031         for ( int j = 0; j < size; j++ ){
032             adjMatrix[i][j] = 0;
033         }
034     }
035     
036     int source, target;
037     // input based on adjMatrix
038     for ( int source = 0; source < size; source++ ){
039         for ( int target = 0; target < size; target++ ){
040             cin >> adjMatrix[source][target];
041         }
042     }
043 }
044 
045 int main(){
046     inputGraph();
047     depthFirstSearch();
048     
049     for ( int i = 0; i < size; i++ ){
050         cout << i << " " << group[i] << endl;
051     }
052     return 0;
053 }
スポンサーサイト



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




単一始点最短経路 (重みなし)

2006.04.26 22:51  グラフ 探索

bfsBack.gif


001 #define MAX 1000
002 int size;
003 int adjMatrix[MAX][MAX]; // graph structure
004 
005 void breadthFirstSearch( int source ){
006     queue< int > Q;
007     bool visited[MAX];
008     int dist[MAX];
009     int pi[MAX];
010     
011     for ( int i = 0; i < size; i++ ) {
012         visited[i] = false;
013         dist[i] = INT_MAX;
014     }
015     int currentNode = source;
016     
017     Q.push( currentNode );
018     visited[currentNode] = true;
019     dist[currentNode] = 0;
020     pi[currentNode] = -1;
021     
022     while ( !Q.empty() ){
023         currentNode = Q.front(), Q.pop();
024         
025         for ( int nextNode = 0; nextNode < size; nextNode++ ){
026             if ( !adjMatrix[currentNode][nextNode] ) continue;
027             if ( !visited[nextNode] ){
028                 visited[nextNode] = true;
029                 dist[nextNode] = dist[currentNode] + 1;
030                 pi[nextNode] = currentNode;
031                 Q.push( nextNode );
032             }
033         }
034     }
035 }

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




Ariticulation Points 関節点 切断点

2006.04.26 22:50  グラフ 探索

連結グラフGにおいて、ノード u と、 u から出ている全てのエッジを削除して得られる部分グラフが、もはや連結でなくなってしまうとき、ノード u をグラフ GArticulation Point (関節点または切断点)といいます。例えば、以下に示すグラフで、赤いノードが Articulation Points です。


articulationPoints.gif

連結グラフの Articulation Points を検出することは、実際の問題で非常に重要になります。たとえば、コンピュータの通信網をグラフとしてモデル化した場合、この通信網の Articulation Points になっているコンピュータが故障してしまえば、その通信網は機能しなくなってしまいます。一方、Articulation Points が存在しない連結グラフになれば、たとえ1つのコンピュータが故障しても、他の全てのコンピュータは通信ができることが保障されます。

以下に示す Depth First Search (DFS) の応用によって、連結グラフ G の全ての Articulation Points を検出することができます。

G の任意のノードをスタート点として、DFS を行う。グラフ G の各ノード u に対して、DFS における訪問の順番 prenum[u] を記録します。
DFS によって生成される木(DFS Tree)における u の親 parent[u] を記録します。ここで、この DFS Tree を T とします。
各ノード u に対して、以下のうちの最小値として lowest[u] を計算すます。
i.prenum[u]
ii.GBack edge (u, v) が存在するとき、ノード v における prenum[v]. Back edge (u, v) とは、ノード u から T に属するノード v に向かう T に属さない G のエッジです 
iii.T に属するノード u のすべての子供 x に対する lowest[x]
Articulation Points は以下のように決定されます
(1)T のルート r が2つ以上の子供をもつとき(必要十分条件)、 rG の Articulation Point です。
(2)各ノード u において、u の親 parent[u] p とすると、prenum[p] ≦ lowest[u] ならば(必要十分条件)、p は Articulation Point である(p がルートの場合は (1) を適用します)。

具体的な例を考えてみましょう。

Example 1

以下の図はグラフ G と、G をノード 0 から DFS を行った DFS Tree T を表しています。T において、Back edges は点線で表されていて、各ノードの左側にそれぞれ prenum[u]lowest[u] が示されています。

prenum[u] は DFS において各ノード u が訪問される順番(pre-order): 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 という順番で記録されます。

lowest[u] は DFS において各ノード u の訪問が"終了"する順番(post-order): 4 → 7 → 6 → 5 → 3 → 2 → 1 → 0 という順番で"決定"されます。lowest[u] がどのように"更新"されていくかは、後ほど説明します。

Graph : G DFS Tree : T
artPointG1.gif
artPointT1.gif


(1) より
T のルートであるノード 0 の子供の数は 1 つなので、ノード 0 は Articulation Point ではありません。

(2) より
各ノード u の親を p とすると prenum[p] ≦ lowest[u] を満たすかをチェックします。

case 1. ノード 5 (親がノード 3)に注目します
prenum[3] ≦ lowest[5] を満たす (4 ≦ 6)ので、ノード 3 が Articulation Point になります。つまり、ノード 5 またはノード 5 から Tのノードを任意の数だけ下にたどったノード 5 の子孫から、ノード 3 の祖先へのエッジがないことを示しています。

case 2. ノード 2 (親がノード 1)に注目します
prenum[1] ≦ lowest[2] を満たさないので、ノード 1 は Articulation Point ではありません。つまり、ノード 2 またはノード 2 の子孫から、ノード 1 の祖先へのエッジが存在していることを示しています。

以下の例も考えてみましょう。

Example 2

Graph : G DFS Tree : T
artPointG2.gif
artPointT2.gif


#define SIZE 1000

Graph graph = Graph( SIZE ); // graph structure
bool visited[SIZE];

int prenum[SIZE]; int parent[SIZE]; int lowest[SIZE]; int timer;

void dfs( int current, int prev ){

    // ノード current を訪問した直後の処理
    prenum[current] = timer; lowest[current] = timer;
    timer++;

    visited[current] = true;

    int next;

    while ( (next = graph.next( current )) != graph.END ){
        if ( !visited[next] ){
            // ノード current からノード next へ訪問する直前の処理
            parent[next] = current;

            dfs( next, current );

            // ノード next の探索が終了した直後の処理
            lowest[current] = min( lowest[current], lowest[next] );
        } else if ( next != prev ){
            // エッジ current --> next が Back-edge の場合の処理
            lowest[current] = min( lowest[current], prenum[next] );
        }
    }

    // ノード current の探索が終了した直後の処理


}

void depthFirstSearchScheme(){
    for ( int i = 0; i < SIZE; i++ ) visited[ i ] = false;
    int root = 0;
    timer = 1;
      
    graph.reset();

    // lowest の計算
    dfs( root, -1 );
}

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




幅優先探索木 Breadth First Search Tree

2006.04.26 22:50  グラフ 探索

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




深さ優先探索木 Depth First Search Tree

2006.04.26 22:49  グラフ 探索

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




幅優先探索 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) | ↑ページトップ |