Transcript Document

Lectrue4-Properties of DFS
Properties of DFS
Classification of edges
Topological sort
 2004 SDU
Properties of DFS
Definition: In a rooted forest (especially, depth-first
forest), any vertex u on the simple path from the root to v
is called an ancestor of v, and v is called a descendant of
u.
Note: u = [v] if and only if DFS-VISIT (v) was called
during a search of u’s adjacency list. u is called the parent
of v. So:
Vertex v is a descendant of vertex u in the depth-first forest if and
only if v is discovered during the time in which u is gray (when v is
discovered, DFS-VISIT([v]) is called, DFS-VISIT( [v]), …DFSVISIT(u)) is called).
 2004 SDU
2
Properties of DFS (Cont.)
Parenthesis Theorem:
In any DFS of a graph (directed or undirected), for each pair
of vertices u, v, exactly one of the following conditions
holds:
1. u is a descendant of v, and [d[u], f[u]] is a subinterval of
[d[v], f[v]].
2. u is an ancestor of v, and [d[v], f[v]] is a subinterval of
[d[u], f[u]].
3. Neither u is a descendant of v nor v is a descendant of u,
and [d[u], f[u]] and [d[v], f[v]] are disjoint.
Page:166
 2004 SDU
3
Proof
It is obvious that each pair u, v satisfies exactly one of
the following:
1.
2.
3.
u is a descendant of v
v is a descendant of u
neither is descendant of the other
It is enough to prove that
1 holds if and only if [d[u], f[u]] is a subinterval of [d[v], f[v]];
2 holds if and only if [d[v], f[v]] is a subinterval of [d[u], f[u]];
3 holds if and only if [d[u], f[u]] and [d[v], f[v]] are disjoint.
 2004 SDU
4
Proof (Continued)
If 1 holds, then u must be discovered when v is gray, that
means d[v]d[u]<f[u]  f[v]. In the opposite, if d[v] 
d[u]<f[u]  f[v], then u is discovered when v is gray, that
is, u is a descendant of v.
Then second case is similar to the above.
If neither is descendant of the other. Without loss of
generality, suppose d[u]<d[v], then, since v is not a
descendant of u, v must be discovered after u finishes,
that is, f[u]<d[v], hence, [d[u], f[u]] is disjoint with
[d[v],f[v]]. In the opposite, if [d[u],f[u]] and [d[v],f[v]] are
disjoint, then neither is discovered when the other is gray,
so, neither is descendant of the other.
 2004 SDU
5
Nesting of descendants’ intervals
Corollary: Vertex v is a proper descendant of vertex
u in the depth-first forest for a graph G if and
only if d[u]< d[v] < f[v] < f[u].
 2004 SDU
6
White-path theorem
Theorem:
 In a depth-first forest of a graph G = (V, E),
vertex v is a descendant of u if and only if at
time d[u], vertex v can be reached from u
along a path consisting entirely of white
vertices.
Note!
1: All vertices along the path are white
2: At this time
3: Does BFS satisfy this theorem?
 2004 SDU
7
Proof of White-path theorem
=>Assume v is a descendant of u, there is a
unique path from u to v in the DFS forest.
Suppose w is an arbitrary vertex on the path from
u to v in the depth-first forest, then w is a
descendant of u. By the nesting of descendants’
interval corollary, d[u]<d[w], and so at time d[u],
w is white.
 2004 SDU
8
Proof of White-path theorem
<=(By contradiction) Suppose at time d[u], there is a path from u to v
consisting only of white vertices, but v does not become a
descendant of u in the depth-first tree. Without loss of generality,
assume that every other vertex along the path becomes a descendant
of u (otherwise, let v be the closest vertex to u along the path that
does not become a descendant of u). Let w be the predecessor of v
in the path. Hence, w is a descendant of u, and by parenthesis
theorem, d[u]  d[w]<f[w]  f[u].
Since v is not descendent of u, it can not be a son of w. Hence, when
scanning v in Adj[w], v cannot be white, which means d[v]<f[w] 
f[u]. By parenthesis theorem, [d[v], f[v]] must be disjoint with [d[u],
f[u]], so, d[v]<d[u], which contradicts to that at time d[u], v is white.
 2004 SDU
