寻路算法

图的寻路算法也可以通过深度优先遍历 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/haodaima/graph/Path.java 文件代码：

package haodaima.graph;

import haodaima.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(" -> ");
        }
    }
}