経路探索アルゴリズム

グラフの経路探索アルゴリズムは深さ優先探索（DFS）でも実装できます。グラフ graph の開始点 s から他の点までの経路を探すために、前の小節の実装クラスに経路を記録するグローバル変数 from 配列を追加します。from[i] は、探索された経路における i の前のノードを表します。

まずコンストラクタが経路探索アルゴリズムの初期条件を初期化し、from = new int[G.V()]とfrom = new int[G.V()]ループ内でデフォルト値を設定します。visited 配列はすべて false に、from 配列はすべて -1 にします。その後、開始ノードに対して DFS の再帰処理を行います。

...
// コンストラクタ、経路探索アルゴリズム、グラフ graph の s 点から他の点への経路を探す
public Path(Graph graph, int s){
    // アルゴリズムの初期化
    G = graph;
    assert s >= 0 && s < G.V();
    visited = new boolean[G.V()];
    from = new int[G.V()];
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        from[i] = -1;
    }
    this.s = s;
    // 経路探索アルゴリズム
    dfs(s);
}
...

では、s 点から w 点への経路が存在するかどうかを判断するには、visited の対応する配列の値を調べるだけでよい。

...
boolean hasPath(int w){
    assert w >= 0 && w < G.V();
    return visited[w];
}
...

s 点から w 点への具体的な経路を取得するには、path メソッドを使用して実装します。まず連結しているかどうかを判断し、hasPath メソッドを呼び出します。コンストラクタから、from 配列をたどって遡るだけで、すべての経路を見つけられることがわかります。

...
Vector<Integer> path(int w){
    assert hasPath(w) ;
    Stack<Integer> s = new Stack<Integer>();
    // from 配列を逆方向にたどって s から w への経路を見つけ、スタックに格納する
    int p = w;
    while( p != -1 ){
        s.push(p);
        p = from[p];
    }
    // スタックから要素を順に取り出し、s から w への順序どおりの経路を取得する
    Vector<Integer> res = new Vector<Integer>();
    while( !s.empty() )
        res.add( s.pop() );
    return res;
}
...

Java サンプルコード

ソースコードパッケージのダウンロード：Download

src/サンプル/graph/Path.java ファイルのコード：

package サンプル.graph;

import サンプル.graph.read.Graph;

import java.util.Stack;
import java.util.Vector;

/**
* 経路探索
 */
public class Path {
    // グラフの参照
    private Graph G;
    // 開始点
    private int s;
    // DFS の過程でノードが訪問済みかどうかを記録
    private boolean[] visited;
    // 経路を記録、from[i] は探索された経路における i の前のノードを表す
    private int[] from;

    // グラフの深さ優先探索
    private void dfs( int v ){
        visited[v] = true;
        for( int i : G.adj(v) )
            if( !visited[i] ){
                from[i] = v;
                dfs(i);
            }
    }

    // コンストラクタ、経路探索アルゴリズム、グラフ graph の s 点から他の点への経路を探す
    public Path(Graph graph, int s){
        // アルゴリズムの初期化
        G = graph;
        assert s >= 0 && s < G.V();
        visited = new boolean[G.V()];
        from = new int[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
        }
        this.s = s;
        // 経路探索アルゴリズム
        dfs(s);
    }

    // s 点から w 点への経路が存在するかを問い合わせる
    boolean hasPath(int w){
        assert w >= 0 && w < G.V();
        return visited[w];
    }

    // s 点から w 点への経路を問い合わせ、vec に格納する
    Vector<Integer> path(int w){

        assert hasPath(w) ;

        Stack<Integer> s = new Stack<Integer>();
        // from 配列を逆方向にたどって s から w への経路を見つけ、スタックに格納する
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // スタックから要素を順に取り出し、s から w への順序どおりの経路を取得する
        Vector<Integer> res = new Vector<Integer>();
        while( !s.empty() )
            res.add( s.pop() );

        return res;
    }

    // s 点から w 点への経路を出力する
    void showPath(int w){

        assert hasPath(w) ;

        Vector<Integer> vec = path(w);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )
                System.out.println();
            else
                System.out.print(" -> ");
        }
    }
}
その他の拡張