Write a class DepthFirstPaths.java to implement a Depth First Search algorithm u
ID: 3807138 • Letter: W
Question
Write a class DepthFirstPaths.java to implement a Depth First Search algorithm using the pseudocode given below. Alternatively you can download the file DepthFirstPaths.java and implement all the unimplemented methods of the class so that it performs Depth First Search on graph G. See the pseudocode given below. DFS (G) for each vertex u element G, V u.color = WHITE u, pi = NIL time = 0 5 for each vertex u element G. V if u.color == WHITE DFS-VISIT(G, u) DFS-VISIT (G,u) time = time + 1 // white vertex u has just been discovered u.d = time u.color = GRAY for each v element G.Adj[u] // explore edge (u, v) if v.color == WHITE v.pi = u DFS-VISIT(G,v) u.color = BLACK // blacken u; it is finished time = time + 1 u.f = time Write driver program, which reads input file mediumG.txt as an undirected graph and runs the Depth First Search algorithm to find paths to all the other vertices considering 0 as the source. This driver program should display the paths in the following manner: 0 to v: "list of all the vertices traversed to go to v from 0, separated by ','".Explanation / Answer
package edu.princeton.cs.algs4;
/**
* The {@code DepthFirstPaths} class represents a data type for finding
* paths from a source vertex <em>s</em> to every other vertex
* in an undirected graph.
* <p>
* This implementation uses depth-first search.
* The constructor takes time proportional to <em>V</em> + <em>E</em>,
* where <em>V</em> is the number of vertices and <em>E</em> is the number of edges.
* It uses extra space (not including the graph) proportional to <em>V</em>.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/41graph">Section 4.1</a>
* of <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
*
*/
public class DepthFirstPaths {
private boolean[] marked; // marked[v] = is there an s-v path?
private int[] edgeTo; // edgeTo[v] = last edge on s-v path
private final int s; // source vertex
/**
* Computes a path between {@code s} and every other vertex in graph {@code G}.
* @param G the graph
* @param s the source vertex
*/
public DepthFirstPaths(Graph G, int s) {
this.s = s;
edgeTo = new int[G.V()];
marked = new boolean[G.V()];
dfs(G, s);
}
// depth first search from v
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);
}
}
}
/**
* Is there a path between the source vertex {@code s} and vertex {@code v}?
* @param v the vertex
* @return {@code true} if there is a path, {@code false} otherwise
*/
public boolean hasPathTo(int v) {
return marked[v];
}
/**
* Returns a path between the source vertex {@code s} and vertex {@code v}, or
* {@code null} if no such path.
* @param v the vertex
* @return the sequence of vertices on a path between the source vertex
* {@code s} and vertex {@code 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 {@code DepthFirstPaths} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
In in = new In(args[0]);
Graph G = new Graph(in);
int s = Integer.parseInt(args[1]);
DepthFirstPaths dfs = new DepthFirstPaths(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 ", s, v);
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.