图的深度优先遍历寻路算法

图的深度优先遍历寻路算法

看注释吧

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
package GraphBasics;

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

/**
* @ Description:深度优先遍历寻路算法
* @ Date: Created in 12:53 2018/8/1
* @ Author: Anthony_Duan
*/
public class Path {
private Graph G;
private int s;
private boolean[] visited;
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<>();
//通过from数组逆向查找到从s到w的路径,存到栈中
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点的路径
void showPath(int w) {
assert hasPath(w);
Vector<Integer> vec = path(w);
for (int i = 0; i < vec.size(); i++) {
System.out.println(vec.elementAt(i));
if (i == vec.size() - 1) {
System.out.println();
} else {
System.out.print("->");
}
}
}
}
-------------End Of This ArticleThank You For Reading-------------