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.
131 lines
3.8 KiB
Java
131 lines
3.8 KiB
Java
|
|
|
|
import edu.princeton.cs.introcs.In;
|
|
import edu.princeton.cs.introcs.StdOut;
|
|
|
|
/*************************************************************************
|
|
* Compilation: javac DepthFirstDirectedPaths.java
|
|
* Execution: java DepthFirstDirectedPaths G s
|
|
* Dependencies: Digraph.java Stack.java
|
|
*
|
|
* Determine reachability in a digraph from a given vertex using
|
|
* depth first search.
|
|
* Runs in O(E + V) time.
|
|
*
|
|
* % tinyDG.txt 3
|
|
* 3 to 0: 3-5-4-2-0
|
|
* 3 to 1: 3-5-4-2-0-1
|
|
* 3 to 2: 3-5-4-2
|
|
* 3 to 3: 3
|
|
* 3 to 4: 3-5-4
|
|
* 3 to 5: 3-5
|
|
* 3 to 6: not connected
|
|
* 3 to 7: not connected
|
|
* 3 to 8: not connected
|
|
* 3 to 9: not connected
|
|
* 3 to 10: not connected
|
|
* 3 to 11: not connected
|
|
* 3 to 12: not connected
|
|
*
|
|
*************************************************************************/
|
|
|
|
/**
|
|
* The DepthFirstDirectedPaths class represents a data type for finding
|
|
* directed paths from a source vertex s to every
|
|
* other vertex in the digraph.
|
|
*
|
|
* This implementation uses depth-first search.
|
|
* The constructor takes time proportional to V + E ,
|
|
* where V is the number of vertices and E is the number of edges.
|
|
* It uses extra space (not including the graph) proportional to V .
|
|
*
|
|
* 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 DepthFirstDirectedPaths {
|
|
private boolean[] marked; // marked[v] = true if v is reachable from s
|
|
private int[] edgeTo; // edgeTo[v] = last edge on path from s to v
|
|
private final int s; // source vertex
|
|
|
|
/**
|
|
* Computes a directed path from s to every other vertex in digraph G .
|
|
* @param G the digraph
|
|
* @param s the source vertex
|
|
*/
|
|
public DepthFirstDirectedPaths(Digraph G, int s) {
|
|
marked = new boolean[G.V()];
|
|
edgeTo = new int[G.V()];
|
|
this.s = s;
|
|
dfs(G, s);
|
|
}
|
|
|
|
private void dfs(Digraph G, int v) {
|
|
marked[v] = true;
|
|
for (int w : G.adj(v)) {
|
|
if (!marked[w]) {
|
|
edgeTo[w] = v;
|
|
dfs(G, w);
|
|
}
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Is there a directed path from the source vertex s to vertex v ?
|
|
* @param v the vertex
|
|
* @return true if there is a directed path from the source
|
|
* vertex s to vertex v , false otherwise
|
|
*/
|
|
public boolean hasPathTo(int v) {
|
|
return marked[v];
|
|
}
|
|
|
|
|
|
/**
|
|
* Returns a directed path from the source vertex s to vertex v , or
|
|
* null if no such path.
|
|
* @param v the vertex
|
|
* @return the sequence of vertices on a directed path from the source vertex
|
|
* s to vertex v , as an 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;
|
|
}
|
|
|
|
/**
|
|
* Unit tests the DepthFirstDirectedPaths data type.
|
|
*/
|
|
public static void main(String[] args) {
|
|
In in = new In(args[0]);
|
|
Digraph G = new Digraph(in);
|
|
// StdOut.println(G);
|
|
|
|
int s = Integer.parseInt(args[1]);
|
|
DepthFirstDirectedPaths dfs = new DepthFirstDirectedPaths(G, s);
|
|
|
|
for (int v = 0; v < G.V(); v++) {
|
|
if (dfs.hasPathTo(v)) {
|
|
StdOut.printf("%d to %d: ", s, v);
|
|
for (int x : dfs.pathTo(v)) {
|
|
if (x == s) StdOut.print(x);
|
|
else StdOut.print("-" + x);
|
|
}
|
|
StdOut.println();
|
|
}
|
|
|
|
else {
|
|
StdOut.printf("%d to %d: not connected\n", s, v);
|
|
}
|
|
|
|
}
|
|
}
|
|
|
|
}
|