9
Another Proof of<=
(by induction)
<=Suppose the white path is u, v1, v2, …, vk= v, we will
prove that each vi will become a descendent of u.
Base: v1will become a descendent of u.
Because v1Adj[u]. When v1 is scanned in Adj[u], if v1 is
white, then [v1]u; otherwise, v1 must be discovered
when u is gray. In either case, v1 is a descendent of u.
Induction: suppose v1, …, vi-1 will all become descendents
of u.
Consider vi. When vi is scanned in Adj[vi-1], if vi is white,
then [vi]vi-1; otherwise, vi must be discovered when u
is gray, since vi is white at d[u], and before f[vi-1], thus
before f[u], it becomes non-white. In either case, vi is a
descendent of u.
 2004 SDU
10
Exercises
Page 162 22.2-5, 22.2-7
Page 171 22.3-7, 22.3-8, 22.3-10
Page 175 22.4-3
 2004 SDU
11
Applications of DFS
1.
2.
3.
Classifying edges of a graph (for directed or
undirected graph)
Topological sort (for directed acyclic graph)
Strongly connected components decomposing
(for directed graph)
 2004 SDU
Classification of Edges
Let G = (V, E) be the depth-first forest produced by a depth first
search on directed graph G = (V, E), then the edges of G can be
classified into four categories (the non-tree edges are classified
according to the relationship between the end points):
1.
2.
3.
4.
Tree edges: Edges in G 。
Back edges: Edges (u, v) connecting a vertex u to an ancestor v. Selfloops in directed graphs are considered to be back edges.
Forward edges: Those non-tree edges (u, v) connecting a vertex u to a
descendant v.
Cross edges: All other edges. They can go between vertices in the same
depth-first tree as long as neither vertex is ancestor of the other, or they
go between vertices in different trees.
Recalling that for each pair of vertices u, v, there are only
three probabilities between them: u is descendant of v,
opposite, neither.
 2004 SDU
13
Classification of Edges (Example)
1/8
a
T
B
C
9/14
d
b 2/7
T
10/11
3/6
e
T
T
F
c
12/13
C
g
T
f
4/5
 2004 SDU
T: tree edge
F: forward edge
B: back edge
C: cross edge
14
Observation
 In a depth-first search, an edge (u, v) can be
classified according to the color of v when (u, v)
is explored:



WHITE indicates a tree edge
GRAY indicates a back edge
BLACK indicates a forward or cross edge
•
How to distinguish a forward edge and a cross edge?
− d[u] < d[v] means a a forward edge
− d[u] > d[v] means a cross edge
− We can also classify the edges after the DFS
finishes according to d[], f[],[] values. How?
 2004 SDU
15
Classifying Edges in an
Undirected Graph
In an undirected graph, (u, v) and (v, u) are in fact the same edge.
To avoid ambiguity, we classify the edge according to whichever of
(u, v) or (v, u) is encountered first during the execution of the DFS
algorithm.
In a depth-first search of an undirected graph G, every edge of G is
either a tree edge or a back edge.
Proof: Let (u, v) be an arbitrary edge of G, and W.L.O.G, suppose d[u]
<d[v]. According to the white-path theorem (uv is a white path at time
d[u]), v will become a descendant of u. When we scan u’s adjacency
list in DFS-VISIT(u), v will be found since (u, v) is an edge of G.
– v is WHITE, which indicates (u, v) is explored first in the direction
from u to v, (u, v) becomes a tree edge.
– v is not WHITE, then DFS-VISIT(v) has been called before the
scan comes to v when scanning u’s adjacency list in DFS-VISIT(u).
Note that u is also in v’s adjacency list, so (u, v) must be first
explored in the direction from v to u. Since u is an ancestor of v, (v,
u) becomes a back edge.
 2004 SDU
