ALGORITHM NOTE

Shortest path problem (最短経路問題) とは、重みつきグラフ G(V, E) において、ある与えられたノード x, y を接続する path の中で、エッジの重みの総和が最小である path を求める問題です。この問題には、様々な応用がありますが、以下の２つが重要です。

Single Source Shortest Path Problem (単一始点最短経路)

G(V, E) をエッジのコスト（長さ）が非負である重みつきグラフとし、s を、G のノードとします。ただし、s から G の全てのノードに対して経路があるものとします。このとき、s を根とし、s から G の全てのノードへの最短経路を包含する G の spanning tree T が存在します。このような tree を shortest path spanning tree といいます。以下に例を示します。

Kruskal's Algorithm は、グラフ G(V, E) の MST を求めるためのアルゴリズムです。これも Greedy Algorithm で、各計算ステップで、最も適したエッジを選び、MST を求めます。このアルゴリズムを実装するために必要なデータ構造が Disjoint Sets です。Kruskal's Algorithm は以下のように実装します。

class edge{
    public:
    int source, target;
    double cost;
    edge(){}
    edge( int source, int target, double cost ):
    source(source), target(target), cost(cost){}
    
    bool operator < ( const edge &e ) const{
        return cost < e.cost;
    }
};

int N;
vector<edge> edges;

void kruskal( vector<edge> &mst ){
    
    sort( edges.begin(), edges.end() );
    
    DisjointSet dset = DisjointSet( N );
    
    for ( int i = 0; i < N; i++ ) dset.makeSet( i );
    
    int source, target;
    for ( int i = 0; i < edges.size(); i++ ){
        edge e = edges[i];
        if ( dset.findSet( e.source ) != dset.findSet( e.target ) ){
            mst.push_back( e );
            dset.union( e.source, e.target );
        }
    }
}

Prim's Algorithm は、グラフ G(V, E) の最小全域木 (MST) を求めるための、最も一般的なアルゴリズムです。基本的な考え方は以下のようになります。

このアルゴリズムを実装するポイントは、各選択ステップで "どのように最小の重みをもつエッジを記録するか" です。Prim's Algorithm は以下のように実装します。

(cost[v]、pi[v]) には、T に属するノード u と、V - T に属するノード v をつなぐエッジの中で、重みが最小のエッジの情報が記録されます。cost[v] には重みを、pi[v] には、ノード u、つまり MST におけるノード v の親が記録されます。従って、各ステップで、ノード u を選択するという操作は、「T に属するノードと V - T に属するノードをつなぐエッジの中で、重みが最小のもの」を選ぶ操作に相当します。 また、u が選ばれた時点で、エッジ ( u, pi[u] ) が MST を構成するエッジとなります。

001 int N;
002 int M[MAX][MAX];
003 
004 void prim(){
005     dist = 0.0;
006     
007     bool visited[MAX];
008     int cost[MAX];
009     int pi[MAX];
010     
011     for ( int i = 0; i < N; i++ ){
012         visited[i] = false;
013         cost[i] = INT_MAX;
014     }
015     
016     cost[0] = 0;
017     pi[0] = -1;
018     
019     while ( 1 ){
020         int mincost = INT_MAX;
021         int u;
022         // cost が最小となるノード u を選択する
023         for ( int i = 0; i < N; i++ ){
024             if ( !visited[i] && cost[i] < mincost ){
025                 mincost = cost[i];
026                 u = i;
027             }
028         }
029         
030         // すべてのノードが MST に含まれたとき
031         if ( mincost == INT_MAX ) break;
032         
033         visited[u] = true;
034         
035         for ( int v = 0; v < N; v++ ){
036             if ( visited[v] || M[u][v] == INT_MAX ) continue;
037             // 更新処理
038             if ( M[u][v] < cost[v] ){
039                 cost[v] = M[u][v];
040                 pi[v] = u;
041             }
042         }
043     }
044 }

多くの実用的なアルゴリズムは、「解の一部を選択する計算ステップの繰り返し」という構成になっています。Greedy Algorithm （貪欲アルゴリズム、よくばり法）は、各計算ステップで、局所的に最適（その時点で最も最適と思われるもの）な選択を繰り返し、最終的に大域的な最適解を求める方法です。

さらに一般化すると、Greedy Algorithm では、候補の集合 C、すでに選択された要素の集合 S、各ステップで、まだ選ばれていない候補の中から最適とされる要素を決定する選択関数 F、から成ります。最初は、選択された要素の集合 S は空で、その後１ステップごとに、候補の集合 C から選択関数 F によって決定された最適な要素を S に追加します。選択された要素は候補 C から取り除かれます。

例えば、これから紹介するグラフの最小全域木を求めるための Prim's Algorithm や Kruskal's Algorithm、グラフの単一始点最短経路を求めるための Dijkstra's Algorithm はGreedy Algorithm に分類されます。

この中でも、Prim's Algorithm と Dijkstra's Algorithm は同様の計算スキームをもち、以下のように動作します。

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

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

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

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

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
	→

(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
	→

#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 );
}

• グラフの連結性（connectivity）
• グラフの連結成分（connected component）
• グラフの最短経路問題（重み無し）
• Maximum flow （最大流）
• 探索
• etc.

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

このアルゴリズムを実装するためには、FIFO (First In First Out)の仕組みをもつキューのデータ構造が必要であり、プログラムの雛形が以下のようになります。

void breadthFirstSearch(){
    
　　最初に訪問するノードをキューに入れる

    while ( キューが空でない間 ){
        キューの先頭からノード currentNode を取り出す

　　　　( currentNode に隣接しているノード nextNode を探す ){
        
            nextNode が未訪問ならば nextNode を訪問済みとし、
            キューに入れる

        }
    }
}

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 }

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

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

