Transcript Graphs - CSUDH Computer Science

Chapter 13: Graphs I
Objectives:
Graph ADT: Operations
Graph Implementation: Data structures
Graph Traversals: DFS and BFS
Directed graphs
Weighted graphs
Shortest paths
Minimum Spanning Trees (MST)
CSC311: Data Structures
1
Graphs
A graph is a pair (V, E), where
– V is a set of nodes, called vertices
– E is a collection of pairs of vertices, called edges
– Vertices and edges are positions and store elements
Example:
– A vertex represents an airport and stores the three-letter airport
code
– An edge represents a flight route between two airports and
stores the mileage of the route
SFO
PVD
ORD
LGA
HNL
Graphs I
LAX
DFW
CSC311: Data Structures
MIA
2
Edge Types
Directed edge
– ordered pair of vertices (u,v)
– first vertex u is the origin
– second vertex v is the
destination
– e.g., a flight
ORD
flight
AA 1206
PVD
ORD
849
miles
PVD
Undirected edge
– unordered pair of vertices (u,v)
– e.g., a flight route
Directed graph
– all the edges are directed
– e.g., route network
Undirected graph
– all the edges are undirected
– e.g., flight network
Graphs I
CSC311: Data Structures
3
Applications
Electronic circuits
cslab1a
cslab1b
– Printed circuit board
– Integrated circuit
Transportation networks
math.brown.edu
cs.brown.edu
– Highway network
– Flight network
brown.edu
Computer networks
– Local area network
– Internet
– Web
qwest.net
att.net
cox.net
Databases
John
– Entity-relationship diagramPaul
Graphs I
CSC311: Data Structures
David
4
Terminology
End vertices (or endpoints)
of an edge
– U and V are the endpoints
of a
a
Edges incident on a vertex
– a, d, and b are incident on
V
Adjacent vertices
– U and V are adjacent
U
V
b
d
X
c
Degree of a vertex
– X has degree 5
e
W
– h and i are parallel edges
j
Z
i
g
f
Parallel edges
h
Y
Self-loop
– j is a self-loop
Graphs I
CSC311: Data Structures
5
Terminology (cont.)
Path
– sequence of alternating
vertices and edges
– begins with a vertex
– ends with a vertex
– each edge is preceded and
followed by its endpoints
Simple path
a
U
– path such that all its vertices
and edges are distinct
Examples
– P1=(V,b,X,h,Z) is a simple
path
– P2=(U,c,W,e,X,g,Y,f,W,d,V) is
a path that is not simple
Graphs I
CSC311: Data Structures
c
V
b
d
P2
P1
X
e
W
h
Z
g
f
Y
6
Terminology (cont.)
Cycle
– circular sequence of alternating
vertices and edges
– each edge is preceded and
followed by its endpoints
Simple cycle
– cycle such that all its vertices
and edges are distinct
Examples
a
U
c
– C1=(V,b,X,g,Y,f,W,c,U,a,) is a
simple cycle
– C2=(U,c,W,e,X,g,Y,f,W,d,V,a,)
is a cycle that is not simple
Graphs I
CSC311: Data Structures
V
b
d
C2
X
e
C1
g
W
f
h
Z
Y
7
Properties
Property 1
Notation
Sv deg(v) = 2m
n
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)
m
deg(v)
number of
vertices
number of edges
degree of vertex
vExample
– n=4
– m=6
– deg(v) = 3
What is the bound for a
directed graph?
Graphs I
CSC311: Data Structures
8
Main Methods of the Graph ADT
Vertices and edges
Update methods
– are positions
– store elements
Accessor methods
– endVertices(e): an array
of the two endvertices of
e
– opposite(v, e): the vertex
opposite of v on e
– areAdjacent(v, w): true iff
v and w are adjacent
– replace(v, x): replace
element at vertex v with
x
– replace(e, x): replace
element at edge e with x
Graphs I
– insertVertex(o): insert a
vertex storing element o
– insertEdge(v, w, o): insert
an edge (v,w) storing
element o
– removeVertex(v): remove
vertex v (and its incident
edges)
– removeEdge(e): remove
edge e
Iterator methods
– incidentEdges(v): edges
incident to v
– vertices(): all vertices in
the graph
– edges(): all edges in the
graph
CSC311: Data Structures
9
Edge List Structure
u
Vertex object
a
– element
– reference to position in
vertex sequence
v
c
b
d
w
z
Edge object
–
–
–
–
element
origin vertex object
destination vertex object
reference to position in
edge sequence
u
z
w
v
Vertex sequence
– sequence of vertex
objects
a
b
c
d
Edge sequence
– sequence of edge objects
Graphs I
CSC311: Data Structures
10
Adjacency List Structure
a
Edge list structure
Incidence sequence
for each vertex
– sequence of
references to edge
objects of incident
edges
v
b
u
u
w
v
w
Augmented edge
objects
– references to
associated positions
in incidence
sequences of end
vertices
Graphs I
a
CSC311: Data Structures
b
11
Adjacency Matrix Structure
a
Edge list structure
Augmented vertex
objects
v
b
u
w
– Integer key (index)
associated with vertex
2D-array adjacency
array
0
u
1
– Reference to edge
object for adjacent
vertices
– Null for non
nonadjacent vertices
0
0
The “old fashioned”
version just has 0 for no
edge and 1 for edge
Graphs I
CSC311: Data Structures
2
1

