CMSC451 Homework 4 Solution

Consider the following directed graph for each of the problems:



1. Perform a breadth-first search on the graph assuming that the vertices and adjacency lists are listed in alphabetical order. Show the breadth-first search tree that is generated.

2. Perform a depth-first search on the graph assuming that the vertices and adjacency lists are listed in alphabetical order. Classify each edge as tree, forward, back or cross edge. Label each vertex with its start and finish time.

3. Remove all the back edges from the graph so it becomes a DAG. Perform a depth-first search recording the start and finish times. Using those finish times, provide the topological order that is produced. Provide one breadth-first topological order for that graph.

4. Determine the strongly connected components of the graph using the algorithm provided in the sample problems. Show the final depth-first search of the transpose graph labeled with its start and finish times. Identify the strongly connected components based on that search.

Grading Rubric
Problem Meets Does Not Meet
Problem 1 10 points 0 points

Breadth-first search was done correctly assuming alphabetical vertex and adjacency lists (5) Breadth-first search was not done correctly assuming alphabetical vertex and adjacency lists (0)
Tree provided is a correct breadth-first search tree (5) Tree provided is not a correct breadthfirst search tree (0)
Problem 2 10 points 0 points

Performed a correct depth-first search
(3) Did not perform a correct depth-first search (0)
Tree edges correctly labeled (1) Tree edges not correctly labeled (0)
Back edges correctly labeled (1) Back edges not correctly labeled (0)
Forward edges correctly labeled (1) Forward edges not correctly labeled (0)
Cross edges correctly labeled (1) Cross edges not correctly labeled (0)
Provided correct start and finish times
(3) Did not provide correct start and finish times (0)
Problem 3 10 points 0 points

Correctly transformed the graph into a DAG (2) Did not correctly transform the graph into a DAG (0)
Provided correct start and finish times
(3) Did not provide correct start and finish times (0)
Provided correct topological order from finish times (3) Did not provide correct topological order from finish times (0)
Provided correct breadth-first topological order (2) Did not provide correct breadth-first topological order (0)
Problem 4 10 points 0 points

Correctly transposed graph (2) Did not correctly transpose graph (0)
Provided correct start and finish times
(4) Did not provide correct start and finish times (0)
Provided correct strongly connected components (2) Did not provide correct strongly connected components (0)