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)
	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:

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).

Adjacency matrix

  • 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
                visited.add(u)
                for v,d in dist[u]:
                    if v not in visited: heapq.heappush(pq,(d,v))
        return ret

Adjacency 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

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
guest
0 Comments
Inline Feedbacks
View all comments