-
Notifications
You must be signed in to change notification settings - Fork 0
/
DepthFirstPaths.java
101 lines (93 loc) · 1.68 KB
/
DepthFirstPaths.java
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
package fundamentals.graph;
import java.util.Stack;
/**
* The type Depth first paths.
*/
public class DepthFirstPaths {
//to store visit status of vertex
private boolean[] marked;
//to store the last vertex, e.g. if 0 can reach 2 by vertex 1 (0->1->2),then store 1 at edgeTo[2].
/*
* e.g.
*
* paths:
* 0->1
* 1->6
* 0->2
* 2->3
* 2->4
* 4->5
*
* the graph to a tree reachable represent:
*
* 0
* 1 2
* 6 3 4
* 5
*
* if use 0 as start vertex,the array of edgeTo data as follows;
*
* edgeTo as follows:
* index->last reachable vertex
* 0->0
* 1->0
* 2->0
* 3->2
* 4->2
* 5->4
* 6->1
*
* edgeTo----> {0,0,0,2,2,4,1}
*
* */
private int[] edgeTo;//key thinking
//start vertex
private final int s;
/**
* Instantiates a new Depth first paths.
*
* @param G the g
* @param s the s
*/
public DepthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
dfs(G, s);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
}
/**
* Has path to boolean.
*
* @param v the v
* @return the boolean
*/
public boolean hasPathTo(int v) {
return marked[v];
}
/**
* Path to iterable.
*
* @param v the v
* @return the iterable
*/
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<Integer> path = new Stack<Integer>();
for (int x = v; x != s; x = edgeTo[x]) {
path.push(x);
}
path.push(s);
return path;
}
}