prim's algorithm

Work in Progress

Summary

Prim’s algorithm

greedy
constructive, add to the main tree

Time complexity

add outgoing from source to PQ:
next best edge:
average case:

Invariant

at the kth iteration, we have a minimum tree spanning k nodes

Concept

Algorithm

from a source node, enqueue all outgoing edges into a priority queue
dequeue edge with lowest weight
check against a “taken” array to avoid a cycle

java

List<Boolean> taken = new ArrayList<>(Collections.nCopies(V, false)); // similar to visited array

int prim(int s) {
	int mst_cost = 0, num_taken = 0;
	
	PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1])); // e = [ v, w ]
	
	// take the source node and enqueue outgoing edges
	taken.set(s, true);
	for (int[] v_w : AL.get(s))
		if (!taken.get(v_w[0]))
			pq.offer(v_w);
	
	while (!pq.isEmpty()) { // every vertex, k neighbours are relaxed -> O(E log V)
		int[] min = pq.poll();
		int u = min[0];
		
		if (taken.get(u)) continue; // already taken, skip to avoid cycle
		
		mst_cost += min[1]; // add w of this edge
		++num_taken;
		
		// take the current node and enqueue outgoing edges
		taken.set(u, true);
		for (int[] v_w : AL.get(u))
			if (!taken.get(v_w[0]))
				pq.offer(v_w);
		
		if (num_taken == V-1) break; // early termination, once we have a spanning tree, break
	}
    
  return mst_cost;
}

in Prim’s algorithm the PQ stores [v, w] whereas in Dijkstra’s the PQ stores [v, d]

6 vertex graph: prim(0)

curr | pq
0    | [1, 2], [2, 4]
1    | [0, 2], [2, 3], [3, 3], [2, 4], [4, 4]
0    | [2, 3], [3, 3], [2, 4], [4, 4]                                                    <- already taken
2    | [1, 3], [3, 3], [4, 3], [0, 4], [2, 4], [4, 4]
1    | [3, 3], [4, 3], [0, 4], [2, 4], [4, 4]                                            <- already taken
3    | [4, 2], [1, 3], [4, 3], [5, 3], [0, 4], [2, 4], [4, 4]
4    | [3, 2], [5, 2], [1, 3], [2, 3], [4, 3], [5, 3], [0, 4], [1, 4], [2, 4], [4, 4]
3    | [5, 2], [1, 3], [2, 3], [4, 3], [5, 3], [0, 4], [1, 4], [2, 4], [4, 4]            <- already taken
5    | [1, 3], [2, 3], [4, 3], [5, 3], [0, 4], [1, 4], [2, 4], [4, 4]                    <- V-1 taken, break

Application

Leetcode: Min Cost to Connect All Points

prim’s method

java

int V = points.length;
List<List<int[]>> AL = new ArrayList<>();
for (int i = 0; i < V; i++)
	AL.add(new ArrayList<>());

for (int i = 0; i < V - 1; i++)
	for (int j = i + 1; j < V; j++) {
		int w = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
		AL.get(i).add(new int[] { j, w });
		AL.get(j).add(new int[] { i, w });
	}

List<Boolean> taken = new ArrayList<>(Collections.nCopies(V, false));

int mst_cost = 0, num_taken = 0;

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.<int[]>comparingInt(x -> x[1]).thenComparingInt(x -> x[0]));// e = [ v, w ]

// s = 0
taken.set(0, true);
for (int[] v_w : AL.get(0))
	if (!taken.get(v_w[0]))
		pq.offer(v_w);

while (!pq.isEmpty()) {
	int[] min = pq.poll();
	int u = min[0];

	if (taken.get(u))
		continue;

	mst_cost += min[1];

	taken.set(u, true);
	for (int[] v_w : AL.get(u))
		if (!taken.get(v_w[0]))
			pq.offer(v_w);

	if (num_taken == V - 1)
		break;
}

return mst_cost;