无权图的广度优先遍历寻找单源最短路径

无权图的广度优先遍历寻找单源最短路径

直接看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package GraphBasics;

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

/**
* @ Description: 寻找s到w的最短路径
* @ Date: Created in 13:14 2018/8/1
* @ Author: Anthony_Duan
*/
public class ShortestPath {
private Graph G;
private int s;
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<>();

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);

// 通过from数组逆向查找到从s到w的路径, 存放到栈中
Stack<Integer> s = new Stack<>();

int p = w;
while (p != -1) {
s.push(p);
p = from[p];
}

// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector<Integer> res = new Vector<>();
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];
}
}
-------------End Of This ArticleThank You For Reading-------------