You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
127 lines
3.8 KiB
Java
127 lines
3.8 KiB
Java
|
|
|
|
import edu.princeton.cs.introcs.In;
|
|
import edu.princeton.cs.introcs.StdOut;
|
|
|
|
/*************************************************************************
|
|
* Compilation: javac DirectedDFS.java
|
|
* Execution: java DirectedDFS V E
|
|
* Dependencies: Digraph.java Bag.java In.java StdOut.java
|
|
* Data files: http://www.cs.princeton.edu/algs4/42directed/tinyDG.txt
|
|
*
|
|
* Determine single-source or multiple-source reachability in a digraph
|
|
* using depth first search.
|
|
* Runs in O(E + V) time.
|
|
*
|
|
* % java DirectedDFS tinyDG.txt 1
|
|
* 1
|
|
*
|
|
* % java DirectedDFS tinyDG.txt 2
|
|
* 0 1 2 3 4 5
|
|
*
|
|
* % java DirectedDFS tinyDG.txt 1 2 6
|
|
* 0 1 2 3 4 5 6 8 9 10 11 12
|
|
*
|
|
*************************************************************************/
|
|
/**
|
|
* The DirectedDFS class represents a data type for
|
|
* determining the vertices reachable from a given source vertex s
|
|
* (or set of source vertices) in a digraph. For versions that find the paths,
|
|
* see {@link DepthFirstDirectedPaths} and {@link BreadthFirstDirectedPaths}.
|
|
*
|
|
* This implementation uses depth-first search.
|
|
* The constructor takes time proportional to V + E
|
|
* (in the worst case),
|
|
* where V is the number of vertices and E is the number of edges.
|
|
*
|
|
* For additional documentation, see <a href="/algs4/41graph">Section 4.1</a> of
|
|
* Algorithms, 4th Edition 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 G that are
|
|
* reachable from the source vertex s .
|
|
* @param G the digraph
|
|
* @param s the source vertex
|
|
*/
|
|
public DirectedDFS(Digraph G, int s) {
|
|
marked = new boolean[G.V()];
|
|
dfs(G, s);
|
|
}
|
|
|
|
/**
|
|
* Computes the vertices in digraph G that are
|
|
* connected to any of the source vertices sources .
|
|
* @param G the graph
|
|
* @param sources the source vertices
|
|
*/
|
|
public DirectedDFS(Digraph G, Iterable<Integer> sources) {
|
|
marked = new boolean[G.V()];
|
|
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 v ?
|
|
* @param v the vertex
|
|
* @return true if there is a directed path, false otherwise
|
|
*/
|
|
public boolean marked(int 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;
|
|
}
|
|
|
|
/**
|
|
* Unit tests the DirectedDFS data type.
|
|
*/
|
|
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();
|
|
}
|
|
|
|
}
|