w
2


1
a
2
v


b
12
Asymptotic Performance
n vertices, m edges
no parallel edges
no self-loops
Bounds are “big-Oh”
Edge
List
Adjacency
List
Adjacenc
y Matrix
Space
n+m
n+m
n2
incidentEdges(v)
areAdjacent (v, w)
insertVertex(o)
m
m
1
deg(v)
min(deg(v), deg(w))
1
n
1
n2
insertEdge(v, w, o)
1
1
1
removeVertex(v)
m
deg(v)
removeEdge(e)
1
1
n2
1
Graphs I
CSC311: Data Structures
13
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
Graphs I
CSC311: Data Structures
Subgraph
Spanning subgraph
14
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
Graphs I
Connected graph
Non connected graph with two
connected components
CSC311: Data Structures
15
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
Graphs I
CSC311: Data Structures
Tree
Forest
16
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
Graphs I
CSC311: Data Structures
17
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
Graphs I
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 while Euler tour is
to binary trees
CSC311: Data Structures
18
DFS Algorithm
The algorithm uses a
mechanism for setting and
getting “labels” of vertices
and edges
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)
Graphs I
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)
CSC311: Data Structures
19
Example
unexplored vertex
visited vertex
unexplored edge
discovery edge
back edge
A
A
A
B
D
E
A
D
E
C
Graphs I
E
C
A
B
D
B
C
CSC311: Data Structures
20
Example (cont.)
A
B
A
D
E
C
C
A
A
B
D
E
C
Graphs I
B
B
D
E
D
E
C
CSC311: Data Structures
21
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
Graphs I
A
B
CSC311: Data Structures
D
E
C
22
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
Graphs I
Sv deg(v) = 2m
CSC311: Data Structures
23
Path Finding
We can specialize the DFS
algorithm to find a path
between two given vertices
u and z using the template
method pattern
We call DFS(G, u) with u 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
Graphs I
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(e)
else
setLabel(e, BACK)
S.pop(v)
CSC311: Data Structures
24
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
Graphs I
Algorithm cycleDFS(G, v, z)
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, z)
S.pop(e)
else
T  new empty stack
repeat
o  S.pop()
T.push(o)
until o = w
return T.elements()
S.pop(v)
CSC311: Data Structures
25
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
Graphs I
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
CSC311: Data Structures
26
BFS Algorithm
The algorithm uses a
mechanism for setting
and getting “labels” of
vertices and edges
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)
Graphs I
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
CSC311: Data Structures
27
Example
L0
unexplored vertex
visited vertex
unexplored edge
discovery edge
cross edge
A
A
L0
L1
B
B
L0
C
D
C
E
A
E
Graphs I
L1
A
L1
F
F
A
B
C
E
CSC311: Data Structures
D
D
F
28
Example (cont.)
L0
L1
L0
A
B
C
E
L0
L1
Graphs I
F
L0
C
E
B
L2
A
B
L2
D
L1
D
L1
CSC311: Data Structures
C
E
D
F
A
B
L2
F
A
C
E
D
F
29
Example (cont.)
L0
L1
L0
L1
C
E
D
L1
B
L2
F
A
C
E
D
F
A
B
L2
Graphs I
A
B
L2
L0
C
E
D
F
CSC311: Data Structures
30
Properties
Notation
A
Gs: connected component of s
Property 1
B
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
L1
– The path of Ts from s to v has i
edges
– Every path from s to v in Gs has at
least i edges
Graphs I
CSC311: Data Structures
C
E
L0
F
A
B
L2
D
C
E
D
F
31
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
Graphs I
Sv deg(v) = 2m
CSC311: Data Structures
32
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
Graphs I
CSC311: Data Structures
33
DFS vs. BFS
Applications
DFS
BFS