16
Singly Connected Graph
(Page 172 22.3-12)
A directed graph G = (V, E) is singly connected if
u  v (v is reachable from u) implies that
there is at most one simple path from u to v for
all vertices u, v V.
How to determine whether or not a directed
graph is singly connected?
 2004 SDU
17
A directed graph is not singly connected  There exists a vertex u
such that during the call of DFS-VISIT(u), a forward edge or cross
edge will be found.
<=If a forward edge xy is found during the call of DFS-VISIT(u),
then there are two paths from x to y: one is xy, the other is the path
from x to y in the corresponding depth-first tree. If there is a cross
edge xy, then there are two paths from s to y: one is the path from s to
y in the depth-first tree, the other is the path from s to x plus (x, y).
=>If G is not singly connected, then there exist two paths from some
vertex u to some vertex v. Suppose one path is P1 = <u = u1,u2,…,uk,
x1,x2,…xl, w,…,v>, the other path is P2 = <u = u1, u2, …,uk,
y1,y2,…,ym,w,…,v>. That is, u, u2, …, uk are the first common
vertices of P1 and P2; x1 and y1 are the first different vertices of P1
and P2; w is the first common vertex of P1 and P2 after the different
vertices x1,…,xl, and y1, …, ym. Notice that w may be v, and one of
the sets {x1, …, xl} and {y1, …, ym} may be empty.
u u2 uk
 2004 SDU
x1
x2
y1
y2
w
v
18
Consider the call of DFS-VISIT(u). Notice that all the vertices in the
two paths will be descendents of u according to white-path theorem.
When scanning u’s adjacency list we will find u2. u2 cannot be gray.
If u2 is black, then this is a forward edge, the conclusion is drawn.
Otherwise, u2 is white, and (u, u2) is a tree edge.
When scanning u2’ adjacency list we will find u3. u3 cannot be gray,
since otherwise u3 is an ancestor of u2 and therefore an ancestor of u
since u is the parent of u2. If u3 is black, then (u2, u3) is a forward
edge or cross edge, the proof is end. If u3 is white, (u2, u3) is a tree
edge.
Proceeding in this way, we can prove that either a forward edge or
cross edge is met along <u, u2, …, uk, x1, …, xl, w> and along <u,
u2, ..., uk, y1, …, ym, w>, or all the edges in these two sub-paths of P1
and P2 are tree edges. In the former case, the proof is end. In the
latter case, w will be proved to have two predecessors, which is a
dilemma.
Therefore, only the former case is possible, and the proof is end.
 2004 SDU
19
The Answer
Consider all vertices that is reachable from x. A depthfirst search on G starting only from x will generate a tree
T rooted at x, each vertex of the tree is reachable from x
in the graph G. Other vertices that are not in the tree are
not reachable from x in the graph G. If an edge (u, v) G,
where u, v T, (u, v) T, then (u, v) is
 A back edge, or
 A forward edge (indicates not singly connected) or
 A cross edge (indicates not singly connected)
Make each vertex v as the starting vertex, do depth-first
search.
How to modify the DFS-Algorithm? And the time
complexity?
 2004 SDU
20
The Modification
 2004 SDU
21
Modification (continued)
DFS(G)
1
time0;
2
for (each vertex u V[G])
2
do{
for (each vertex v V[G])
do{ color[v]  WHITE;
3
[v]  NIL;
4
5
}
6
7
8
 2004 SDU
DFS-VISIT(u)
}
Print “G is singly connected”
22
The Modification (Continued)
8
9
10
Add
else if color[v] = BLACK
then {Print “G is not singly connected”;
Return } //algorithm ended
11
12
Remove
 2004 SDU
23
Topological Sort
A topological sort of a
directed acyclic graph
G = (V, E) is a linear
ordering of all its
vertices such that if G
contains an edge (u, v),
then u appears before v
in the ordering.
2
1
4
3
1
3
4
2
How about if G contains a cycle?
 2004 SDU
