寻路算法

图的寻路算法也可以通过深度优先遍历 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 >= && s < G. V ( ) ;
    visited = new boolean [ G. V ( ) ] ;
    from = new int [ G. V ( ) ] ;
    for ( int i = ; i < G. V ( ) ; i ++ ) {
        visited [ i ] = false ;
        from [ i ] = - 1 ;
    }
    this . s = s ;
    // 寻路算法
    dfs ( s ) ;
}
...

那么判断 s 点到 w 点是否有路径，只要查询 visited 对应数组值即可。

...
boolean hasPath ( int w ) {
    assert w >= && 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/yssmx/graph/Path.java 文件代码：

package yssmx.graph ;

import yssmx.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 >= && s < G. V ( ) ;
        visited = new boolean [ G. V ( ) ] ;
        from = new int [ G. V ( ) ] ;
        for ( int i = ; i < G. V ( ) ; i ++ ) {
            visited [ i ] = false ;
            from [ i ] = - 1 ;
        }
        this . s = s ;
        // 寻路算法
        dfs ( s ) ;
    }

    // 查询从s点到w点是否有路径
    boolean hasPath ( int w ) {
        assert w >= && 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 = ; i < vec. size ( ) ; i ++ ) {
            System . out . print ( vec. elementAt ( i ) ) ;
            if ( i == vec. size ( ) - 1 )
                System . out . println ( ) ;
            else
                System . out . print ( " -> " ) ;
        }
    }
}