This lab will serve as a warm-up for Assignment 12. You will be working with the provided graph abstract data type to implement two graph algorithms. The first algorithm is an edge reversal, i.e., the algorithms takes an input graph and returns a graph which is identical to the input but all of the edges are reversed. You will use this function as part of Assignment 12 to test strong connectivity. The second algorithm is breadth-first search. In Assignment 12 you will be implementing Dijkstra’s algorithm which is essentially breadth-first search, replacing the queue with a priority queue.
First, copy the starter code over from the usual locations, and read over the API for the graph ADT, described using JavaDocs in graph.h. You will also being using a queue for this assignment, which has been provided to you in queue.h (it’s the doubly linked list from a previous lab). Once you understand the API we will be using when working with graphs, read over the JavaDocs in graph_lib.h, which contains the specifications for the two functions you will be implementing for this lab.
Your edge reversal should run in O(n + m) time (for n nodes and m edges) and must only access the graph through the functions declared in graph.h, i.e., you should not try to directly manipulate struct graph. There are several ways to implement this method; if you get stuck coming up with an algorithm, you should feel free to ask for help. Make sure you thoroughly test this method! Feel free to create some test cases and draw them on the whiteboards. You may want to uncomment the debugging code to print the underlying graph.
You will be implementing the breadth-first search algorithm, as described in class. In lab you will only be implementing the “basic” breadth-first search algorithm, i.e., you will explore all vertices reachable from a single vertex without restarting to explore the entire graph. Recall, that the “basic” breadth-first search takes a connected graph and produces a spanning tree represented using an array of parents. The entire solution to this problem is contained in the lecture slides, but you should make sure you understand every line you are typing! You should thoroughly test this method as well, and compare your results with the examples on the white boards.
You may freely use code from this lab while implementing Assignment 12.
As usual for C code, run make package to create a folder on your desktop (remember to fill in the authors variable in the makefile first). Once you have the folder with both your name and your partner’s name, turn it in using the usual submit script:
/common/cs/cs062/bin/submit cs062 lab12 ~/Desktop/Lab12_Names