程序代写 CSC 226: Algorithms and Data Structures II Quinton ’s Algorithm

Lecture 10: Kruskal’s Algorithm
CSC 226: Algorithms and Data Structures II Quinton ’s Algorithm
• Initialize forest consisting of all nodes
• Pick a (non-selected) minimum weight edge and if it connects two different trees of the

forest, select it. Otherwise, discard it.
• Repeat until all components are connect it
• Exampleofagreedyalgorithm

Kruskal’s Algorithm
• Initialize forest consisting of all nodes
• Pick a (non-selected) minimum weight edge and if it connects two different trees of the
forest, select it. Otherwise, discard it.
• Repeat until all components are connect it
• Exampleofagreedyalgorithm

Kruskal’s Algorithm Pseudocode
𝑲𝒓𝒖𝒔𝒌𝒂𝒍𝑴𝑺𝑻(𝑮):
Input: A weighted connected graph 𝑮 with 𝒏 vertices and 𝒎 edges Output: An MST 𝑻 for 𝑮
Data structures: Disjoint set 𝑪 maintaining connected components, Priority Queue 𝑸 of edges, and Tree 𝑻
for each vertex 𝒖 in 𝑮 do
𝑪(𝒖) ← {𝒖} // 𝑪(𝒖) denotes the connected component containing 𝒖
Let 𝑸 be a min priority queue storing all edges in 𝑮 by weight while 𝑻 has less than 𝒏 − 𝟏 edges do
𝒖,𝒗 ←𝑸.𝒓𝒆𝒎𝒐𝒗𝒆𝑴𝒊𝒏()
Let 𝒖 ∈ 𝑪 𝒖
Let𝒗∈𝑪𝒗 𝟔𝟒𝟐 if 𝑪 𝒖 ≠ 𝑪 𝒗 then 𝟑
Addedge 𝒖,𝒗 to𝑻
Union𝑪 𝒖 and𝑪 𝒗 return 𝑻

Kruskal’s Algorithm Pseudocode
𝑲𝒓𝒖𝒔𝒌𝒂𝒍𝑴𝑺𝑻(𝑮):
Input: A weighted connected graph 𝑮 with 𝒏 vertices and 𝒎 edges Output: An MST 𝑻 for 𝑮
Data structures: Disjoint set 𝑪 maintaining connected components, Priority Queue 𝑸 of edges, and Tree 𝑻
for each vertex 𝒖 in 𝑮 do
𝑪(𝒖) ← {𝒖} // 𝑪(𝒖) denotes the connected component containing 𝒖
Let 𝑸 be a min priority queue storing all edges in 𝑮 by weight 𝑻←∅
while 𝑻 has less than 𝒏 − 𝟏 edges do
𝑶 𝒎 log 𝒎 but we can make this 𝑶 𝒎
𝒖,𝒗 ←𝑸.𝒓𝒆𝒎𝒐𝒗𝒆𝑴𝒊𝒏() Let 𝒖 ∈ 𝑪 𝒖
if𝑪𝒖 ≠𝑪𝒗 then
Add edge 𝒖,𝒗 to 𝑻
Union𝑪 𝒖 and𝑪 𝒗 return 𝑻
How do we implement this disjoint set efficiently such that this takes 𝑶 𝒎 log 𝒏 ?

Implementing Kruskal’s Algorithm
We need to solve two problems to efficiently implement Kruskal’s algorithm:
• Efficiently constructing (inserting all edges into) the priority queue: bottom-up heap • Efficientcycledetection:union-finddatastructure

(Min) Heap Review
Root always min element
Parent smaller than any children
Heap always a complete binary tree

Insert (𝑼𝒑𝑯𝒆𝒂𝒑()): 𝑶(𝐥𝐨𝐠(𝒏)) 𝟏𝟎

Insert (𝑼𝒑𝑯𝒆𝒂𝒑()): 𝑶(𝐥𝐨𝐠(𝒏)) 𝟐𝟎

Insert (𝑼𝒑𝑯𝒆𝒂𝒑()): 𝑶(𝐥𝐨𝐠(𝒏)) 𝟏𝟎

Remove Minimum (𝑫𝒐𝒘𝒏𝑯𝒆𝒂𝒑()): 𝑶(𝐥𝐨𝐠(𝒏)) 𝟏𝟎

