Readings
•
Problems Problem 1
Graph Traversals: BFS & DFS—Monday, March 2/Tuesday, March 3
q
n
yr
s
t
x
vw
z
Run DFS on the graph above starting from q. Mark the start and finish times of each vertex and classify
each edge as a forward, back, tree or cross edge. You may assume we process vertices in alphabetical order.
1
Solution Set
CIS 121—Data Structures and Algorithms—Spring 2020
Lecture Notes Chapter 16: Graph Traversals: BFS & DFS
Solution
q 1/16
B
t 8/15 T T
x 9/12 TB
z 10/11
n 17/20 CT
T
s 2/7 TB
T F
y 13/14 C
r 18/19
Problem 2
v 3/6 T w 4/5
Design an algorithm to find the shortest path between nodes u and v in a connected, unweighted graph. Solution
Since the graph is unweighted, we can just run BFS starting from u and for each node x that we visit, we just keep a pointer to its parent node (the node we visited x from). When we reach v, we stop and find the shortest path by backtracking through the pointers that we kept (i.e. we could see that v’s parent was d, d’s parentwasc,andc’sparentwasu,soourpathwouldbeu!c!d!v). WejustdoaBFSandbacktrack no more than O(n) times (the longest path in a graph is n 1 edges), so this algorithm also runs in linear time.
Problem 3: Finding a Cycle in a Directed Graph
Design an algorithm to determine if a directed graph G has a cycle, and return a cycle if one exists.
Solution
We can use DFS for this question. We will run DFS from an arbitrary vertex s, while also maintaining a parent pointer array A. During our DFS traversal, if we go from a node u to a neighbor v, we will set A[v] = u. If we ever see a back edge (u, v), we know we have found a cycle. We can then return the cycle by creating a list L and following the parent pointers until we get back to v, at each step adding the current node to the front of the list. Once we reach vertex v, then L must contain every node in the cycle so we return it. If we never see a back edge during our DFS traversal, then there are no cycles in G so we return nothing.
2
Solution Set