Learn Minimum Spanning Tree Prim — Free DSA Tutorial

What is Prim

Prim's algorithm also builds a minimum spanning tree, but instead of considering all edges globally like Kruskal, it grows one connected tree outward from a single starting vertex, always extending along the cheapest available edge.

Example: What is Prim

#include <iostream>
using namespace std;
int main() {
	cout << "Prim: grow one tree outward from a start vertex, always extending along the cheapest edge out";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Prim: grow one tree outward from a start vertex, always extending along the cheapest edge out");
	}
}

print("Prim: grow one tree outward from a start vertex, always extending along the cheapest edge out")

#include <stdio.h>
int main() {
	printf("Prim: grow one tree outward from a start vertex, always extending along the cheapest edge out");
	return 0;
}

Key Values

Every vertex outside the tree keeps a key value — the weight of the cheapest edge connecting it to the tree so far — which gets updated whenever a newly-added tree vertex offers it a cheaper connection.

Example: Key Values

#include <iostream>
using namespace std;
int main() {
	int key[4] = {0, 1000000, 1000000, 1000000};
	int newEdgeWeight = 6, v = 2;
	if (newEdgeWeight < key[v]) { key[v] = newEdgeWeight; cout << "key[" << v << "] updated to " << key[v]; }
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] key = {0, 1000000, 1000000, 1000000};
		int newEdgeWeight = 6, v = 2;
		if (newEdgeWeight < key[v]) { key[v] = newEdgeWeight; System.out.println("key[" + v + "] updated to " + key[v]); }
	}
}

key = [0, 1000000, 1000000, 1000000]
new_edge_weight, v = 6, 2
if new_edge_weight < key[v]:
    key[v] = new_edge_weight
    print(f"key[{v}] updated to {key[v]}")

#include <stdio.h>
int main() {
	int key[4] = {0, 1000000, 1000000, 1000000};
	int newEdgeWeight = 6, v = 2;
	if (newEdgeWeight < key[v]) { key[v] = newEdgeWeight; printf("key[%d] updated to %d", v, key[v]); }
	return 0;
}

Visited Set

A vertex moves into the visited set the moment it's added to the growing tree, and from then on only vertices outside that set are candidates for the next cheapest edge, keeping the tree cycle-free by construction.

Example: Visited Set

#include <iostream>
using namespace std;
int main() {
	bool inTree[4] = {true, false, false, false};
	inTree[1] = true;
	cout << "Vertex 1 moved into tree; only vertices outside {0,1} are now candidates";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		boolean[] inTree = {true, false, false, false};
		inTree[1] = true;
		System.out.println("Vertex 1 moved into tree; only vertices outside {0,1} are now candidates");
	}
}

in_tree = [True, False, False, False]
in_tree[1] = True
print("Vertex 1 moved into tree; only vertices outside {0,1} are now candidates")

#include <stdio.h>
int main() {
	int inTree[4] = {1, 0, 0, 0};
	inTree[1] = 1;
	printf("Vertex 1 moved into tree; only vertices outside {0,1} are now candidates");
	return 0;
}

Example

Picture the tree starting as a single city, then repeatedly annexing whichever neighboring city has the cheapest road to any city already in the tree, until every city has joined.

Example: Example

#include <iostream>
using namespace std;
int main() {
	cout << "Tree starts as one city, repeatedly annexes the cheapest-connected neighboring city";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Tree starts as one city, repeatedly annexes the cheapest-connected neighboring city");
	}
}

print("Tree starts as one city, repeatedly annexes the cheapest-connected neighboring city")

#include <stdio.h>
int main() {
	printf("Tree starts as one city, repeatedly annexes the cheapest-connected neighboring city");
	return 0;
}

Complexity

A straightforward implementation that scans all key values each round to find the minimum costs O(V²), well-suited to dense graphs; using a min-heap to track candidate edges instead brings sparse graphs down to O(E log V).

Example: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Prim: O(V^2) naive scan for dense graphs; O(E log V) with a min-heap for sparse graphs";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Prim: O(V^2) naive scan for dense graphs; O(E log V) with a min-heap for sparse graphs");
	}
}

print("Prim: O(V^2) naive scan for dense graphs; O(E log V) with a min-heap for sparse graphs")

#include <stdio.h>
int main() {
	printf("Prim: O(V^2) naive scan for dense graphs; O(E log V) with a min-heap for sparse graphs");
	return 0;
}

Minimum Spanning Tree Prim

What is Prim

Key Values

Visited Set

Example

Complexity

Chapter Quiz — Complete all 10 topics to unlock

Login to run this code