CSC263 Worksheet: Week 9 Depth First Search Winter 2022
1. Run DFS(G) on the directed graph G shown here. Assume that adjacency list and sub lists are all ordered in
increasing alphabetical order. Annotate on each vertex its parent as well as discovery and finish times. And
draw the resulting DFS trees.
A B
D E
CF
2. Now run DFS(G) on the following undirected graph. Produce two possible versions of the adjacenty lists and
note the di↵erence in the resulting DFS trees.
a
k
r
u
qs
pn


欢迎咨询51作业君