Java project:

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.

Write a 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 , .

DepthFirstPaths.java

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 s and every other vertex in graph G.

* @param G the graph you built in the previous assignment, make sure it has the adjacency list adj for each vertex

* @param s the source vertex

*/

public DepthFirstPaths(Graph G, int s) {

//initialize marked, edgeTo and s

dfs(G, s);

}

// depth first search from v

private void dfs(Graph G, int v) {

//write your dfs code here. Edit edgeTo and marked whenever necessary. It would be easy to use recursion in this function

}

/**

* Is there a path between the source vertex s and vertex v?

* @param v the vertex

* @return true if there is a path, false otherwise

*/

public boolean hasPathTo(int v) {

//return something that represents the above task.

}

/**

* Returns a path between the source vertex s and vertex v, or

* null if no such path.

* @param v the vertex

* @return the sequence of vertices on a path between the source vertex

* s and vertex v, as an Iterable

*/

public Iterable pathTo(int v) {

//implement your code

}

/**

* Unit tests the DepthFirstPaths data type.

*/

}

mediumG.txt

250 1273 244 246 239 240 238 245 235 238 233 240 232 248 231 248 229 249 228 241 226 231 223 242 223 249 222 225 220 247 219 221 218 224 218 227 217 232 216 232 214 219 214 221 213 235 213 238 212 214 212 219 212 221 212 244 211 222 211 225 210 212 210 214 210 219 210 221 210 244

DFS(G) 1 for each vertex u E G. V 2 ucolor = WHITE u.? = NIL 5 for each vertex u E G. V if u.color == WHITE DFS-VISIT (G,u) DFS-VISIT (G, u) /I white vertex u has just been discovered timetime 1 2 u,d=tirne 3 ?.color-: GRAY 4 for each v e G.Adju] // explore edge (u, v) if v. color == WHITE DFS-VISIT (G, v) // blacken u; it is finished 8 u.color BLACK tine = time + 1 10 u.f time