# Minimum Spanning Tree – Prim

minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Source: https://en.wikipedia.org/wiki/Minimum_spanning_tree

This post will introduce one of the algorithms to find an MST: Prim. Logics, time/space complexities, and implementations will be provided. Feat. Leetcode challenge 1584. Min Cost to Connect All Points.

## Logic

Prim’s logic is quite similar to Dijkstra’s algorithm, which also finds the lightest edge greedily. It starts with an arbitrary vertex v and ends up with a set of edges A spanning all the vertices. At each step, it would look for the edge that connects A to an isolated vertex in the graph. The pseudo-code is shown below.

MST-PRIM(G,w,r)
'''
G: the connected graph
w: weights
r: the root vertex
Q: a min-priority queue based on a key field
key: for each vertex v, key[v] is the minimum weight \
of any edge connecting to a vertex in the MST
π: for each vertex v, π[v] names the parent of v in the MST
'''
for each u in V[G]
key[u] = inf
π[u] = NIL

key[r] = 0
Q = V[G]

while Q:
u = EXTRACT_MIN(Q)
if v in Q and w(u,v)<key[v]
π[v] = u
key[v] = w(u,v)



Here’s an illustration for Prim:

## Complexities

There are two ways of implementations for line 17.

• using adjacency matrix, so that EXTRACT_MIN takes O(V);
• using binary heap, so that EXTRACT_MIN takes O(logV).

• Initialisation takes O(V)(Line 11 – 15).
• Line 16 would be executed for O(V) time, so EXTRACT_MIN takes O(V*V) in total.
• As the while-loop in line 16 will be executed for each vertex and the for-loop in line 18 will be executed for each edge of the vertex, therefore the for-loop in line 18 will be executed for O(E) times.

Therefore, the total time complexity would be O(V+V^2+E)=O(V^2). The space complexity would be O(V+E).

#### Binary heap

• Initialisation takes O(V)(Line 11 – 15).
• Line 16 would be executed for O(V) time, so EXTRACT_MIN takes O(V*logV) in total.
• As the while-loop in line 16 will be executed for each vertex and the for-loop in line 18 will be executed for each edge of the vertex, therefore the for-loop in line 18 will be executed for O(E) times.
• Line 21 indicates an update operation on the heap, thus taking logV.

Therefore, the total time complexity would be O(V+V^logV+ElogV)=O(ElogV). The space complexity would be O(V+E).

## Implementations – 1584. Min Cost to Connect All Points

Two implementations using the binary heap and the adjacency matrix will be both provided. Noticing that this graph is a dense one, hence using the binary heap brings O(ElogV)=O(V^2logV) and using the adjacency matrix brings O(V^2). Therefore the latter one would provide a more efficient solution.

#### Binary heap

class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
dist = collections.defaultdict(list)
n = len(points)
for i in range(n):
for j in range(i+1,n):
d = abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1])
dist[i].append((j,d))
dist[j].append((i,d))
ret = 0
visited = set([])
pq = [(0,0)]
while pq:
w,u = heapq.heappop(pq)
if u not in visited:
ret += w
for v,d in dist[u]:
if v not in visited: heapq.heappush(pq,(d,v))
return ret


class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
def dist(u,v):
return abs(points[u][0]-points[v][0])+abs(points[u][1]-points[v][1])
n = len(points)
ret = 0
visited = [False]*n
visited[0] = True
closest = [0]*n
for i in range(1,n): closest[i] = dist(0,i)
for _ in range(n-1):
mini = float('inf')
node = -1
for i in range(n):
if not visited[i] and closest[i] < mini:
mini = closest[i]
node = i
ret += mini
visited[node] = True
for i in range(n):
if not visited[i]: closest[i] = min(closest[i],dist(i,node))
return ret


## Reference

• https://shawnlyu.com/algorithms/shortest-path-algorithms-i-dijkstra/
• https://leetcode.com/problems/min-cost-to-connect-all-points/
• https://iq.opengenus.org/prim-minimum-spanning-tree-algorithm/
• https://en.wikipedia.org/wiki/Prim%27s_algorithm

Subscribe
Notify of