Scribd
Upload
27 views13 pages

AoA Module 3 Note 5 Prims Algorithm MCST

Prim's algorithm incrementally builds a Minimum Cost Spanning Tree (MCST) by starting with any vertex and connecting additional vertices using the minimum weight edge from the tree to the outside. The algorithm's correctness is supported by the Minimum Separator Lemma, and its implementation is similar to Dijkstra's algorithm, though with a different distance update rule. The complexity of Prim's algorithm is O(n^2), primarily due to the need to identify the unvisited vertex with the minimum distance.

Uploaded by

shivamteli07
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
27 views13 pages

AoA Module 3 Note 5 Prims Algorithm MCST

Prim's algorithm incrementally builds a Minimum Cost Spanning Tree (MCST) by starting with any vertex and connecting additional vertices using the minimum weight edge from the tree to the outside. The algorithm's correctness is supported by the Minimum Separator Lemma, and its implementation is similar to Dijkstra's algorithm, though with a different distance update rule. The complexity of Prim's algorithm is O(n^2), primarily due to the need to identify the unvisited vertex with the minimum distance.

Uploaded by

shivamteli07
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Prim’s algorithm

G = (V , E ), W : E → R

Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 3 / 10
Prim’s algorithm

G = (V , E ), W : E → R
Incrementally build an MCST
TV ⊆ V : tree vertices, already added to MCST
TE ⊆ E : tree edges, already added to MCST

Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 3 / 10
Prim’s algorithm

G = (V , E ), W : E → R
Incrementally build an MCST
TV ⊆ V : tree vertices, already added to MCST
TE ⊆ E : tree edges, already added to MCST

Initially, TV = TE = ∅

Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 3 / 10
Prim’s algorithm

G = (V , E ), W : E → R
Incrementally build an MCST
TV ⊆ V : tree vertices, already added to MCST
TE ⊆ E : tree edges, already added to MCST

Initially, TV = TE = ∅
Choose minimum weight edge e = (i, j)
Set TV = {i, j}, TE = {e} MCST

Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 3 / 10
Prim’s algorithm

G = (V , E ), W : E → R
Incrementally build an MCST
TV ⊆ V : tree vertices, already added to MCST
TE ⊆ E : tree edges, already added to MCST

Initially, TV = TE = ∅
Choose minimum weight edge e = (i, j)
Set TV = {i, j}, TE = {e} MCST

Repeat n − 2 times
Choose minimum weight edge f = (u, v ) such that
u ∈ TV , v ∈
/ TV
Add v to TV , f to TE
Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 3 / 10
Prim’s algorithm

G = (V , E ), W : E → R Example

Incrementally build an MCST 70


3 4
TV ⊆ V : tree vertices, already added to MCST 18 6 8
TE ⊆ E : tree edges, already added to MCST
10 20
0 1 2
Initially, TV = TE = ∅
Choose minimum weight edge e = (i, j) TV = ∅
Set TV = {i, j}, TE = {e} MCST TE = ∅
Repeat n − 2 times
Choose minimum weight edge f = (u, v ) such that
u ∈ TV , v ∈
/ TV
Add v to TV , f to TE
Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 3 / 10
Prim’s algorithm

G = (V , E ), W : E → R Example

Incrementally build an MCST 70


3 4
TV ⊆ V : tree vertices, already added to MCST 18 6 8
TE ⊆ E : tree edges, already added to MCST
10 20
0 1 2
Initially, TV = TE = ∅
Choose minimum weight edge e = (i, j) TV = {1, 3}
Set TV = {i, j}, TE = {e} MCST TE = {(1, 3)}
Repeat n − 2 times
Choose minimum weight edge f = (u, v ) such that
u ∈ TV , v ∈
/ TV
Add v to TV , f to TE
Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 3 / 10
Prim’s algorithm

G = (V , E ), W : E → R Example

Incrementally build an MCST 70


3 4
TV ⊆ V : tree vertices, already added to MCST 18 6 8
TE ⊆ E : tree edges, already added to MCST
10 20
0 1 2
Initially, TV = TE = ∅
Choose minimum weight edge e = (i, j) TV = {1, 3, 0}
Set TV = {i, j}, TE = {e} MCST TE = {(1, 3), (1, 0)}
Repeat n − 2 times
Choose minimum weight edge f = (u, v ) such that
u ∈ TV , v ∈
/ TV
Add v to TV , f to TE
Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 3 / 10
Prim’s algorithm

