Courses

# Graphs and Minimum spanning trees - PPT, Introduction to Algorithms Notes | EduRev

## : Graphs and Minimum spanning trees - PPT, Introduction to Algorithms Notes | EduRev

``` Page 1

Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 1
Graphs and Minimum
spanning trees
Graphs
Definition. A directed graph (digraph) G =
(V, E) is an ordered pair consisting of
• a set V of vertices (singular: vertex),
• a set E ? V × V of edges.
In an undirected graph G = (V, E), the edge
set E consists of unordered pairs of vertices.
In either case, we have |E| = O(|V|
2
).
Moreover, if G is connected, then  |E| = |V| – 1.
(Review CLRS, Appendix B.4 and B.5.)
u
v
w
x
y
representation
The adjacency matrix of a graph G = (V, E), where
V = {1, 2, …, n}, is the matrix A[1 . . n, 1 . . n]
given by
A[i, j] =
1 if (i, j) ? E,
0 if (i, j) ? E.
2 1
3 4
A 1 2 3 4
1
2
3
4
0 1 1 0
0 0 1 0
0 0 0 0
0 0 1 0
T(|V|
2
) storage
 dense
representation.
An adjacency list of a vertex v ? V is the list Adj[v]
2 1
3 4
For undirected graphs, |Adj[v]| = degree(v).
For digraphs, | Adj[v] | = out-degree(v).
Handshaking Lemma:
• For undirected graphs:

v?V
degree(v) = 2|E|
• For digraphs:

v?V
in-degree(v) + 
v?V
out-degree(v) = 2 | E |
•Claim: In any party, there is an even number of
people that shake an odd number of hand.
 adjacency lists use T(|V| + |E|) storage
 a sparse representation
Paths in a graph
•A simple path between vertices u and v is a list
of edges,  each edge is ordered, each consecutive
pair share a vertex (the last vertex of one edge is
the first vertex of the following edge)  and a each
vertex is used by at most two edges.
•A graph is connected if there is a path between
every pair of vertices.
•The length of the path is the number of edges in
the path.
Page 2

Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 1
Graphs and Minimum
spanning trees
Graphs
Definition. A directed graph (digraph) G =
(V, E) is an ordered pair consisting of
• a set V of vertices (singular: vertex),
• a set E ? V × V of edges.
In an undirected graph G = (V, E), the edge
set E consists of unordered pairs of vertices.
In either case, we have |E| = O(|V|
2
).
Moreover, if G is connected, then  |E| = |V| – 1.
(Review CLRS, Appendix B.4 and B.5.)
u
v
w
x
y
representation
The adjacency matrix of a graph G = (V, E), where
V = {1, 2, …, n}, is the matrix A[1 . . n, 1 . . n]
given by
A[i, j] =
1 if (i, j) ? E,
0 if (i, j) ? E.
2 1
3 4
A 1 2 3 4
1
2
3
4
0 1 1 0
0 0 1 0
0 0 0 0
0 0 1 0
T(|V|
2
) storage
 dense
representation.
An adjacency list of a vertex v ? V is the list Adj[v]
2 1
3 4
For undirected graphs, |Adj[v]| = degree(v).
For digraphs, | Adj[v] | = out-degree(v).
Handshaking Lemma:
• For undirected graphs:

v?V
degree(v) = 2|E|
• For digraphs:

v?V
in-degree(v) + 
v?V
out-degree(v) = 2 | E |
•Claim: In any party, there is an even number of
people that shake an odd number of hand.
 adjacency lists use T(|V| + |E|) storage
 a sparse representation
Paths in a graph
•A simple path between vertices u and v is a list
of edges,  each edge is ordered, each consecutive
pair share a vertex (the last vertex of one edge is
the first vertex of the following edge)  and a each
vertex is used by at most two edges.
•A graph is connected if there is a path between
every pair of vertices.
•The length of the path is the number of edges in
the path.
Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 2
Trees
•A tree is a connected graph without cycles.
•A graph is a tree is there is a unique path
between every pair of vertices.
•In a tree |E|=|V|-1
Minimum spanning trees
Input: A connected, undirected graph G = (V, E)
with weights assign to each edge (a real value).
• For simplicity, assume that all edge weights are
distinct. (CLRS covers the general case.)

?
=
T v u
v u w T w
) , (
) , ( ) ( .
Output: A spanning tree T — a tree that connects
all vertices — of minimum weight:
The weight of the graph is the sum of weights of
its edges
Example of MST
6 12
5
14
3
8
10
15
9
7
Hallmark for “greedy”
algorithms
Greedy-choice property
A locally optimal choice
is globally optimal.
Theorem. Let T be the MST of G = (V, E), and let A
? V.  Suppose that (u, v) ? E is the least-weight edge
connecting A to V \ A. Then, (u, v) ? T.
A V\A
5
9
14
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V \ A
T:
u
v
(u, v) = least-weight edge
connecting A to V \ A
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V – A
T:
u
Consider the unique simple path from u to v in T.
(u, v) = least-weight edge
connecting A to V – A
v
Page 3

Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 1
Graphs and Minimum
spanning trees
Graphs
Definition. A directed graph (digraph) G =
(V, E) is an ordered pair consisting of
• a set V of vertices (singular: vertex),
• a set E ? V × V of edges.
In an undirected graph G = (V, E), the edge
set E consists of unordered pairs of vertices.
In either case, we have |E| = O(|V|
2
).
Moreover, if G is connected, then  |E| = |V| – 1.
(Review CLRS, Appendix B.4 and B.5.)
u
v
w
x
y
representation
The adjacency matrix of a graph G = (V, E), where
V = {1, 2, …, n}, is the matrix A[1 . . n, 1 . . n]
given by
A[i, j] =
1 if (i, j) ? E,
0 if (i, j) ? E.
2 1
3 4
A 1 2 3 4
1
2
3
4
0 1 1 0
0 0 1 0
0 0 0 0
0 0 1 0
T(|V|
2
) storage
 dense
representation.
An adjacency list of a vertex v ? V is the list Adj[v]
2 1
3 4
For undirected graphs, |Adj[v]| = degree(v).
For digraphs, | Adj[v] | = out-degree(v).
Handshaking Lemma:
• For undirected graphs:

v?V
degree(v) = 2|E|
• For digraphs:

v?V
in-degree(v) + 
v?V
out-degree(v) = 2 | E |
•Claim: In any party, there is an even number of
people that shake an odd number of hand.
 adjacency lists use T(|V| + |E|) storage
 a sparse representation
Paths in a graph
•A simple path between vertices u and v is a list
of edges,  each edge is ordered, each consecutive
pair share a vertex (the last vertex of one edge is
the first vertex of the following edge)  and a each
vertex is used by at most two edges.
•A graph is connected if there is a path between
every pair of vertices.
•The length of the path is the number of edges in
the path.
Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 2
Trees
•A tree is a connected graph without cycles.
•A graph is a tree is there is a unique path
between every pair of vertices.
•In a tree |E|=|V|-1
Minimum spanning trees
Input: A connected, undirected graph G = (V, E)
with weights assign to each edge (a real value).
• For simplicity, assume that all edge weights are
distinct. (CLRS covers the general case.)

?
=
T v u
v u w T w
) , (
) , ( ) ( .
Output: A spanning tree T — a tree that connects
all vertices — of minimum weight:
The weight of the graph is the sum of weights of
its edges
Example of MST
6 12
5
14
3
8
10
15
9
7
Hallmark for “greedy”
algorithms
Greedy-choice property
A locally optimal choice
is globally optimal.
Theorem. Let T be the MST of G = (V, E), and let A
? V.  Suppose that (u, v) ? E is the least-weight edge
connecting A to V \ A. Then, (u, v) ? T.
A V\A
5
9
14
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V \ A
T:
u
v
(u, v) = least-weight edge
connecting A to V \ A
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V – A
T:
u
Consider the unique simple path from u to v in T.
(u, v) = least-weight edge
connecting A to V – A
v
Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 3
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V – A
T:
u
(u, v) = least-weight edge
connecting A to V – A
v
Consider the unique simple path from u to v in T.
Swap (u, v) with the first edge on this path that
connects a vertex in A to a vertex in V \ A.
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V – A
T':
u
(u, v) = least-weight edge
connecting A to V – A
v
Consider the unique simple path from u to v in T.
Swap (u, v) with the first edge on this path that
connects a vertex in A to a vertex in V – A.
A lighter-weight spanning tree than T results.
Prim’s alg – main ideas
V\A
9
14
A
2
9
7
•Maintain a MST for the set A of vertices
•Maintains for each vertex of V\A the edge
with min-weight connecting it to A.
•Add at each iteration the vertex with min
weight.
14
2
9
Prim’s algorithm
IDEA: Maintain V \ A as a priority queue Q.  Key
each vertex in Q with the weight of the least-
weight edge connecting it to a vertex in A.
Q ? V
key[v] ? 8 for all v ? V
key[s] ? 0 for some arbitrary s ? V
while Q ? Ø
do u ? EXTRACT-MIN(Q)
do if v ? Q and w(u, v) < key[v]
then key[v] ? w(u, v)  DECREASE-KEY
p[v] ? u
At the end, {(v, p[v])} forms the MST.
Example of Prim’s algorithm
? A
? V \ A
8
8 8
8 0
8
8
8
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
8
8 8
8 0
8
8
8
6 12
5
14
3
8
10
15
9
7
Page 4

Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 1
Graphs and Minimum
spanning trees
Graphs
Definition. A directed graph (digraph) G =
(V, E) is an ordered pair consisting of
• a set V of vertices (singular: vertex),
• a set E ? V × V of edges.
In an undirected graph G = (V, E), the edge
set E consists of unordered pairs of vertices.
In either case, we have |E| = O(|V|
2
).
Moreover, if G is connected, then  |E| = |V| – 1.
(Review CLRS, Appendix B.4 and B.5.)
u
v
w
x
y
representation
The adjacency matrix of a graph G = (V, E), where
V = {1, 2, …, n}, is the matrix A[1 . . n, 1 . . n]
given by
A[i, j] =
1 if (i, j) ? E,
0 if (i, j) ? E.
2 1
3 4
A 1 2 3 4
1
2
3
4
0 1 1 0
0 0 1 0
0 0 0 0
0 0 1 0
T(|V|
2
) storage
 dense
representation.
An adjacency list of a vertex v ? V is the list Adj[v]
2 1
3 4
For undirected graphs, |Adj[v]| = degree(v).
For digraphs, | Adj[v] | = out-degree(v).
Handshaking Lemma:
• For undirected graphs:

v?V
degree(v) = 2|E|
• For digraphs:

v?V
in-degree(v) + 
v?V
out-degree(v) = 2 | E |
•Claim: In any party, there is an even number of
people that shake an odd number of hand.
 adjacency lists use T(|V| + |E|) storage
 a sparse representation
Paths in a graph
•A simple path between vertices u and v is a list
of edges,  each edge is ordered, each consecutive
pair share a vertex (the last vertex of one edge is
the first vertex of the following edge)  and a each
vertex is used by at most two edges.
•A graph is connected if there is a path between
every pair of vertices.
•The length of the path is the number of edges in
the path.
Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 2
Trees
•A tree is a connected graph without cycles.
•A graph is a tree is there is a unique path
between every pair of vertices.
•In a tree |E|=|V|-1
Minimum spanning trees
Input: A connected, undirected graph G = (V, E)
with weights assign to each edge (a real value).
• For simplicity, assume that all edge weights are
distinct. (CLRS covers the general case.)

?
=
T v u
v u w T w
) , (
) , ( ) ( .
Output: A spanning tree T — a tree that connects
all vertices — of minimum weight:
The weight of the graph is the sum of weights of
its edges
Example of MST
6 12
5
14
3
8
10
15
9
7
Hallmark for “greedy”
algorithms
Greedy-choice property
A locally optimal choice
is globally optimal.
Theorem. Let T be the MST of G = (V, E), and let A
? V.  Suppose that (u, v) ? E is the least-weight edge
connecting A to V \ A. Then, (u, v) ? T.
A V\A
5
9
14
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V \ A
T:
u
v
(u, v) = least-weight edge
connecting A to V \ A
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V – A
T:
u
Consider the unique simple path from u to v in T.
(u, v) = least-weight edge
connecting A to V – A
v
Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 3
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V – A
T:
u
(u, v) = least-weight edge
connecting A to V – A
v
Consider the unique simple path from u to v in T.
Swap (u, v) with the first edge on this path that
connects a vertex in A to a vertex in V \ A.
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V – A
T':
u
(u, v) = least-weight edge
connecting A to V – A
v
Consider the unique simple path from u to v in T.
Swap (u, v) with the first edge on this path that
connects a vertex in A to a vertex in V – A.
A lighter-weight spanning tree than T results.
Prim’s alg – main ideas
V\A
9
14
A
2
9
7
•Maintain a MST for the set A of vertices
•Maintains for each vertex of V\A the edge
with min-weight connecting it to A.
•Add at each iteration the vertex with min
weight.
14
2
9
Prim’s algorithm
IDEA: Maintain V \ A as a priority queue Q.  Key
each vertex in Q with the weight of the least-
weight edge connecting it to a vertex in A.
Q ? V
key[v] ? 8 for all v ? V
key[s] ? 0 for some arbitrary s ? V
while Q ? Ø
do u ? EXTRACT-MIN(Q)
do if v ? Q and w(u, v) < key[v]
then key[v] ? w(u, v)  DECREASE-KEY
p[v] ? u
At the end, {(v, p[v])} forms the MST.
Example of Prim’s algorithm
? A
? V \ A
8
8 8
8 0
8
8
8
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
8
8 8
8 0
8
8
8
6 12
5
14
3
8
10
15
9
7
Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 4
Example of Prim’s algorithm
? A
? V \ A
8
8 7
8 0
10
8
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
8
8 7
8 0
10
8
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
12
5 7
8 0
10
9
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
12
5 7
8 0
10
9
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
6
5 7
14 0
8
9
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
6
5 7
14 0
8
9
15
6 12
5
14
3
8
10
15
9
7
Page 5

Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 1
Graphs and Minimum
spanning trees
Graphs
Definition. A directed graph (digraph) G =
(V, E) is an ordered pair consisting of
• a set V of vertices (singular: vertex),
• a set E ? V × V of edges.
In an undirected graph G = (V, E), the edge
set E consists of unordered pairs of vertices.
In either case, we have |E| = O(|V|
2
).
Moreover, if G is connected, then  |E| = |V| – 1.
(Review CLRS, Appendix B.4 and B.5.)
u
v
w
x
y
representation
The adjacency matrix of a graph G = (V, E), where
V = {1, 2, …, n}, is the matrix A[1 . . n, 1 . . n]
given by
A[i, j] =
1 if (i, j) ? E,
0 if (i, j) ? E.
2 1
3 4
A 1 2 3 4
1
2
3
4
0 1 1 0
0 0 1 0
0 0 0 0
0 0 1 0
T(|V|
2
) storage
 dense
representation.
An adjacency list of a vertex v ? V is the list Adj[v]
2 1
3 4
For undirected graphs, |Adj[v]| = degree(v).
For digraphs, | Adj[v] | = out-degree(v).
Handshaking Lemma:
• For undirected graphs:

v?V
degree(v) = 2|E|
• For digraphs:

v?V
in-degree(v) + 
v?V
out-degree(v) = 2 | E |
•Claim: In any party, there is an even number of
people that shake an odd number of hand.
 adjacency lists use T(|V| + |E|) storage
 a sparse representation
Paths in a graph
•A simple path between vertices u and v is a list
of edges,  each edge is ordered, each consecutive
pair share a vertex (the last vertex of one edge is
the first vertex of the following edge)  and a each
vertex is used by at most two edges.
•A graph is connected if there is a path between
every pair of vertices.
•The length of the path is the number of edges in
the path.
Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 2
Trees
•A tree is a connected graph without cycles.
•A graph is a tree is there is a unique path
between every pair of vertices.
•In a tree |E|=|V|-1
Minimum spanning trees
Input: A connected, undirected graph G = (V, E)
with weights assign to each edge (a real value).
• For simplicity, assume that all edge weights are
distinct. (CLRS covers the general case.)

?
=
T v u
v u w T w
) , (
) , ( ) ( .
Output: A spanning tree T — a tree that connects
all vertices — of minimum weight:
The weight of the graph is the sum of weights of
its edges
Example of MST
6 12
5
14
3
8
10
15
9
7
Hallmark for “greedy”
algorithms
Greedy-choice property
A locally optimal choice
is globally optimal.
Theorem. Let T be the MST of G = (V, E), and let A
? V.  Suppose that (u, v) ? E is the least-weight edge
connecting A to V \ A. Then, (u, v) ? T.
A V\A
5
9
14
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V \ A
T:
u
v
(u, v) = least-weight edge
connecting A to V \ A
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V – A
T:
u
Consider the unique simple path from u to v in T.
(u, v) = least-weight edge
connecting A to V – A
v
Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 3
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V – A
T:
u
(u, v) = least-weight edge
connecting A to V – A
v
Consider the unique simple path from u to v in T.
Swap (u, v) with the first edge on this path that
connects a vertex in A to a vertex in V \ A.
Proof of theorem
Proof. Suppose (u, v) ? T. Cut and paste.
? A
? V – A
T':
u
(u, v) = least-weight edge
connecting A to V – A
v
Consider the unique simple path from u to v in T.
Swap (u, v) with the first edge on this path that
connects a vertex in A to a vertex in V – A.
A lighter-weight spanning tree than T results.
Prim’s alg – main ideas
V\A
9
14
A
2
9
7
•Maintain a MST for the set A of vertices
•Maintains for each vertex of V\A the edge
with min-weight connecting it to A.
•Add at each iteration the vertex with min
weight.
14
2
9
Prim’s algorithm
IDEA: Maintain V \ A as a priority queue Q.  Key
each vertex in Q with the weight of the least-
weight edge connecting it to a vertex in A.
Q ? V
key[v] ? 8 for all v ? V
key[s] ? 0 for some arbitrary s ? V
while Q ? Ø
do u ? EXTRACT-MIN(Q)
do if v ? Q and w(u, v) < key[v]
then key[v] ? w(u, v)  DECREASE-KEY
p[v] ? u
At the end, {(v, p[v])} forms the MST.
Example of Prim’s algorithm
? A
? V \ A
8
8 8
8 0
8
8
8
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
8
8 8
8 0
8
8
8
6 12
5
14
3
8
10
15
9
7
Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 4
Example of Prim’s algorithm
? A
? V \ A
8
8 7
8 0
10
8
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
8
8 7
8 0
10
8
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
12
5 7
8 0
10
9
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
12
5 7
8 0
10
9
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
6
5 7
14 0
8
9
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
6
5 7
14 0
8
9
15
6 12
5
14
3
8
10
15
9
7
Introduction to Algorithms, Lecture 16 November 7, 2001
© 2001 by Charles E. Leiserson 5
Example of Prim’s algorithm
? A
? V \ A
6
5 7
14 0
8
9
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
6
5 7
3 0
8
9
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
6
5 7
3 0
8
9
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
6
5 7
3 0
8
9
15
6 12
5
14
3
8
10
15
9
7
Example of Prim’s algorithm
? A
? V \ A
6
5 7
3 0
8
9
15
6 12
5
14
3
8
10
15
9
7
Handshaking Lemma  T(|E|) implicit DECREASE-KEY’s.
Q ? V
key[v] ? 8 for all v ? V
key[s] ? 0 for some arbitrary s ? V
while Q ? Ø
do u ? EXTRACT-MIN(Q)
do if v ? Q and w(u, v) < key[v]
then key[v] ? w(u, v)
p[v] ? u
Analysis of Prim
degree(u)
times
|V |
times
T(|V|)
total
Time = T(|V|)·T
EXTRACT-MIN
+ T(|E|)·T
DECREASE-KEY
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!