1. Write a program to implement the depth-first search algorithm using the pseudocode given on the...

 

Transcribed Image Text:

1. Write a program to implement the depth-first search algorithm using the pseudocode given on the next page. 2. 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 ,'. There is another file called tinyG.txt which you can use for your testing purpose. DFS (G) 1 for each vertex u € G.V 2 u.color = WHITE 3 U.π = NIL 4 5 6 7 time=0 for each vertex u € G.V if u.color == WHITE DFS-VISIT (G, u) DFS-VISIT (G, u) 1 time = time + 1 2 u.d = time u.color= GRAY for each ve G.Adj[u] 3 4 5 6 7 8 = 9 time time +1 10 u.f = time if v.color == WHITE V.π = u DFS-VISIT (G, v) u.color= BLACK // white vertex u has just been discovered // explore edge (u, v) // blacken u; it is finished 1. Write a program to implement the depth-first search algorithm using the pseudocode given on the next page. 2. 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 ,'. There is another file called tinyG.txt which you can use for your testing purpose. DFS (G) 1 for each vertex u € G.V 2 u.color = WHITE 3 U.π = NIL 4 5 6 7 time=0 for each vertex u € G.V if u.color == WHITE DFS-VISIT (G, u) DFS-VISIT (G, u) 1 time = time + 1 2 u.d = time u.color= GRAY for each ve G.Adj[u] 3 4 5 6 7 8 = 9 time time +1 10 u.f = time if v.color == WHITE V.π = u DFS-VISIT (G, v) u.color= BLACK // white vertex u has just been discovered // explore edge (u, v) // blacken u; it is finished

Answer rating: 100% (QA)

Answer 1 THE DFS is as follows import javautil public class DFS no of vertices int V we are building graph using adjacency list so we should have link... View the full answer