forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDirectedDFS.java
More file actions
132 lines (118 loc) · 4.27 KB
/
Copy pathDirectedDFS.java
File metadata and controls
132 lines (118 loc) · 4.27 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
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/**
* The {@code DirectedDFS} class represents a data type for
* determining the vertices reachable from a given source vertex <em>s</em>
* (or set of source vertices) in a digraph. For versions that find the paths,
* see {@link DepthFirstDirectedPaths} and {@link BreadthFirstDirectedPaths}.
* <p>
* This implementation uses depth-first search.
* The constructor takes time proportional to <em>V</em> + <em>E</em>
* (in the worst case),
* where <em>V</em> is the number of vertices and <em>E</em> is the number of edges.
* <p>
* For additional documentation,
* see <a href="http://algs4.cs.princeton.edu/42digraph">Section 4.2</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class DirectedDFS {
private boolean[] marked; // marked[v] = true if v is reachable
// from source (or sources)
private int count; // number of vertices reachable from s
/**
* Computes the vertices in digraph {@code G} that are
* reachable from the source vertex {@code s}.
* @param G the digraph
* @param s the source vertex
* @throws IllegalArgumentException unless {@code 0 <= s < V}
*/
public DirectedDFS(Digraph G, int s) {
marked = new boolean[G.V()];
validateVertex(s);
dfs(G, s);
}
/**
* Computes the vertices in digraph {@code G} that are
* connected to any of the source vertices {@code sources}.
* @param G the graph
* @param sources the source vertices
* @throws IllegalArgumentException unless {@code 0 <= s < V}
* for each vertex {@code s} in {@code sources}
*/
public DirectedDFS(Digraph G, Iterable<Integer> sources) {
marked = new boolean[G.V()];
validateVertices(sources);
for (int v : sources) {
if (!marked[v]) dfs(G, v);
}
}
private void dfs(Digraph G, int v) {
count++;
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) dfs(G, w);
}
}
/**
* Is there a directed path from the source vertex (or any
* of the source vertices) and vertex {@code v}?
* @param v the vertex
* @return {@code true} if there is a directed path, {@code false} otherwise
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public boolean marked(int v) {
validateVertex(v);
return marked[v];
}
/**
* Returns the number of vertices reachable from the source vertex
* (or source vertices).
* @return the number of vertices reachable from the source vertex
* (or source vertices)
*/
public int count() {
return count;
}
// throw an IllegalArgumentException unless {@code 0 <= v < V}
private void validateVertex(int v) {
int V = marked.length;
if (v < 0 || v >= V)
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
}
// throw an IllegalArgumentException unless {@code 0 <= v < V}
private void validateVertices(Iterable<Integer> vertices) {
if (vertices == null) {
throw new IllegalArgumentException("argument is null");
}
int V = marked.length;
for (int v : vertices) {
if (v < 0 || v >= V) {
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
}
}
}
/**
* Unit tests the {@code DirectedDFS} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
// read in digraph from command-line argument
In in = new In(args[0]);
Digraph G = new Digraph(in);
// read in sources from command-line arguments
Bag<Integer> sources = new Bag<Integer>();
for (int i = 1; i < args.length; i++) {
int s = Integer.parseInt(args[i]);
sources.add(s);
}
// multiple-source reachability
DirectedDFS dfs = new DirectedDFS(G, sources);
// print out vertices reachable from sources
for (int v = 0; v < G.V(); v++) {
if (dfs.marked(v)) StdOut.print(v + " ");
}
StdOut.println();
}
}