寻路算法-开发文档-JsSaaS开发平台

系统、网站、API站点，简单高效开发

数据结构

数据结构与算法插入排序希尔排序归并排序随机化快速排序双路快速排序三路排序算法排序算法衍生问题

堆

堆的基本存储堆的 shift up 堆的 shift down 基础堆排序优化堆排序索引堆及其优化

二分搜索树

二分搜索树二分搜索树节点的插入二分搜索树节点的查找二分搜索树深度优先遍历二分搜索树层序遍历二分搜索树节点删除二分搜索树的特性

并查集

并查集基础并查集快速查找并查集快速合并并查集 size 的优化并查集 rank 的优化并查集路径压缩

图论

图论基础和表示相邻节点迭代器深度优先遍历与连通分量寻路算法广度优先遍历与最短路径

寻路算法

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

package runoob.graph;

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