=============================================================================
CSC 263 Lecture Summary for Week 10 Fall 2019
=============================================================================
READING: Sections 22.2, 22.3.
SELF-TEST: Exercise 22.3-2.
BFS (cont’d)
– Runtime? Each node enqueued at most once (when it is white), and colour
changed to gray at same time. So main loop iterates at most O(|V|) times.
But, adjacency list of each node examined at most once over entire run,
so total running time is O(|V| + |E|) — linear in size of adjacency lists.
– space complexity: in a fully connected graph we would put every node except s
onto the queue, so we need O(|V|) space
– At the end of BFS, d[v] = \delta(s,v) = minimum distance from s to v =
smallest number of edges on any s–v path.
——————
Depth-First Search
——————
– Similar to BFS, each vertex coloured white (not yet “discovered”), gray
(“discovered” but not yet completely “visited”), or black (adjacency list
completely visited). Main idea of DFS: “go as far as possible before
backtracking”. Also keep track of two “timestamps” for each vertex: d[v]
= discovery time (when v is first encountered), f[v] = finish time (when
v has been completely visited).
– To implement “depth-first” strategy, natural to write DFS recursively.
(Could also use a stack instead of a queue to keep track of vertices to
examine.)
One more “twist”, because DFS commonly used to find connected components
of a graph: instead of taking start vertex s as input, main DFS function
called repeatedly on each unvisited vertex until all vertices have been
visited. (Note: same trick could be used with BFS to entirely visit each
connected component of a graph. This is NOT unique to DFS.)
– Depth-First Search algorithm (with ‘colour’ field omitted, using d[]
field instead since colour[v] = white iff d[v] = oo):
DFS(G=(V,E)):
for each v in V: DFS-VISIT(G=(V,E),u):
f[v] <- d[v] <- oo d[u] <- time <- time + 1
pi[v] <- NIL for each (u,v) in E:
time <- 0 # global if d[v] = oo:
for each v in V: pi[v] <- u
if d[v] = oo: DFS-VISIT(G,v)
DFS-VISIT(G,v) f[u] <- time <- time + 1
- Example: final values of each field after running algorithm.
Input v | pi | d | f
----- ------------------
1:[2,7] 1 | - | 1 | 14
2:[] 2 | 1 | 2 | 3
3:[1,2,4] 3 | 7 | 5 | 8
4:[] 4 | 3 | 6 | 7
5:[3,4] 5 | 6 | 10 | 11
6:[4,5] 6 | 7 | 9 | 12
7:[3,4,6] 7 | 1 | 4 | 13
- Runtime? DFS-VISIT only called on vertices with d[] = oo and those
vertices immediately set d[] < oo; together with loop in DFS this means
DFS-VISIT called exactly once for each vertex. Outside of recursive
calls, each execution of DFS-VISIT examines adjacency list for one
vertex; so total running time is Theta(n+m) (linear in size of adjacency
lists).
- DFS constructs "DFS-forest" for G. For certain applications, we
distinguish between different types of edges in DFS-forest:
. Tree Edges (u,v) = edges in the DFS-forest -- when (u,v) examined,
d[v] = oo.
. Back Edges (u,v) = v is ancestor of u in the DFS-forest -- when (u,v)
examined, d[v] < f[v] = oo.
. Forward Edges (u,v) = v is descendent of u in the DFS-forest -- when
(u,v) examined, d[u] < d[v] < f[v] < oo. Impossible if G undirected.
. Cross Edges (u,v) = all other edges not part of DFS-forest: v neither
ancestor nor descendent of u in DFS-forest -- when (u,v) examined,
f[v] < d[u] < oo. Impossible if G undirected.
- Possible to prove many interesting properties about timestamps d[v],
f[v]; for example, they have "parenthesis structure": for all vertices u
and v,
. either v is a descendant of u in the DFS-forest and [d[v],f[v]] is
entirely contained within [d[u],f[u]], or
. u is a descendant of v in the DFS-forest and [d[u],f[u]] is entirely
contained within [d[v],f[v]], or
. neither vertex is a descendant of the other and the intervals
[d[u],f[u]] and [d[v],f[v]] are disjoint (no overlap).
- Applications:
. Discovering cycles in a graph.
. Discovering connected components, and strongly connected components
in a graph.
. Topologically sorting a graph (i.e., ordering the vertices so that if
there is a directed edge (u,v), then u \leq v).
- We could also do DFS with the same algorithm as BFS
using a stack instead of a queue (compare to DFS):
BFS(G=(V,E),s):
# Initialization.
for all v in V:
colour[v] <- white
d[v] <- oo
pi[v] <- NIL
initialize empty stack T
colour[s] <- gray
d[s] <- 0
pi[s] <- NIL # not necessary because of loop above
PUSH(T,s)
# Loop invariant: T contains exactly the gray vertices.
while T not empty:
u <- POP(T)
for each edge (u,v) in E:
if colour[v] == white:
colour[v] <- gray
d[v] <- d[u] + 1
pi[v] <- u
PUSH(T,v)
colour[u] <- black
Execution of DFS on directed example:
s ------> a ——> b
| | / |
| | v |
| | c |
| | / \ |
v v v v v
f <------ e ------> d
– Stack: [s]
. Pop s — edges (s,a), (s,f)
. Push f (d[f] = 1, pi[f] = s)
. Push a (d[a] = 1, pi[a] = s)
– Stack: [a,f]
. Pop a — edges (a,b), (a,e)
. Push e (d[e] = 2, pi[e] = a)
. Push b (d[b] = 2, pi[b] = a)
– Stack: [b,e,f]
. Pop b — edges (b,c), (b,d)
. Push d (d[d] = 3, pi[d] = b)
. Push c (d[c] = 3, pi[c] = b)
– Stack: [c,d,e,f]
. Pop c — edges (c,d), (c,e)
– Stack: [d,e,f]
. Pop d — no edge
– Stack: [e,f]
. Pop e — edges (e,d), (e,f)
– Stack [f]
. Pop f — no edge
-Compare to BFS on the same graph
-Execution could have looked much different if we had push
edges in a different order (increasing instead of decreasing)