广度优先遍历与最短路径-开发文档-JsSaaS开发平台

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

数据结构

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

堆

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

二分搜索树

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

并查集

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

图论

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

广度优先遍历与最短路径

广度优先遍历从某个顶点 v 出发，首先访问这个结点，并将其标记为已访问过，然后顺序访问结点v的所有未被访问的邻接点 {vi,..,vj} ，并将其标记为已访问过，然后将 {vi,...,vj} 中的每一个节点重复节点v的访问方法，直到所有结点都被访问完为止。

我们可以分为三个步骤：

（1）使用一个辅助队列 q，首先将顶点 v 入队，将其标记为已访问，然后循环检测队列是否为空。
（2）如果队列不为空，则取出队列第一个元素，并将与该元素相关联的所有未被访问的节点入队，将这些节点标记为已访问。
（3）如果队列为空，则说明已经按照广度优先遍历了所有的节点。

下图所示，右边蓝色表示从 0 开始遍历节点的顺序，下面是记录距离 0 的距离，可知广度优先遍历能求出无权图的最短路径。

下面用代码展示如何用广度优先遍历方式完成遍历，并且查询到最短路径。我们在上一小节代码的基础上增加一全局变量 ord 数组，记录路径中节点的次序。ord[i] 表示 i 节点在路径中的次序。同时构造函数做出相应调整，在遍历相邻节点时每访问一个未被访问的节点进行 ord[i] = ord[v] + 1记录距离。邻接表的广度优先遍历时间复杂度为 O(V+E)，邻接矩阵的时间复杂度为O(V^2)。

...
// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
public ShortestPath(Graph graph, int s){
// 算法初始化
G = graph;
assert s >= 0 && s < G.V();

visited = new boolean[G.V()];
from = new int[G.V()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// 无向图最短路径算法, 从s开始广度优先遍历整张图
LinkedList<Integer> q = new LinkedList<Integer>();
q.push( s );
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.pop();
for( int i : G.adj(v) )
if( !visited[i] ){
q.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}
...

查看从 s 点到 w 点的最短路径长度，若从 s 到 w 不可达，返回-1。

...
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
...

Java 实例代码

源码包下载：Download

src/runoob/graph/ShortestPath.java 文件代码：

package runoob.graph;

import runoob.graph.read.Graph;

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

/**
* 广度优先遍历与最短路径
*/
public class ShortestPath {
// 图的引用
private Graph G;
// 起始点
private int s;
// 记录dfs的过程中节点是否被访问
private boolean[] visited;
// 记录路径, from[i]表示查找的路径上i的上一个节点
private int[] from;
// 记录路径中节点的次序。ord[i]表示i节点在路径中的次序。
private int[] ord;
// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
public ShortestPath(Graph graph, int s){

// 算法初始化
G = graph;
assert s >= 0 && s < G.V();

visited = new boolean[G.V()];
from = new int[G.V()];
ord = new int[G.V()];
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this.s = s;
// 无向图最短路径算法, 从s开始广度优先遍历整张图
LinkedList<Integer> q = new LinkedList<Integer>();
q.push( s );
visited[s] = true;
ord[s] = 0;
while( !q.isEmpty() ){
int v = q.pop();
for( int i : G.adj(v) )
if( !visited[i] ){
q.push(i);
visited[i] = true;
from[i] = v;
ord[i] = ord[v] + 1;
}
}
}

// 查询从s点到w点是否有路径
public boolean hasPath(int w){
assert w >= 0 && w < G.V();
return visited[w];
}
// 查询从s点到w点的路径, 存放在vec中
public 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点的路径
public 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(" -> ");
}
}
// 查看从s点到w点的最短路径长度
// 若从s到w不可达，返回-1
public int length(int w){
assert w >= 0 && w < G.V();
return ord[w];
}
}