Bill Thies
thies@mit.edu
Office hours: Sat 13pm, here
http://cag.lcs.mit.edu/~thies/6.046
Announcements:
 PS 6 due Wednesday
 PS 7 out, no problems
 Week from Wed: take home test (due Mon 11/22)
Today:
 Depthfirst search

DEPTHFIRST SEARCH
<< give intuition: go as far down one path until you hit node you've
already visited; backtrack until there is unexplored node. >>
<< algorithm is useful not just for searching, but because it
maintains extra information about graph, in terms of starting and
finishing times. will see applications >>
DFS(G)
for each vertex u in V[G]
do color[u] < WHITE
pi[u] < NIL
time < 0
for each vertex u \in V[G]
do if color[u] = WHITE
then DFSVISIT(u)
DFSVISIT(u)
color[u] < GRAY
time < time + 1
d[u] < time
for each v \in Adj[u]
do if color[v] = WHITE
then pi[v] < u
DFSVISIT(v)
color[u] < BLACK
f[u] < time + 1
time < time + 1

[ work example of DFS. See CLRS p.542 for similar picture. ]
Runtime? << annotate loop in code to run Theta(E) times >>
 Theta (V + E)

DepthFirst Forest: tree with multiple roots
[ draw example. See CLRS p. 544, Figure 22.5(a) for similar picture. ]
<< note: this is depthfirst forest, following the pi values >>
<< note: includes all vertices in graph >>

Edge Classification
<< add edges to forest, labeling as you go >>
1. Tree edge: encounter new (white) vertex
 gray to white
2. Back edge: from descendent to ancestor
 gray to gray
3. Forward edge: nontree edge from ancestor to descendent
 gray to black
4. cross edge: remainder  betweeen trees or subtrees
 gray to black

[ draw timing version. See CLRS p. 544, Figure 22.5(b) for similar picture. ]
Parenthesis theorem. Only relationship between intervals for pair of
vertices is as follows:
0 N
time >
 (one completely overlaps the other)

  (intervals are disjoint)
Why not:
a  (only partial overlap)
b 
> b must be descendant of a. Must finish b before finishing a.

Using timing to classify edge (a, b)
1. b:  BACK EDGE
a: 
that is, d[b] < d[a] < f[a] < f[b]
2. a:  TREE or FORWARD EDGE
b: 
that is, d[a] < d[b] < f[b] < f[a]
3. b:  a:  CROSS EDGE
that is, d[b] < f[b] < d[a] < f[a]
4. a:  b:  impossible edge

Lemma. If G is undirected, a DFS produces only tree and back edges.
Proof. << by picture>>
Try to make a forward edge, drawn from 1>3
1
\T \F? > No, this edge is actually a back edge from 3>1
2 
\T 
3
Try to make a cross edge from
2
T
3
T/ \T
45
C? > No, this edge is actually tree edge from 4>5
(and 5>3 is back edge)
Q: Test in O(V) time whether or not an undirected graph has a cycle?
A: Run DFS, output true on first back edge.
 if no back edges, E = O(V)
 if back edge, quit when found it
<< does this algorithm work on directed graph? yes...>>

We did not cover this in recitation.

 Theorem. A digraph has cycle iff DFS yields a back edge
 Proof.
 > if (a,b) backedge, then v is ancestor of u in depthfirst forest
 > if cycle, let a = first vertex discovered. let be = predecessor on cycle.

 \./
 b > a > >
  ... 

 << must visit everything reachable from b before returning from
 DFSvisit. Thus, (a,b) is a backedge >>

 Runtime? Theta(V + E)
  must visit all forward and cross edges


Topological Sort
 Linear ordering of V s.t. (a, b) in E implies a precedes b in
ordering
<< layout vertices on horiz. line s.t. all edges are from left to right >>
[ draw example from book, p. 550 ]
undershorts \ socks watch
 \ 
\/ \ \./
pants > shoes

\./
belt < shirt
 \./
 tie
 \./
> jacket

TOPOSORT(G)
1. run DFS(G)
2. output vertices in DECREASING order of finishing times f[v]
[ work through example, starting at shirt ]
[ draw linear ordering ]
Correctness: (a, b) in E ==> f[a] > f[b]
 When (a, b) is explored, a is gray
 b gray: back edge (not in dag)
 b white: b becomes descendent of a
==> f[a] > f[b]
 b black: b already finished, but a not finished
==> f[a] > f[b]
Runtime? O(V+E)
 Can output vertices in reverse order as you are running DFS

We only talked through this in recitation (didn't put on board)

 DAG Shortest Paths [CLRS p. 592]

 << will help on your problem set >>

 DAGShortestPaths (G, w, s)
 1. run TOPOSORT(G)
 2. INITIALIZESINGLESOURCE (G, s)
 3. for each vertex a, in topo. sorted order
 do for each vertex b \in Adj[a]
 do RELAX(a, b, w)

 Only paths go from left to right, so never have to relax from right.

 Theta(V+E) time (vs. Dijkstra's algorithm, Theta(E + V lg V)


We did not cover this in recitation

 DFS vs. BFS

 Recall BFS:
 Q < V
 while Q is not empty
 do a < DEQUEUE (Q)
 for each b in Adj[a]
 do if b not in VISITED
 then VISITED < VISITED + {b}
 ENQUEUE(Q, b)

 How to change this to DFS?
  replace Q with stack (draw push, pop)

 DFS BFS
 memory usage small (# edges in path) large (# edges in queue)
 edge classification tree, back, forward, cross tree, cross
 path found arbitrary shortest
 misc start/finish time apps (only starts from one vertex)
 > e.g., connectivity (SCC)
 << physical  for exploring maze >>



 True / False

 T/F: if there is path from u to v in directed graph G, and if d[u] <
 d[v] in DFS, then v is descendant of u in depthfirst forest produced

 false. could be vertex z on path from u to v with d[z] < d[u].

 T/F: if there is path from u to v in digraph G, then any DFS must
 result in d[v] <= f[u]

 false. cross edges.

 T/F: a vertex u of a directed graph can end up in a depthfirst tree
 containin only u, even though u has both incoming and outgoing edges
 in G.

 true (self loop)