このアルゴリズムを実装するために必要なプログラミングテクニックが「再帰」であり、プログラムの雛形が以下のようになります。

void depthFirstSearch( int currentNode ){
    
    currentNode を訪問済みとする

    ( currentNode に隣接しているノード nextNode を探す ){

        nextNode が未訪問ならば depthFirstSearch( nextNode );

    }
}

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 }

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;
}

	各計算ステップにおいて、配列は「ソート済みの部分」と「未ソートの部分」とに分けられます。
	1.「未ソートの部分」から最小の要素を探します。
	2. 選ばれた最小の要素と未ソートの部分の先頭の要素を交換します。
	1. 2. を未ソートの部分がなくなるまで繰り返します。

1. 初期状態は全ての要素が未ソートの部分に属します。 2. 未ソートの部分から最小値2を選択し、未ソートの部分の先頭7と交換します。 3. 未ソートの部分から最小値3を選択し、未ソートの部分の先頭5と交換します。 4. 未ソートの部分から最小値5を選択し、未ソートの部分の先頭11と交換します。 5. 未ソートの部分から最小値6を選択し、未ソートの部分の先頭8と交換します。 6. 未ソートの部分から最小値7を選択し、未ソートの部分の先頭12と交換します。 7. 未ソートの部分から最小値8を選択し、未ソートの部分の先頭11と交換します。 8. 未ソートの部分から最小値11を選択し、未ソートの部分の先頭12と交換します。 9. ソートが完了します。

#include<iostream>
using namespace std;

#define MAX 100

void selectionSort( int size, int data[]){
    for ( int front = 0; front < size - 1; front++ ){
        // 最小値のインデックスを探す
        int minIndex = front; 
        for ( int j = front + 1; j < size; j++ ){
            if ( data[j] < data[minIndex] ) minIndex = j;
        }
        // 未ソート部分の先頭と最小値を交換
        int tmp = data[front];
        data[front] = data[minIndex];
        data[minIndex] = tmp;
    }
}

• 安定なソート
• ソートのアルゴリズム
• バブルソート
• 選択ソート
• マージソート

初期化: head = tailのときキューが空になります。初期値はhead = tail = 0とします。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 3 ）。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 7 ）。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 1 ）。 dequeue: headが指す要素を取り出し、headを1増やします （例: 3を取り出す）。 enqueue(x): tailが指す場所にxを追加し、tailを1増やします （例: x = 8 ）。 dequeue: headが指す要素を取り出し、headを1増やします （例: 7を取り出す）

#include<iostream>
#include<string>
using namespace std;

#define MAX 100

class Queue{
    private:
    int buffer[MAX];
    int head, tail;

    public:
    Queue(){
        initialize();
    }

    void initialize(){
        head = tail = 0;
    }

    bool isEmpty(){
        return ( head == tail );
    }

    bool isFull(){
        return ( head == tail + 1 );
    }

    void enqueue( int x ){
        if ( isFull() ){
            cout << "overflow" << endl;
            return;
        } else {
            buffer[tail] = x;
            if ( tail + 1 == MAX ) tail = 0; // 循環
            else tail++;
        }
    }

    int dequeue(){
        if ( isEmpty() ){
            cout << "underflow" << endl;
        } else {
            int x = buffer[head];
            if ( head + 1 == MAX ) head = 0; // 循環
            else head++;
            return x;
        }
    }
};

int main(void){
    Queue queue;
    int x;
    string command;

    while (1){
            cin >> command;
            if ( command == "enqueue" ) {
                cin >> x;
                queue.enqueue(x);
            } else if ( command == "dequeue" ){
                cout << queue.dequeue() << endl;
            } else break;
    }

    return 0;
}

初期化: top = 0としてスタックを空にします。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 3 ）。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 12 ）。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 1 ）。 pop: topが指している要素を取り出し、topを1減らします （例: 1を取り出す）。 pop: topが指している要素を取り出し、topを1減らします （例: 12を取り出す）。 push(x): top を1増やし、topが指す場所にxを追加します （例: x = 5 ）

#include<iostream>
#include<string>
using namespace std;

#define MAX 5

class Stack{
    private:
    int buffer[MAX];
    int top;

    public:
    Stack(){
        initialize();
    }

    void initialize(){
        top = 0;
    }

    bool isEmpty(){
        return ( top == 0 );
    }

    bool isFull(){
        return  ( top >= MAX );
    }

    void push( int x ){
        if ( isFull() ){
            cout << "overflow" << endl;
        } else {
            top++;
            buffer[top] = x;
        }
    }

    int pop(){
        if ( isEmpty() ) {
            cout << "underflow" << endl;
        } else {
            int x = buffer[top];
            top--;
            return x;
        }
    }
};

int main(void){
    Stack stack;
    int x;
    string command;

    while (1){
        cin >> command;
        if ( command == "push" ) {
            cin >> x;
            stack.push(x);
        } else if ( command == "pop" ){
            cout << stack.pop() << endl;
        } else break;
    }

    return 0;
}

#include<stack>

using namespace std;

main(){
    stack<int> st;
    st.push(1);
    st.push(7);
    st.push(3);
    cout << st.top() << endl; st.pop();
    cout << st.top() << endl; st.pop();
    st.push(5);
    cout << st.top() << endl; st.pop();
    cout << st.top() << endl; st.pop();
}

• 「データの集合」
• 「データの集合に対する操作」
• 「データをルールに従って正しく保つための制約」

• スタック Stack
• キュー Queue
• 優先順位キュー Priority Queue
• Disjoint Sets
• 二分探索木
• etc.