Spanning forest, connected
components, paths, cycles
Shortest paths

Biconnected components

L0
A
B
C
E
D
L1
DFS
Graphs I
B
L2
F
A
C
E
D
F
BFS
CSC311: Data Structures
34
DFS vs. BFS (cont.)
Back edge (v,w)
Cross edge (v,w)
– w is an ancestor of v
in the tree of
discovery edges
– w is in the same level
as v or in the next
level in the tree of
discovery edges
L0
A
B
C
E
D
L1
DFS
Graphs I
B
L2
F
A
C
E
D
F
BFS
CSC311: Data Structures
35
Digraphs
A digraph is a
graph whose edges
are all directed
E
D
– Short for “directed
graph”
C
Applications
– one-way streets
– flights
– task scheduling
Graphs I
B
A
CSC311: Data Structures
36
Digraph Properties
E
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 outedges in separate adjacency
lists, we can perform listing of
in-edges and out-edges in time
proportional to their size.
Graphs I
CSC311: Data Structures
D
C
B
A
37
Digraph Application
Scheduling: edge (a,b) means task a must
be completed before b can be started
ics21
ics22
ics23
ics51
ics53
ics52
ics161
ics131
ics141
ics121
The good life
ics151
Graphs I
ics171
CSC311: Data Structures
38
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
D
C
B
A directed DFS starting a
vertex s determines the
vertices reachable from s
Graphs I
E
CSC311: Data Structures
A
39
Reachability
DFS tree rooted at v: vertices
reachable from v via directed paths
E
E
D
C
D
A
C
A
F
E
B
C
A
Graphs I
D
CSC311: Data Structures
F
B
40
Strong Connectivity
Each vertex can reach all other vertices
a
g
c
d
e
b
f
Graphs I
CSC311: Data Structures
41
Strong Connectivity Algorithm
Pick a vertex v in G.
Perform a DFS from v in G.
a
G:
– If there’s a w not visited, print
“no”.
d
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).
Graphs I
CSC311: Data Structures
g
c
e
b
f
a
G’:
g
c
d
f
e
b
42
Strongly Connected Components
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).
a
c
d
{a,c,g}
b
{f,d,e,b}
e
f
Graphs I
g
CSC311: Data Structures
43
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
Graphs I
CSC311: Data Structures
D
E
B
C
G
A
D
E
B
C
A
G*
44
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.
Graphs I
Alternatively ... Use
dynamic programming:
The Floyd-Warshall
Algorithm
CSC311: Data Structures
45
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:
i
Uses only vertices numbered 1,…,k
(add this edge if it’s not already in)
j
Uses only vertices
numbered 1,…,k-1
k
Graphs I
Uses only vertices
numbered 1,…,k-1
CSC311: Data Structures
46
Topological Sorting
Number vertices, so that (u,v) in E
implies u < v
wake up
1
A typical student day
3
2
study computer sci.
eat
4
7
play
nap
5
more c.s.
8
write c.s. program
6
work out
9
make cookies
for professors
10
11
sleep
dream about graphs
Graphs I
CSC311: Data Structures
47
Algorithm for Topological Sorting
Note: This algorithm is different than
the one in Goodrich-Tamassia
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
Running time: O(n + m). How…?
Graphs I
CSC311: Data Structures
48
Topological Sorting
Algorithm using DFS
Simulate the algorithm by
using depth-first search
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)
O(n+m) time.
Graphs I
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)
else
{e is a forward or cross edge}
Label v with topological number n
nn-1
CSC311: Data Structures
49
Topological Sorting Example
Graphs I
CSC311: Data Structures
50
Topological Sorting Example
9
Graphs I
CSC311: Data Structures
51
Topological Sorting Example
8
9
Graphs I
CSC311: Data Structures
52
Topological Sorting Example
7
8
9
Graphs I
CSC311: Data Structures
53
Topological Sorting Example
6
7
8
9
Graphs I
CSC311: Data Structures
54
Topological Sorting Example
6
5
7
8
9
Graphs I
CSC311: Data Structures
55
Topological Sorting Example
4
6
5
7
8
9
Graphs I
CSC311: Data Structures
56
Topological Sorting Example
3
4
6
5
7
8
9
Graphs I
CSC311: Data Structures
57
Topological Sorting Example
2
3
4
6
5
7
8
9
Graphs I
CSC311: Data Structures
58
Topological Sorting Example
2
1
3
4
6
5
7
8
9
Graphs I
CSC311: Data Structures
59