-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDirectedDFS.java
More file actions
46 lines (39 loc) · 1.15 KB
/
Copy pathDirectedDFS.java
File metadata and controls
46 lines (39 loc) · 1.15 KB
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
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.Interval1D;
import edu.princeton.cs.algs4.StdOut;
/**
* Created by mofma on 2017/5/2.
*/
public class DirectedDFS {
private boolean[] marked;
private void dfs(Digraph G, int v){
marked[v] = true;
for(int w: G.adj(v)) {
if (!marked[w]) dfs(G,w);
}
}
public DirectedDFS(Digraph G, int s){
marked = new boolean[G.V()];
dfs(G,s);
}
public DirectedDFS(Digraph G, Iterable<Integer> srcs){
marked = new boolean[G.V()];
for(int s : srcs)
if(!marked[s]) dfs(G,s);
}
public boolean marked(int v) {
return marked[v];
}
public static void main(String[] args) {
Digraph G = new Digraph(new In(args[0]));
Bag<Integer> srcs = new Bag<Integer>();
for(int i = 1; i< args.length; i++) {
srcs.add(Integer.parseInt(args[i]));
}
DirectedDFS reachable = new DirectedDFS(G, srcs);
for(int v = 0; v < G.V(); v++)
if(reachable.marked[v]) StdOut.print(v + " ");
StdOut.println();
}
}