Description
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)
