## Description

CMSC 451 Homework 4

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)