Lecture 8: Prim’s Algorithm
CSC 226: Algorithms and Data Structures II Quinton Yong
quintonyong@ uvic.ca
Copyright By PowCoder代写 加微信 powcoder
Two basic facts about Trees
Let 𝑻 be a connected graph with no cycles, that is, a tree
• What happens if we add a new edge to 𝑻, without adding a new vertex?
• What happens if we remove an edge from 𝑻, without removing any vertices?
Two Fundamental Properties of MSTs
Cycle Property:
Let 𝑪 be any cycle in a weighted graph 𝑮 with distinct edge weights. Let 𝒆 be the “heaviest” edge in the cycle. Then the minimum spanning tree for 𝑮 does not contain 𝒆.
Cut Property:
Let 𝑿 be any proper subset (strictly less elements) of vertices in a weighted graph 𝑮 = (𝑽, 𝑬) with distinct edge weights, and let 𝒆 be the “lightest” edge that has exactly one endpoint in 𝑿. Then the minimum spanning tree 𝑻 for 𝑮 must contain 𝒆.
Cycle Property Proof
Cycle Property: Let 𝑪 be any cycle in a weighted graph 𝑮 with distinct edge weights. Let 𝒆 be the “heaviest” edge in the cycle. Then the minimum spanning tree for 𝑮 does not contain 𝒆.
Proof: Suppose for a contradiction that there is a cycle 𝑪 in 𝑮 such that the heaviest edge 𝒆 in 𝑪 appears in the minimum spanning tree 𝑻 of 𝑮.
Removing 𝒆 will result in two trees 𝑻𝟏 and 𝑻𝟏.
𝒆 is in the cycle 𝑪, which means there must be some other edge 𝒇 in 𝑪 that connects 𝑻𝟏 and 𝑻𝟐. 𝒘 𝒇 <𝒘 𝒆 since𝒆istheheaviestedgein𝑪.
Adding 𝒇 to connect 𝑻𝟏 and 𝑻𝟐 results in a spanning tree 𝑻′ with less weight than 𝑻.
Therefore, it is a contradiction that 𝑻 is the minimum spanning tree.
Cut Property Proof
Cut Property: Let 𝑿 be any proper subset (strictly less elements) of vertices in a weighted graph
𝑮 = (𝑽, 𝑬) with distinct edge weights, and let 𝒆 be the “lightest” edge that has exactly one endpoint in 𝑿. Then the minimum spanning tree 𝑻 for 𝑮 must contain 𝒆.
Proof: Let 𝑿 ⊂ 𝑽 such that 𝑿 ≠ ∅ and let 𝒆 be the lightest edge that connects 𝑿 and 𝑽 ∖ 𝑿. Suppose for a contradiction that MST 𝑻 of 𝑮 does not contain 𝒆.
Add 𝒆 to 𝑻.
This will create a cycle, call it 𝑪.
Because 𝒆 creates a cycle and connects 𝑿 to 𝑽 ∖ 𝑿, there must exist some edge 𝒇 that also connects 𝑿 to 𝑽 ∖ 𝑿 in 𝑻.
Remove 𝑭 giving tree 𝑻′. 𝒘 𝒆 < 𝒘 𝒇 since 𝒆 was the lightest edge connecting 𝑿 to 𝑽 ∖ 𝑿. Therefore, it is a contradiction that 𝑻 is the minimum spanning tree.
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm
• Initializetreewithsinglechosenvertex
• Grow tree by finding the lightest incident edge to all nodes in the spanning tree that’s not yet in
the tree and connect it to the tree
• Repeat until all vertices are in the tree
• Exampleofagreedyalgorithm
Prim’s Algorithm Correctness Proof
Theorem: If 𝑮 = (𝑽, 𝑬) is a connected, weighted graph with distinct edge weights, then Prim’s algorithm correctly finds the MST for 𝑮.
Proof: Let 𝑻 be the MST for 𝑮. Let 𝑺 be the spanning tree created by Prim’s algorithm. We want to show that 𝑻 = 𝑺.
We will use induction on the number of edges added to 𝑺. That is, we show that for every edge 𝒆
that Prim’s adds to 𝑺, then 𝒆 must be in 𝑻.
Let 𝒎 be the number of edges added to 𝑺.
Base case: When 𝒎 = 𝟏 (after 1 edge has been added to 𝑺). Let 𝒗𝟎 denote the starting vertex. Let
𝒆𝟏 = {𝒗𝟎, 𝒗𝟏} be that edge.
At this point, 𝑺 contains vertices 𝒗𝟎, 𝒗𝟏 and edges 𝒗𝟎, 𝒗𝟏 . We know that Prim’s algorithm picks
the lightest edge incident to 𝒗𝟎.
Let 𝑿 = {𝒗𝟎} be a cut of graph 𝑮 = (𝑽, 𝑬). By the cut property, the minimum weight edge from 𝑿 to 𝑽 − 𝑿 must be in the MST 𝑻. That edge is 𝒆𝟏. Thus, 𝒆𝟏 ∈ 𝑻.
Prim’s Algorithm Correctness Proof
Induction: Let 𝒎 = 𝒌 and let 𝑺 = 𝒗𝟎,𝒗𝟏,...,𝒗𝒌 , 𝒆𝟏,...,𝒆𝒌 be the current state of the tree built by Prim’s algorithm after 𝒌 iterations.
Assumethat𝒆𝟏,...,𝒆𝒌 areallin𝑻,theMSTfor𝑮.
Consider 𝒎 = 𝒌 + 𝟏. Run the next iteration of Prim’s, adding vertex 𝒗𝒌+𝟏 and edge 𝒆𝒌+𝟏.
𝒗𝟎, 𝒗𝟏, ... , 𝒗𝒌
be a cut of the vertex set 𝑽 in 𝑮. By the cut property, the lightest edge from 𝑿
to 𝑽 − 𝑿 must be in the MST for 𝑮. That edge is 𝒆𝒌+𝟏, by Prim’s which chooses the lightest edge out of {𝒗𝟎, 𝒗𝟏, ... , 𝒗𝒌} which does not create a cycle (i.e. exactly one endpoint in 𝑿).
Therefore, 𝒆𝒌+𝟏 is in 𝑻 and we are done. Every edge that Prim’s adds to tree 𝑺 is in the minimum spanning tree 𝑻 and adds exactly 𝒏 − 𝟏 edges.
Prim’s Algorithm Pseudocode
𝑷𝒓𝒊𝒎𝑴𝑺𝑻(𝑮):
Input: A weighted connected graph 𝑮 with 𝒏 vertices and 𝒎 edges Output: An MST 𝑻 for 𝑮
Data structures: Array 𝑫 maintains minimum distance to vertices, Indexed Priority Queue 𝑸 of distances, and Tree 𝑻
Pick an arbitrary vertex 𝒗 in 𝑮 𝑫𝒗←𝟎
for each vertex 𝒖 ≠ 𝒗 do
for each vertex 𝒖 do // including v
Add 𝒖,𝐧𝐮𝐥𝐥𝐞𝐝𝐠𝐞 ,𝑫 𝒖 while 𝑸 is not empty do
to𝑸//𝐷 𝑢 istheprioritykey
𝒖, 𝒆 ← 𝑸. 𝒓𝒆𝒎𝒐𝒗𝒆𝑴𝒊𝒏()
Add vertex 𝒖 and edge 𝒆 to 𝑻
for each vertex 𝒛 adjacent to 𝒖 such that 𝒛 is in 𝑸 do
if𝒘𝒖,𝒛 <𝑫𝒛then 𝑫𝒛 ←𝒘 𝒖,𝒛
Change 𝒛 entry in 𝑸 to
𝒛,(𝒖,𝒛) ,𝑫 𝒛
𝒂𝒃𝒄𝒅𝒆𝒇𝒈𝒉𝒊𝒋
Prim’s Algorithm Pseudocode
𝑷𝒓𝒊𝒎𝑴𝑺𝑻(𝑮):
Input: A weighted connected graph 𝑮 with 𝒏 vertices and 𝒎 edges Output: An MST 𝑻 for 𝑮
Data structures: Array 𝑫 maintains minimum distance to vertices, Indexed Priority Queue 𝑸 of distances, and Tree 𝑻
Pick an arbitrary vertex 𝒗 in 𝑮 𝑫𝒗←𝟎
for each vertex 𝒖 ≠ 𝒗 do
for each vertex 𝒖 do // including v
Add 𝒖,𝐧𝐮𝐥𝐥𝐞𝐝𝐠𝐞 ,𝑫 𝒖 while 𝑸 is not empty do
to𝑸//𝐷 𝑢 istheprioritykey
𝒖, 𝒆 ← 𝑸. 𝒓𝒆𝒎𝒐𝒗𝒆𝑴𝒊𝒏()
Add vertex 𝒖 and edge 𝒆 to 𝑻
for each vertex 𝒛 adjacent to 𝒖 such that 𝒛 is in 𝑸 do
if𝒘𝒖,𝒛 <𝑫𝒛then 𝑫𝒛 ←𝒘 𝒖,𝒛
Change 𝒛 entry in 𝑸 to
𝒛,(𝒖,𝒛) ,𝑫 𝒛
𝒂𝒃𝒄𝒅𝒆𝒇𝒈𝒉𝒊𝒋
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com