February 19, 2009
1
(Review CLRS, Appendix B.) February 19, 2009
2
February 19, 2009
3
Analysis of Algorithms
Graphs (review)
Adjacency-matrix representation
Adjacency-matrix representation
Adjacency-list representation
Adjacency-list representation
212
For undirected graphs, |Adj[v]| = degree(v). For digraphs, |Adj[v]| = out-degree(v).
2 1
1 0 1 1 0 Θ(V ) storage 20010 ⇒dense
3 4
30000 40010
representation. 4
34
February 19, 2009
February 19, 2009
5
February 19, 2009 6
LECTURES 20-21
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.
The adjacency matrix of a graph G = (V, E), where V = {1, 2, …, n}, is the matrix A[1 . . n, 1 . . n]
Greedy Algorithms
• Graphs
given by
1 if (i, j) ∈ E, 0 if(i,j)∉E.
• Minimum spanning trees
A[i, j] =
•Optimalsubstructure
InanundirectedgraphG=(V,E),theedge set E consists of unordered pairs of vertices.
• Greedy choice
•Prim’sgreedyMST algorithm
Ineithercase,wehave|E|=O(V2). Moreover, if G is connected, then |E| ≥ |V| – 1, which implies that lg|E| = Θ(lgV).
The adjacency matrix of a graph G = (V, E), where V = {1, 2, …, n}, is the matrix A[1 . . n, 1 . . n]
An adjacency list of a vertex v ∈ V is the list Adj[v] of vertices adjacent to v.
An adjacency list of a vertex v ∈ V is the list Adj[v] of vertices adjacent to v.
given by
2 1
Adj[1] = {2, 3}
2 1
Adj[1] = {2, 3} Adj[2] = {3} Adj[3] = {} Adj[4] = {3}
A[i, j] = A1234
Adj[3] = {}
34 34
1 if(i,j)∈E, 0 if(i,j)∉E.
21 34
Adj[2] = {3}
2 1 3 4
Adjacency-list representation
Minimum spanning trees
Minimum spanning trees
An adjacency list of a vertex v ∈ V is the list Adj[v] of vertices adjacent to v.
Input: A connected, undirected graph G = (V, E) with weight function w : E → R.
Input: A connected, undirected graph G = (V, E) with weight function w : E → R.
2 1
Adj[1] = {2, 3} Adj[2] = {3} Adj[3] = {} Adj[4] = {3}
21
• For simplicity, assume that all edge weights are distinct. (CLRS covers the general case.)
• For simplicity, assume that all edge weights are distinct. (CLRS covers the general case.)
34
3 4
Output: A spanning tree T — a tree that connects all vertices — of minimum weight:
For undirected graphs, |Adj[v]| = degree(v). For digraphs, |Adj[v]| = out-degree(v).
w(T)= ∑w(u,v). ( u , v )∈T
Handshaking Lemma: ∑v∈V degree(v) = 2|E| for undirected graphs ⇒ adjacency lists use Θ(V + E) storage — a sparse representation.
February 19, 2009 7
February 19, 2009
8
February 19, 2009
9
Adj[4] = {3}
Example of MST Example of MST
Optimal substructure
are not shown.)
Remove any edge (u, v) ∈ T.
v
are not shown.)
Remove any edge (u, v) ∈ T.
v
are not shown.)
into two subtrees T1 and T2.
February 19, 2009
13
February 19, 2009
14
February 19, 2009 15
MST T: (Other edges of G
u T
Proof. Cut and paste:
w(T) = w(u, v) + w(T1) + w(T2).
Proof. Cut and paste:
w(T) = w(u, v) + w(T1) + w(T2).
are not shown.)
1
v
If T1′ were a lower-weight spanning tree than T1 for G1,thenT′={(u,v)}∪T1′∪T2 wouldbea lower-weight spanning tree than T for G.
If T1′ were a lower-weight spanning tree than T1 for G1,thenT′={(u,v)}∪T1′∪T2 wouldbea lower-weight spanning tree than T for G.
6 12 6 12 59 59
MST T: (Other edges of G
14 8 7 15 3 10
14 8 7 15 3 10
February 19, 2009 10
February 19, 2009
11
February 19, 2009 12
Optimal substructure
Optimal substructure
Optimal substructure
MST T: u (Other edges of G
MST T: (Other edges of G
u
MST T: (Other edges of G
u
Optimal substructure
Proof of optimal substructure
Proof of optimal substructure
T
2
Remove any edge (u, v) ∈ T. Then, T is partitioned into two subtrees T1 and T2.
Theorem. The subtree T1 is an MST of G1 = (V1, E1), the subgraph of G induced by the vertices of T1:
Do we also have overlapping subproblems? •Yes.
V1 = vertices of T1,
E1 ={(x,y)∈E:x,y∈V1}.
Similarly for T2.
February 19, 2009 16
February 19, 2009
17
February 19, 2009 18
are not shown.)
T2
Remove any edge (u, v) ∈ T. Then, T is partitioned
T1
v
February 19, 2009
19
February 19, 2009 20
February 19, 2009 21
Proof of optimal substructure
Hallmark for “greedy” algorithms
Hallmark for “greedy” algorithms
Proof. Cut and paste:
w(T) = w(u, v) + w(T1) + w(T2).
Greedy-choice property
Greedy-choice property
If T1′ were a lower-weight spanning tree than T1 for G1, then T ′ = {(u, v)} ∪ T1′ ∪ T2 would be a lower-weight spanning tree than T for G.
A locally optimal choice is globally optimal.
A locally optimal choice is globally optimal.
Do we also have overlapping subproblems? •Yes.
Great, then dynamic programming may work!
Theorem. Let T be the MST of G = (V, E), andletA⊆V. Supposethat(u,v)∈Eisthe least-weight edge connecting A to V – A. Then, (u, v) ∈ T.
•Yes, but MST exhibits another powerful property which leads to an even more efficient algorithm.
Proof of theorem
Proof of theorem
Proof of theorem
Proof. Suppose (u, v) ∉ T. Cut and paste. T: v T: v T: v
Proof. Suppose (u, v) ∉ T. Cut and paste.
Proof. Suppose (u, v) ∉ T. Cut and paste.
∈Au ∈Au ∈Au
∈ V – A
(u, v) = least-weight edge connecting A to V – A
∈ V – A (u, v) = least-weight edge connecting A to V – A
∈ V – A (u, v) = least-weight edge connecting A to V – A
February 19, 2009
22
February 19, 2009 23
connects a vertex in A to a vertex in V – A.
February 19, 2009 24
Proof of theorem
Prim’s algorithm
Example of Prim’s algorithm
Proof. Suppose (u, v) ∉ T. Cut and paste.
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 ∞5∞9∞ key[v]←∞forallv∈V ∞ ∞ ∞ key[s] ← 0 for some arbitrary s ∈ V 14 7 15
T′: ∈Au
v
(u, v) = least-weight edge
∈A 6∞12 ∈ V – A
∈ V – A
Consider the unique simple path from u to v in T.
whileQ≠∅ ∞80∞
connecting A to V – A Swap (u, v) with the first edge on this path that
do u ← EXTRACT-MIN(Q) for each v ∈ Adj[u]
∞
0
∞
connects a vertex in A to a vertex in V – A.
⊳ DECREASE-KEY At the end, {(v, π[v])} forms the MST.
∞
A lighter-weight spanning tree than T results. February 19, 2009
25
π[v] ← u
February 19, 2009 26
February 19, 2009
27
Consider the unique simple path from u to v in T.
Consider the unique simple path from u to v in T. Swap (u, v) with the first edge on this path that
do if v ∈ Q and w(u, v) < key[v] then key[v] ← w(u, v)
3
∞
10
∞
February 19, 2009
28 February 19, 2009 29 February 19, 2009 30
February 19, 2009
31 February 19, 2009 32 February 19, 2009 33
Example of Prim’s algorithm Example of Prim’s algorithm Example of Prim’s algorithm
∈A 6∞12 ∈V–A59
∈A 6 ∞ 12 ∈A 6 ∞ 12 ∈V–A59 ∈V–A59
∞∞∞
∞∞∞
∞7∞ ∞7∞ ∞7∞ ∞7∞
∞∞∞
14 8 7 15 ∞0∞
14 8 7 15 14 8 7 15 ∞015 ∞015
∞0∞ 3 10
∞015 ∞015 3 10 3 10
∞ 10 10
∞ 10 10
Example of Prim’s algorithm Example of Prim’s algorithm Example of Prim’s algorithm
12 12 6
∈A 6 12 12 ∈A 6 12 12 ∈A 6 6 12 ∈V–A59 ∈V–A59 ∈V–A59
579 579 579 579 579 579
14 8 7 15
14 8 7 15
14 8 7 15
∞ 015 ∞ 015
∞ 015 ∞ 015
14 015 14 015
3 10
3 10
3 10
10 10 8
10 10 8
Example of Prim’s algorithm Example of Prim’s algorithm Example of Prim’s algorithm
666
∈A 6 6 12 ∈A 6 6 12 ∈A 6 6 12 ∈V–A59 ∈V–A59 ∈V–A59
February 19, 2009
34 February 19, 2009 35 February 19, 2009
36
579 579 579 579 579 579
14 8
7 15
14 8
7 15
14 8
7 15
14
0 15 0 15
14
0 15 0 15
3
0 15 0 15
14
14
3
3 10
3 10
3 10
888 888
February 19, 2009
40
February 19, 2009
41
February 19, 2009
42
|V| times
do u ← EXTRACT-MIN(Q) for each v ∈ Adj[u]
|V| times
do u ← EXTRACT-MIN(Q) for each v ∈ Adj[u]
|V| times
do u ← EXTRACT-MIN(Q) for each v ∈ Adj[u]
Example of Prim’s algorithm Example of Prim’s algorithm Example of Prim’s algorithm
666
∈A 6 6 12 ∈A 6 6 12 ∈A 6 6 12 ∈V–A59 ∈V–A59 ∈V–A59
Θ(V) total
key[v] ← ∞ for all v ∈ V
key[s] ← 0 for some arbitrary s ∈ V while Q ≠ ∅
Θ(V) total
key[v] ← ∞ for all v ∈ V
key[s] ← 0 for some arbitrary s ∈ V while Q ≠ ∅
Θ(V) total
key[v] ← ∞ for all v ∈ V
key[s] ← 0 for some arbitrary s ∈ V while Q ≠ ∅
February 19, 2009
43
February 19, 2009 44
Time = Θ(V)·TEXTRACT-MIN + Θ(E)·TDECREASE-KEY February 19, 2009 45
degree(u) times
do if v ∈ Q and w(u, v) < key[v] then key[v] ← w(u, v)
degree(u) times
do if v ∈ Q and w(u, v) < key[v] then key[v] ← w(u, v)
degree(u) times
do if v ∈ Q and w(u, v) < key[v] then key[v] ← w(u, v)
579 579 579 579 579 579
14 8 7 15
14 8 7 15
14 8 7 15
3 015 3 015
3 015 3 015
3 015 3 015
3 10
3 10
3 10
888
888
February 19, 2009 37 February 19, 2009 38 February 19, 2009 39
Analysis of Prim Analysis of Prim Analysis of Prim
Q←V Q←V Q←V
key[v] ← ∞ for all v ∈ V
key[s] ← 0 for some arbitrary s ∈ V while Q ≠ ∅
Θ(V) total
key[v] ← ∞ for all v ∈ V
key[s] ← 0 for some arbitrary s ∈ V while Q ≠ ∅
Θ(V) total
key[v] ← ∞ for all v ∈ V
key[s] ← 0 for some arbitrary s ∈ V while Q ≠ ∅
do u ← EXTRACT-MIN(Q) for each v ∈ Adj[u]
do u ← EXTRACT-MIN(Q) for each v ∈ Adj[u]
|V| times
do u ← EXTRACT-MIN(Q) for each v ∈ Adj[u]
Analysis of Prim
Analysis of Prim
Analysis of Prim
doif v∈Qandw(u,v)