Remove Minimum (𝑫𝒐𝒘𝒏𝑯𝒆𝒂𝒑()): 𝑶(𝐥𝐨𝐠(𝒏))

Remove Minimum (𝑫𝒐𝒘𝒏𝑯𝒆𝒂𝒑()): 𝑶(𝐥𝐨𝐠(𝒏)) 𝟏𝟏𝟎
Swap places with smallest child

Remove Minimum (𝑫𝒐𝒘𝒏𝑯𝒆𝒂𝒑()): 𝑶(𝐥𝐨𝐠(𝒏)) 𝟐𝟎
Swap places with smallest child

In-place Array Implementation
3𝟕𝟎 𝑖 4 𝟒𝟎
5 𝟗𝟎 6 𝟖𝟎 7 𝟏𝟓𝟎 8 𝟏𝟐𝟎 9 𝟔𝟎
10 𝟓𝟎 11 𝟏𝟎𝟎 12 𝟏𝟒𝟎 13 𝟏𝟑𝟎 14 𝟏𝟏𝟎
𝟕𝟎 𝟒𝟎 𝟗𝟎 𝟖𝟎

Bottom-Up Heap
𝑩𝒐𝒕𝒕𝒐𝒎𝑼𝒑𝑯𝒆𝒂𝒑(𝑺):
Input: A list 𝑺 storing 𝒎 keys Output: A heap 𝑻 storing the 𝒎 keys
if 𝑺 is empty then
return external node
Remove the first key 𝒌 from 𝑺 Split 𝑺 in half into lists 𝑺𝟏 and 𝑺𝟐 𝑻𝟏 ← 𝐵𝑜𝑡𝑡𝑜𝑚𝑈𝑝𝐻𝑒𝑎𝑝 𝑺𝟏
𝑻𝟐 ← 𝐵𝑜𝑡𝑡𝑜𝑚𝑈𝑝𝐻𝑒𝑎𝑝(𝑺𝟐)
𝑻 ← 𝑚𝑒𝑟𝑔𝑒(𝒌, 𝑻𝟏, 𝑻𝟐) 𝐷𝑜𝑤𝑛𝐻𝑒𝑎𝑝 𝑻,𝒓𝒐𝒐𝒕

Bottom-Up Heap
𝑩𝒐𝒕𝒕𝒐𝒎𝑼𝒑𝑯𝒆𝒂𝒑(𝑺):
Input: A list 𝑺 storing 𝒎 keys Output: A heap 𝑻 storing the 𝒎 keys
if 𝑺 is empty then
return external node
𝟖𝟎 𝟓𝟎 𝟒𝟎 𝟔𝟎
Remove the first key 𝒌 from 𝑺 Split 𝑺 in half into lists 𝑺𝟏 and 𝑺𝟐 𝑻𝟏 ← 𝐵𝑜𝑡𝑡𝑜𝑚𝑈𝑝𝐻𝑒𝑎𝑝 𝑺𝟏
𝑻𝟐 ← 𝐵𝑜𝑡𝑡𝑜𝑚𝑈𝑝𝐻𝑒𝑎𝑝(𝑺𝟐)
𝑻 ← 𝑚𝑒𝑟𝑔𝑒(𝒌, 𝑻𝟏, 𝑻𝟐) 𝐷𝑜𝑤𝑛𝐻𝑒𝑎𝑝 𝑻,𝒓𝒐𝒐𝒕
Merging two heaps
𝟖𝟎 𝟓𝟎 𝟕𝟎 𝟔𝟎

Proof Idea (Painting Proof)
For each new node joining two heaps: mark path of maximum number of bubble-down operations Without loss of generality, when marking (swapping), first go right then left until bottom

Did we insert all 𝒎 elements in 𝑶 𝒎 time? Heaps of height 1

Did we insert all 𝒎 elements in 𝑶 𝒎 time? Heaps of height 2

Did we insert all 𝒎 elements in 𝑶 𝒎 time? Heaps of height 3

Did we insert all 𝒎 elements in 𝑶 𝒎 time? Heaps of height 4

Did we insert all 𝒎 elements in 𝑶 𝒎 time?
Each edge is painted at most once and there are edges which remain unpainted. Hence, the number of swap operations is less than the number of edges in the heap. The number of edges in the heap is 𝟐𝒎.
Therefore, constructing this heap takes 𝑶 𝒎 time.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts