CS141 Lab 6

Class Webpage:  http://www.cs.ucr.edu/~jiang/141-homepage.html

For the labs of the sixth week:

• Briefly go over the  first programming assignment solutions. Here are the expected results for all tests. The assignment was graded by Sima Lotfi.

• Go over the  second homework solutions.

• Review the adajcency matrix and adajcency lists data structures for graphs and digraphs using some examples. If time allows, mention some interesting properties of graphs such as the Handshaking Theorem, and relation between graphs and trees.

• Show an algorithm (or C++ program) that takes a digraph represented as adjacency lists and prints the corresponding adacency matrix representation. You may assume the vertices are labeled as integers 1 through n.

• Discuss the classification of the edges (into tree, forward, backward, and cross edges) in a DFS/BFS process on undirected/undirected graphs. Recall necessary definitions. Go over Ex. 22.3-2 on CLRS, p. 547, and repeat the exercise for BFS. Then repeat the exercise for both DFS and BFS but treating Figure 22.6 as an undirected graph. Note that DFS (or BFS) on undirected graphs result in only tree and back edges (or tree and cross edges, resp.).

• Another useful thing is to go over the source-removal algoritgm for topological sorting again, and fill in the details (pseudocode) for finding and keeping track of the sources, i.e. Levitin, p. 176, Question 6. Some hints are given in the slides.

• In-lab exercise: Implement the recursive DFS algorithm in C++, assuming the input digraph is represented as adjacency lists. You may assume that the vertices are labeled as integers 1 through n. For each input digraph, output the sequence of vertices in the order as they are visited by DFS.

TA: Help with the C++ code for accessing the adjacency lists of a digraph, if necessary. Keep track of which students completed the exercise.

• For keen students:

  Can you write efficient non-recursive DFS and BFS algorithms using the data structures stacks and queues? What are the running times of your algorithms? You may assume the input digraph is represented as adjacency lists.

• Advanced stuff for keen students: 

  Extend your above DFS code to check if an input undirected graph is acyclic. If you still have time (in lab or at home), try to do the same thing for digraphs.