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 an undirected graph using adjacency lists
-
Implement Breadth First Search algorithm on graphs.
Problems
-
Write a program to implement an undirected graph using adjacency lists. Write a driver program to read the input files (mediumG.txt and largeG.txt) that contain the number of vertices, number of edges, and the corresponding list of edges and create an undirected graph. You can verify that the graph was constructed successfully by displaying the graph in the form of adjacency list for each vertex (see example below).
-
Implement BFS algorithm on the undirected graphs (created in Problem 1) following the pseudo-code given in the next page. Print the BFS paths from a source (you can pick any vertex as the source) to all the other nodes in the graph.
-
Write a detailed report on the performance of the BFS algorithm for the two input files.
Note that the BFS algorithm uses the queue data structure. You can use any existing package (such as linked list or queue) in the language of your choice to implement the queue, there is no need to implement the queue from scratch.
Adjacency List Visualization
Output:
-
2, 5
-
1,5,3,4
-
2, 4
-
2,5,3
-
4,1,2
DATA
largeG.txt
medium.txt