G = (V , E ), W : E → R Example

Incrementally build an MCST 70


3 4
TV ⊆ V : tree vertices, already added to MCST 18 6 8
TE ⊆ E : tree edges, already added to MCST
10 20
0 1 2
Initially, TV = TE = ∅
Choose minimum weight edge e = (i, j) TV = {1, 3, 0, 2}
Set TV = {i, j}, TE = {e} MCST TE = {(1, 3), (1, 0),
Repeat n − 2 times (1, 2)}
Choose minimum weight edge f = (u, v ) such that
u ∈ TV , v ∈
/ TV
Add v to TV , f to TE
Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 3 / 10
Prim’s algorithm

G = (V , E ), W : E → R Example

Incrementally build an MCST 70


3 4
TV ⊆ V : tree vertices, already added to MCST 18 6 8
TE ⊆ E : tree edges, already added to MCST
10 20
0 1 2
Initially, TV = TE = ∅
Choose minimum weight edge e = (i, j) TV = {1, 3, 0, 2, 4}
Set TV = {i, j}, TE = {e} MCST TE = {(1, 3), (1, 0),
Repeat n − 2 times (1, 2), (2, 4)}
Choose minimum weight edge f = (u, v ) such that
u ∈ TV , v ∈
/ TV
Add v to TV , f to TE
Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 3 / 10
Improved implementation
def primlist2(WList):
For each v, keep track of its infinity = 1 + max([d for u in WList.keys()
nearest neighbour in the tree for (v,d) in WList[u]])
(visited,distance,nbr) = ({},{},{})
visited[v] – is v in the for v in WList.keys():
spanning tree? (visited[v],distance[v],nbr[v]) = (False,infinity,-1)
distance[v] – shortest visited[0] = True
for (v,d) in WList[0]:
distance from v to the tree (distance[v],nbr[v]) = (d,0)
nbr[v] – nearest neighbour of for i in range(1,len(WList.keys())):
v in tree nextd = min([distance[v] for v in WList.keys()
if not visited[v]])
Scan all non-tree vertices to find nextvlist = [v for v in WList.keys()
if (not visited[v]) and
nextv with minimum distance distance[v] == nextd]
if nextvlist == []:
Then (nbr[nextv],nextv) is break
the tree edge to add nextv = min(nextvlist)
visited[nextv] = True
Update distance[v] and for (v,d) in WList[nextv]:
nbr[v] for all neighbours of if not visited[v] and d < distance[v]:
(distance[v],nbr[v]) = (d,nextv)
nextv return(nbr)
Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 8 / 10
Improved implementation — complexity
def primlist2(WList):
Now the scan to find the next infinity = 1 + max([d for u in WList.keys()
vertex to add is O(n) for (v,d) in WList[u]])
(visited,distance,nbr) = ({},{},{})
Very similar to Dijkstra’s for v in WList.keys():
algorithm, except for the update (visited[v],distance[v],nbr[v]) = (False,infinity,-1)
visited[0] = True
rule for distance for (v,d) in WList[0]:
(distance[v],nbr[v]) = (d,0)
Like Dijkstra’s algorithm, this is for i in range(1,len(WList.keys())):
still O(n2 ) even for adjacency nextd = min([distance[v] for v in WList.keys()
if not visited[v]])
lists nextvlist = [v for v in WList.keys()
if (not visited[v]) and
With a more clever data distance[v] == nextd]
structure to extract the if nextvlist == []:
break
minimum, we can do better nextv = min(nextvlist)
visited[nextv] = True
for (v,d) in WList[nextv]:
if not visited[v] and d < distance[v]:
(distance[v],nbr[v]) = (d,nextv)
return(nbr)
Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 9 / 10
Summary

Prim’s algorithm grows an MCST starting with any vertex


At each step, connect one more vertex to the tree using minimum cost edge from
inside the tree to outside the tree
Correctness follows from Minimum Separator Lemma
Implementation similar to Dijkstra’s algorithms
Update rule for distance is different

Complexity is O(n2 )
Even with adjacency lists
Bottleneck is identifying unvisited vertex with minimum distance
Need a better data structure to identify and remove minimum (or maximum) from a
collection
Madhavan Mukund Minimum Cost Spanning Trees:Prim’s Algorithm PDSA using Python Week 5 10 / 10

You might also like