🚈 Prim

Minimum Spanning Tree Problem §

Find the spanning tree of weighted-graph (connects all vertices) that has minimum cumulative weight.

Theory §

The cut property states that for any cut of , the minimum edge crossing the cut must be in all minimum spanning trees. Prim uses this property to greedily add minimum-weight edges, building a connected component and applying the property to cut .

Implementation §

from heapq import heappush, heappop
 
def prim(adj):
	ret = 0
	dist = [float('inf') for _ in range(len(adj))]
	dist[0] = 0
	vis = set()
	pq = [(0, 0)]
	while len(pq) > 0:
		d, c = heappop(pq)
		if c in vis:
			continue
		ret += d
		vis.add(c)
		for n, w in adj[c]:
			if w < dist[n]:
				dist[n] = w
				heappush(pq, (dist[n], n))
	return ret

Runtime §

Assuming our input is valid (that does have a MST), since it must be connected. Each priority queue pop and push takes , and we perform these operations once for each vertex and edge.

Therefore, our runtime is .