Microsoft PowerPoint – wk8-1.ppt – Compatibility Mode
1
1
COMP9024: Data Structures and
Algorithms
Graphs (II)
2
Contents
Depth-First Search
Breadth-First Search
Transitive Closure
Topological Sorting
1
2
2
3
Properties
Notation
n number of vertices
m number of edges
deg(v) degree of vertex v
Property 1
Sv deg(v) = 2m
Proof: each edge is
counted twice
Property 2
In an undirected graph
with no self-loops and
no multiple edges
m n (n – 1)/2
Proof: each vertex has
degree at most (n – 1)
What is the bound for a
directed graph?
Example
n = 4
m = 6
deg(v) = 3
4
Depth-First Search
DB
A
C
E
3
4
3
5
Subgraphs
A subgraph S of a graph
G is a graph such that
The vertices of S are a
subset of the vertices of G
The edges of S are a
subset of the edges of G
A spanning subgraph of G
is a subgraph that
contains all the vertices
of G
Subgraph
Spanning subgraph
6
Connectivity
A graph is
connected if there is
a path between
every pair of
vertices
A connected
component of a
graph G is a
maximal connected
subgraph of G
Connected graph
Non connected graph with two
connected components
5
6
4
7
Trees and Forests
A (free) tree is an
undirected graph T such
that
T is connected
T has no cycles
This definition of tree is
different from the one of
a rooted tree
A forest is an undirected
graph without cycles
The connected
components of a forest
are trees
Tree
Forest
8
Spanning Trees and Forests
A spanning tree of a
connected graph is a
spanning subgraph that is
a tree
A spanning tree is not
unique unless the graph is
a tree
Spanning trees have
applications to the design
of communication
networks
A spanning forest of a
graph is a spanning
subgraph that is a forest
Graph
Spanning tree
7
8
5
9
Depth-First Search
Depth-first search (DFS)
is a general technique
for traversing a graph
A DFS traversal of a
graph G
Visits all the vertices and
edges of G
Determines whether G is
connected
Computes the connected
components of G
Computes a spanning
forest of G
DFS on a graph with n
vertices and m edges
takes O(n + m ) time
DFS can be further
extended to solve other
graph problems
Find and report a path
between two given
vertices
Find a cycle in the graph
Depth-first search is to
graphs what Euler tour
is to binary trees
10
DFS Algorithm
The algorithm uses a mechanism
for setting and getting “labels” of
vertices and edges
Algorithm DFS(G, v)
Input graph G and a start vertex v of G
Output labeling of the edges of G
in the connected component of v
as discovery edges and back edges
{ setLabel(v, VISITED);
for all e G.incidentEdges(v)
if ( getLabel(e) = UNEXPLORED )
{ w = opposite(v, e);
if ( getLabel(w) = UNEXPLORED )
{ setLabel(e, DISCOVERY);
DFS(G, w);
}
else
setLabel(e, BACK);
}
}
Algorithm DFS(G)
Input graph G
Output labeling of the edges of G
as discovery edges and
back edges
{ for all u G.vertices()
setLabel(u, UNEXPLORED);
for all e G.edges()
setLabel(e, UNEXPLORED);
for all v G.vertices()
if ( getLabel(v) = UNEXPLORED )
DFS(G, v);
}
9
10
6
11
Example (1/2)
DB
A
C
E
DB
A
C
E
DB
A
C
E
discovery edge
back edge
A visited vertex
A unexplored vertex
unexplored edge
12
Example (2/2)
DB
A
C
E
DB
A
C
E
DB
A
C
E
DB
A
C
E
11
12
7
13
DFS and Maze Traversal
The DFS algorithm is
similar to a classic
strategy for exploring
a maze
We mark each
intersection, corner
and dead end (vertex)
visited
We mark each corridor
(edge ) traversed
We keep track of the
path back to the
entrance (start vertex)
by means of a rope
(recursion stack)
14
Properties of DFS
Property 1
DFS(G, v) visits all the
vertices and edges in
the connected
component of v
Property 2
The discovery edges
labeled by DFS(G, v)
form a spanning tree of
the connected
component of v
DB
A
C
E
13
14
8
15
Analysis of DFS
Setting/getting a vertex/edge label takes O(1) time
Each vertex is labeled twice
once as UNEXPLORED
once as VISITED
Each edge is labeled twice
once as UNEXPLORED
once as DISCOVERY or BACK
Method incidentEdges is called once for each vertex
DFS runs in O(n + m) time provided the graph is
represented by the adjacency list structure
Recall that Sv deg(v) = 2m
16
Path Finding
We can specialize the DFS
algorithm to find a path
between two given
vertices v and z using the
template method pattern
We call DFS(G, v) with v
as the start vertex
We use a stack S to keep
track of the path between
the start vertex and the
current vertex
As soon as destination
vertex z is encountered,
we return the path as the
contents of the stack
Algorithm pathDFS(G, v, z)
{ setLabel(v, VISITED);
S.push(v);
if ( v = z )
return S.elements();
for all e G.incidentEdges(v)
if ( getLabel(e) = UNEXPLORED )
{ w = opposite(v,e);
if ( getLabel(w) = UNEXPLORED )
{ setLabel(e, DISCOVERY);
S.push(e);
pathDFS(G, w, z);
S.pop();
}
else
setLabel(e, BACK);
}
S.pop();
}
15
16
9
17
Cycle Finding
We can specialize the
DFS algorithm to find a
simple cycle using the
template method pattern
We use a stack S to
keep track of the path
between the start vertex
and the current vertex
As soon as a back edge
(v, w) is encountered,
we return the cycle as
the portion of the stack
from the top to vertex w
Algorithm cycleDFS(G, v)
{ setLabel(v, VISITED);
S.push(v);
for all e G.incidentEdges(v)
if ( getLabel(e) = UNEXPLORED )
{ w = opposite(v,e);
S.push(e);
if ( getLabel(w) = UNEXPLORED )
{ setLabel(e, DISCOVERY);
cycleDFS(G, w);
S.pop(); }
else
{ T = new empty stack
repeat
{ o = S.pop();
T.push(o); }
until ( o = w );
return T.elements(); }
S.pop();
}
18
Breadth-First Search
CB
A
E
D
L0
L1
F
L2
17
18
10
19
Breadth-First Search
Breadth-first search
(BFS) is a general
technique for traversing
a graph
A BFS traversal of a
graph G
Visits all the vertices and
edges of G
Determines whether G is
connected
Computes the connected
components of G
Computes a spanning
forest of G
BFS on a graph with n
vertices and m edges
takes O(n + m ) time
BFS can be further
extended to solve other
graph problems
Find and report a path
with the minimum
number of edges
between two given
vertices
Find a simple cycle, if
there is one
20
BFS Algorithm
The algorithm uses a
mechanism for setting and
getting “labels” of vertices
and edges
Algorithm BFS(G, s)
{ L0 = new empty sequence;
L0.insertLast(s);
setLabel(s, VISITED);
i = 0;
while ( Li.isEmpty() )
{ Li +1 = new empty sequence;
for all v Li.elements()
for all e G.incidentEdges(v)
if ( getLabel(e) = UNEXPLORED )
{ w = opposite(v,e);
if ( getLabel(w) = UNEXPLORED )
{ setLabel(e, DISCOVERY);
setLabel(w, VISITED);
Li +1.insertLast(w); }
else
setLabel(e, CROSS);
}
i = i +1;
}
}
Algorithm BFS(G)
Input graph G
Output labeling of the edges
and partition of the
vertices of G
{
for all u G.vertices()
setLabel(u, UNEXPLORED);
for all e G.edges()
setLabel(e, UNEXPLORED);
for all v G.vertices()
if ( getLabel(v) = UNEXPLORED )
BFS(G, v);
}
19
20
11
21
Example (1/3)
CB
A
E
D
discovery edge
cross edge
A visited vertex
A unexplored vertex
unexplored edge
L0
L1
F
CB
A
E
D
L0
L1
F
CB
A
E
D
L0
L1
F
22
Example (2/3)
CB
A
E
D
L0
L1
F
CB
A
E
D
L0
L1
F
L2
CB
A
E
D
L0
L1
F
L2
CB
A
E
D
L0
L1
F
L2
21
22
12
23
Example (3/3)
CB
A
E
D
L0
L1
F
L2
CB
A
E
D
L0
L1
F
L2
CB
A
E
D
L0
L1
F
L2
24
Properties
Notation
Gs: connected component of s
Property 1
BFS(G, s) visits all the vertices and
edges of Gs
Property 2
The discovery edges labeled by
BFS(G, s) form a spanning tree Ts
of Gs
Property 3
For each vertex v in Li
The path of Ts from s to v has i
edges
Every path from s to v in Gs has at
least i edges
CB
A
E
D
L0
L1
F
L2
CB
A
E
D
F
23
24
13
25
Analysis
Setting/getting a vertex/edge label takes O(1) time
Each vertex is labeled twice
once as UNEXPLORED
once as VISITED
Each edge is labeled twice
once as UNEXPLORED
once as DISCOVERY or CROSS
Each vertex is inserted once into a sequence Li
Method incidentEdges is called once for each vertex
BFS runs in O(n + m) time provided the graph is
represented by the adjacency list structure
Recall that Sv deg(v) = 2m
26
Applications
Using the template method pattern, we can
specialize the BFS traversal of a graph G to
solve the following problems in O(n + m) time
Compute the connected components of G
Compute a spanning forest of G
Find a simple cycle in G, or report that G is a
forest
Given two vertices of G, find a path in G between
them with the minimum number of edges, or
report that no such path exists
25
26
14
27
DFS vs. BFS (1/2)
CB
A
E
D
L0
L1
F
L2
CB
A
E
D
F
DFS BFS
Applications DFS BFS
Spanning forest, connected
components, paths, cycles
Shortest paths
Biconnected components
28
DFS vs. BFS (2/2)
Back edge (v,w)
w is an ancestor of v in
the tree of discovery
edges
Cross edge (v,w)
w is in the same level as
v or in the next level in
the tree of discovery
edges
CB
A
E
D
L0
L1
F
L2
CB
A
E
D
F
DFS BFS
27
28
15
29
Directed Graphs
JFK
BOS
MIA
ORD
LAX
DFW
SFO
30
Digraphs
A digraph is a graph
whose edges are all
directed
Short for “directed graph”
Applications
one-way streets
flights
task scheduling A
C
E
B
D
29
30
16
31
Digraph Properties
A graph G=(V,E) such that
Each edge goes in one direction:
Edge (a,b) goes from a to b, but not b to a.
If G is simple, m < n*(n-1). If we keep in-edges and out-edges in separate adjacency lists, we can perform listing of in- edges and out-edges in time proportional to their size. A C E B D 32 Digraph Application Scheduling: edge (a,b) means task a must be completed before b can be started The good life ics141ics131 ics121 ics53 ics52ics51 ics23ics22ics21 ics161 ics151 ics171 31 32 17 33 Directed DFS We can specialize the traversal algorithms (DFS and BFS) to digraphs by traversing edges only along their direction In the directed DFS algorithm, we have four types of edges discovery edges back edges forward edges cross edges A directed DFS starting a a vertex s determines the vertices reachable from s A C E B D 34 Reachability DFS tree rooted at v: vertices reachable from v via directed paths A C E B D F A C E D A C E B D F 33 34 18 35 Strong Connectivity Each vertex can reach all other vertices a d c b e f g 36 Pick a vertex v in G. Perform a DFS from v in G. If there’s a w not visited, print “no”. Let G’ be G with edges reversed. Perform a DFS from v in G’. If there’s a w not visited, print “no”. Else, print “yes”. Running time: O(n+m). Strong Connectivity Algorithm G: G’: a d c b e f g a d c b e f g 35 36 19 37 Maximal subgraphs such that each vertex can reach all other vertices in the subgraph Can also be done in O(n+m) time using DFS, but is more complicated (similar to biconnectivity). Strongly Connected Components { a , c , g } { f , d , e , b } a d c b e f g 38 Transitive Closure Given a digraph G, the transitive closure of G is the digraph G* such that G* has the same vertices as G if G has a directed path from u to v (u v), G* has a directed edge from u to v The transitive closure provides reachability information about a digraph B A D C E B A D C E G G* 37 38 20 39 Computing the Transitive Closure We can perform DFS starting at each vertex O(n(n+m)) If there's a way to get from A to B and from B to C, then there's a way to get from A to C. Alternatively ... Use dynamic programming: The Floyd-Warshall Algorithm 40 Floyd-Warshall Transitive Closure Idea #1: Number the vertices 1, 2, …, n. Idea #2: Consider paths that use only vertices numbered 1, 2, …, k, as intermediate vertices: k j i Uses only vertices numbered 1,…,k-1 Uses only vertices numbered 1,…,k-1 Uses only vertices numbered 1,…,k (add this edge if it’s not already in) 39 40 21 41 Floyd-Warshall’s Algorithm Floyd-Warshall’s algorithm numbers the vertices of G as v1 , …, vn and computes a series of digraphs G0, …, Gn G0=G Gk has a directed edge (vi, vj) if G has a directed path from vi to vj with intermediate vertices in the set {v1 , …, vk} We have that Gn = G* In phase k, digraph Gk is computed from Gk - 1 Running time: O(n3), assuming areAdjacent is O(1) (e.g., adjacency matrix) Algorithm FloydWarshall(G) Input digraph G Output transitive closure G* of G { i = 1; for all v G.vertices() { denote v as vi ; i = i + 1; } G0 = G; for k = 1 to n do { Gk = Gk -1; for i = 1 to n (i k) do for j = 1 to n (j i, k) do if Gk - 1.areAdjacent(vi, vk) Gk - 1.areAdjacent(vk, vj) if Gk.areAdjacent(vi, vj) Gk.insertDirectedEdge(vi, vj ); } return Gn } 42 Floyd-Warshall Example JFK BOS MIA ORD LAX DFW SFO v2 v1 v3 v4 v5 v6 v7 41 42 22 43 Floyd-Warshall, Iteration 1 JFK BOS MIA ORD LAX DFW SFO v2 v1 v3 v4 v5 v6 v7 44 Floyd-Warshall, Iteration 2 JFK BOS MIA ORD LAX DFW SFO v2 v1 v3 v4 v5 v6 v7 43 44 23 45 Floyd-Warshall, Iteration 3 JFK BOS MIA ORD LAX DFW SFO v2 v1 v3 v4 v5 v6 v7 46 Floyd-Warshall, Iteration 4 JFK BOS MIA ORD LAX DFW SFO v2 v1 v3 v4 v5 v6 v7 45 46 24 47 Floyd-Warshall, Iteration 5 JFK MIA ORD LAX DFW SFO v2 v1 v3 v4 v5 v6 v7 BOS 48 Floyd-Warshall, Iteration 6 JFK MIA ORD LAX DFW SFO v2 v1 v3 v4 v5 v6 v7 BOS 47 48 25 49 Floyd-Warshall, Conclusion JFK MIA ORD LAX DFW SFO v2 v1 v3 v4 v5 v6 v7 BOS 50 DAGs and Topological Ordering A directed acyclic graph (DAG) is a digraph that has no directed cycles A topological ordering of a digraph is a numbering v1 , …, vn of the vertices such that for every edge (vi , vj), we have i < j Example: in a task scheduling digraph, a topological ordering is a task sequence that satisfies the precedence constraints Theorem A digraph admits a topological ordering if and only if it is a DAG B A D C E DAG G B A D C E Topological ordering of G v1 v2 v3 v4 v5 49 50 26 51 write c.s. program play Topological Sorting Number vertices, so that (u,v) in E implies u < v wake up eat nap study computer sci. more c.s. work out sleep dream about graphs A typical student day1 2 3 4 5 6 7 8 9 10 11 make cookies for professors 52 Running time: O(n + m). How…? Algorithm for Topological Sorting Method TopologicalSort(G) { H = G; // Temporary copy of G n = G.numVertices(); while H is not empty do { Let v be a vertex with no outgoing edges; Label v = n; n = n – 1; Remove v from H; } } 51 52 27 53 Topological Sorting Algorithm using DFS Simulate the algorithm by using depth-first search O(n+m) time. Algorithm topologicalDFS(G, v) Input graph G and a start vertex v of G Output labeling of the vertices of G in the connected component of v { setLabel(v, VISITED); for all e G.incidentEdges(v) if ( getLabel(e) = UNEXPLORED ) { w = opposite(v,e); if ( getLabel(w) = UNEXPLORED ) { setLabel(e, DISCOVERY); topologicalDFS(G, w); } } Label v with topological number n; n = n – 1; return; } Algorithm topologicalDFS(G) Input dag G Output topological ordering of G { n = G.numVertices(); for all u G.vertices() setLabel(u, UNEXPLORED); for all e G.edges() setLabel(e, UNEXPLORED); for all v G.vertices() if ( getLabel(v) = UNEXPLORED ) topologicalDFS(G, v); } 54 Topological Sorting Example (1/10) 53 54 28 55 Topological Sorting Example (2/10) 9 56 Topological Sorting Example (3/10) 8 9 55 56 29 57 Topological Sorting Example (4/10) 7 8 9 58 Topological Sorting Example (5/10) 7 8 6 9 57 58 30 59 Topological Sorting Example (6/10) 7 8 56 9 60 Topological Sorting Example (7/10) 7 4 8 56 9 59 60 31 61 Topological Sorting Example (8/10) 7 4 8 56 3 9 62 Topological Sorting Example (9/10) 2 7 4 8 56 3 9 61 62 32 63 Topological Sorting Example (10/10) 2 7 4 8 56 1 3 9 64 Summary Depth-First Search Breadth-First Search Transitive Closure Topological Sorting Suggested reading (Sedgewick): Ch.18 Ch.19 63 64