24
Topological Sort Problem
The problem
 Input: A directed acyclic graph G = (V, E).
 Output: A topological order of all the vertices of G.
 2004 SDU
25
Applications of Topological Sort
Assembly lines in industries
Courses arrangement in schools
A general life-related application—dressing order
Graph Theory
Data Structure
Graph Algorithms
Java Language
Advanced Mathematics
Can you give the topological order?
 2004 SDU
26
Application--Dressing Up
 2004 SDU
27
The Algorithm
• Time Complexity Analysis:
• Line 1: (V + E)
• Line 2: (V)
• Line 3: (1)
 2004 SDU
28
Correctness of the Algorithm
Lemma 22.11
 A directed graph G is acyclic if and only if a depth-first search of
G yields no back edges.
 Proof:
=>: Proof by contradiction. Suppose that there is a back edge (u, v).
Then, vertex v is an ancestor of vertex u in the depth-first search
forest. There is thus a path from v to u in G, and the back edge (u, v)
completes a cycle, a contradiction.
<=: Proof by contradiction. Suppose that G contains a cycle c. Let v be
the first vertex to be discovered in c, (u, v) is an edge in c. At time
d[v], the vertices of c form a path of white vertices from v to u. By
the white-path theorem, vertex u becomes a descendant of v in the
depth-first forest. Therefore, (u, v) is a back edge, a contradiction.
 2004 SDU
29
Correctness of the Algorithm
Theorem 22.12: TOPOLOGICAL-SORT(G)
produces a topological sort of a directed acyclic
graph G.
Proof: Suppose that DFS is run on a given dag G = (V,
E). It suffices to show that if (u, v) is an edge in G,
then f[u] > f[v]. By lemma 22.11, (u, v) cannot be a
back edge, therefore, there are only three cases:
1. (u, v) is a tree edge, u is ancestor of v
2. (u, v) is a forward edge, u is ancestor of v
3. (u, v) is a cross edge, when u is still being processed, v is
black
 In each case, f[u]>f[v].
 2004 SDU
30
Another Method for Topological Sort
See Textbook, page 175, Exercise 22.4-5
Repeat:
1. Select a vertex v of zero in-degree, append it to the
end of a list
2. Delete v and all edges leaving it from G
Return the list.
 2004 SDU
31
Correctness
First we prove that a list of all vertices can be constructed in this
way, i.e., at each time a zero-in-degree vertex must exist. This is
easy to prove by noticing that otherwise a cycle will be found by
tracing along the entering edges.
Second, we prove that such a list is a topological list.
By induction on V.
1. V=2, at most only one edge, trivial.
2. Suppose it is true for V<n.
When V=n. Suppose the algorithm outputs a list L. In the
construction of L, algorithm will first select a vertex S of indegree zero and put it at the most left of L. Let G’ be the graph
obtained from G by deleting S and the edges leaving S.
Obviously, G’ is still a DAG and V’<n. By induction hypothesis,
the list L’ constructed by the algorithm for G’ is a topological list
of G’, i.e., all edges in G’ point from left to right in the list L’.
Notice that L’ is exactly obtained from L by deleting S. In L, if
an edge of G is in G’, then both of its end vertices are in L’, and
thus points from left to right, otherwise, it must points from S to
 2004 SDU right.
32
Time complexity of the second topological sort
algorithm.
If we compute the in-degrees of all the vertices
beforehand, and keep all the vertices of zero-indegree into a list L, then we use constant time for
each run of step1, and Adj[v] time for each run of
step2. For executing step2, we just need to delete
vertex v from the adjacency lists, and for each
vertex x in Adj[v], we decline its in-degree by
one, and insert it into L if its in-degree changes to
zero.
Hence, the total time is (V+E) since v will be
any vertex in the graph.
 2004 SDU
33
Exercises
Page 175: 22.4-2
 2004 SDU
34