Description
Notes:
-
Implement the algorithm and analyze the results using the give input files
-
Deliverables: Report.pdf file and your code file (please do not send a zip file. If you have more than one class in your code, then submit each file separately through Canvas.)
-
Homework report must follow the guidelines provided in the sample report uploaded in Canvas
Objectives:
-
Implement Depth First Search algorithm on graphs.
-
Implement Topological Sort
Problems:
-
Write a program to implement the depth-first search algorithm using the pseudocode given on the next page.
-
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.
-
Implement the Topological Sort algorithm for directed graphs and run the algorithm on the directed graph that is provided in the tinyDG.txt file. The pseudocode is provided in the next page.
