CS计算机代考程序代写 data structure algorithm Microsoft PowerPoint – wk8-1.ppt – Compatibility Mode

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