[SOLVED] algorithm graph =============================================================================

=============================================================================
CSC 263Lecture Summary for Week10Fall 2019
=============================================================================

READING: Sections 22.2, 22.3.
SELF-TEST: Exercise 22.3-2.

BFS (contd)

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 sv 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 + 1pi[v] <- NIL for each (u,v) in E: time <- 0# globalif d[v] = oo: for each v in V:pi[v] <- uif 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 | 142:[]2 |1 |2 |33:[1,2,4] 3 |7 |5 |84:[]4 |3 |6 |75:[3,4] 5 |6 | 10 | 116:[4,5] 6 |7 |9 | 127:[3,4,6] 7 |1 |4 | 13- Runtime? DFS-VISIT only called on vertices with d[] = oo and thosevertices immediately set d[] < oo; together with loop in DFS this meansDFS-VISIT called exactly once for each vertex. Outside of recursivecalls, each execution of DFS-VISIT examines adjacency list for onevertex; so total running time is Theta(n+m) (linear in size of adjacencylists).- DFS constructs “DFS-forest” for G. For certain applications, wedistinguish 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 neitherancestor 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 uand v,. either v is a descendant of u in the DFS-forest and [d[v],f[v]] isentirely contained within [d[u],f[u]], or. u is a descendant of v in the DFS-forest and [d[u],f[u]] is entirelycontained 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 componentsin a graph.. Topologically sorting a graph (i.e., ordering the vertices so that ifthere is a directed edge (u,v), then u leq v).- We could also do DFS with the same algorithm as BFSusing a stack instead of a queue (compare to DFS):BFS(G=(V,E),s):# Initialization.for all v in V:colour[v] <- whited[v] <- oopi[v] <- NILinitialize empty stack Tcolour[s] <- grayd[s] <- 0pi[s] <- NIL# not necessary because of loop abovePUSH(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] <- grayd[v] <- d[u] + 1pi[v] <- uPUSH(T,v)colour[u] <- blackExecution 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)