Minimum Spanning Tree — Prim
Source: https://shawnlyu.com/algorithms/minimum-spanning-tree-prim/
A 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.
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 as 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)
for each v in Adj[u]
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 the binary heap, so that EXTRACT_MIN takes O(logV).
Adjacency matrix
- Initialization 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
- Initialization 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+VlogV+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
visited.add(u)
for v,d in dist[u]:
if v not in visited: heapq.heappush(pq,(d,v))
return retAdjacency matrix
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
