Prim's Algorithm (Minimum Spanning Tree) Code Implementations
Complete Prim's Algorithm (Minimum Spanning Tree) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Prim's Algorithm (Minimum Spanning Tree) Guide ยท Launch Interactive Visualizer
C++ Implementation
// Prim's Algorithm Implementation in C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <limits>
class PrimAlgorithm {
public:
static std::vector<std::pair<int, std::pair<int, int>>> primAlgorithm(const std::unordered_map<int, std::unordered_map<int, int>>& graph, int start) {
std::unordered_set<int> visited;
std::vector<std::pair<int, std::pair<int, int>>> mst;
std::priority_queue<std::pair<int, std::pair<int, int>>,
std::vector<std::pair<int, std::pair<int, int>>>,
std::greater<std::pair<int, std::pair<int, int>>>> pq;
std::unordered_map<int, int> parent;
std::unordered_map<int, int> key;
// Initialize keys
for (const auto& [vertex, neighbors] : graph) {
key[vertex] = std::numeric_limits<int>::max();
}
key[start] = 0;
pq.push({0, {start, -1}}); // {weight, {vertex, parent}}
while (!pq.empty() && visited.size() < graph.size()) {
auto [weight, vertexPair] = pq.top();
int current = vertexPair.first;
int parentVertex = vertexPair.second;
pq.pop();
if (visited.find(current) != visited.end()) continue;
visited.insert(current);
if (parentVertex != -1) {
mst.push_back({weight, {parentVertex, current}});
}
auto it = graph.find(current);
if (it != graph.end()) {
for (const auto& [neighbor, edgeWeight] : it->second) {
if (visited.find(neighbor) == visited.end() && edgeWeight < key[neighbor]) {
key[neighbor] = edgeWeight;
parent[neighbor] = current;
pq.push({edgeWeight, {neighbor, current}});
}
}
}
}
return mst;
}
// Prim's with adjacency matrix
static std::vector<std::pair<int, std::pair<int, int>>> primWithMatrix(const std::vector<std::vector<int>>& adjacencyMatrix, int start) {
int n = adjacencyMatrix.size();
std::vector<bool> visited(n, false);
std::vector<std::pair<int, std::pair<int, int>>> mst;
std::vector<int> key(n, std::numeric_limits<int>::max());
std::vector<int> parent(n, -1);
key[start] = 0;
for (int count = 0; count < n - 1; count++) {
// Find vertex with minimum key value
int minKey = std::numeric_limits<int>::max();
int minIndex = -1;
for (int v = 0; v < n; v++) {
if (!visited[v] && key[v] < minKey) {
minKey = key[v];
minIndex = v;
}
}
if (minIndex == -1) break;
visited[minIndex] = true;
if (parent[minIndex] != -1) {
mst.push_back({key[minIndex], {parent[minIndex], minIndex}});
}
// Update key values of adjacent vertices
for (int v = 0; v < n; v++) {
if (!visited[v] && adjacencyMatrix[minIndex][v] != 0 &&
adjacencyMatrix[minIndex][v] < key[v]) {
key[v] = adjacencyMatrix[minIndex][v];
parent[v] = minIndex;
}
}
}
return mst;
}
// Calculate total weight of MST
static int calculateTotalWeight(const std::vector<std::pair<int, std::pair<int, int>>>& mst) {
int totalWeight = 0;
for (const auto& [weight, edge] : mst) {
totalWeight += weight;
}
return totalWeight;
}
// Prim's for forest (multiple components)
static std::vector<std::vector<std::pair<int, std::pair<int, int>>>> primForest(const std::unordered_map<int, std::unordered_map<int, int>>& graph) {
std::unordered_set<int> visited;
std::vector<std::vector<std::pair<int, std::pair<int, int>>>> components;
for (const auto& [vertex, neighbors] : graph) {
if (visited.find(vertex) == visited.end()) {
auto componentMST = primAlgorithm(graph, vertex);
// Add all vertices in this component to visited
for (const auto& [weight, edge] : componentMST) {
visited.insert(edge.first);
visited.insert(edge.second);
}
components.push_back(componentMST);
}
}
return components;
}
};JAVA Implementation
// Prim's Algorithm Implementation in Java
import java.util.*;
public class PrimAlgorithm {
public static Map<String, Object> primAlgorithm(Map<Integer, Map<Integer, Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
List<Map<String, Object>> mst = new ArrayList<>();
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
Map<Integer, Integer> parent = new HashMap<>();
Map<Integer, Integer> key = new HashMap<>();
// Initialize keys
for (int vertex : graph.keySet()) {
key.put(vertex, Integer.MAX_VALUE);
}
key.put(start, 0);
pq.offer(new int[]{0, start, -1}); // {weight, vertex, parent}
while (!pq.isEmpty() && visited.size() < graph.size()) {
int[] current = pq.poll();
int weight = current[0];
int vertex = current[1];
int parentVertex = current[2];
if (visited.contains(vertex)) continue;
visited.add(vertex);
if (parentVertex != -1) {
Map<String, Object> edge = new HashMap<>();
edge.put("from", parentVertex);
edge.put("to", vertex);
edge.put("weight", weight);
mst.add(edge);
}
Map<Integer, Integer> neighbors = graph.getOrDefault(vertex, new HashMap<>());
for (Map.Entry<Integer, Integer> entry : neighbors.entrySet()) {
int neighbor = entry.getKey();
int edgeWeight = entry.getValue();
if (!visited.contains(neighbor) && edgeWeight < key.get(neighbor)) {
key.put(neighbor, edgeWeight);
parent.put(neighbor, vertex);
pq.offer(new int[]{edgeWeight, neighbor, vertex});
}
}
}
Map<String, Object> result = new HashMap<>();
result.put("mst", mst);
result.put("totalWeight", mst.stream().mapToInt(edge -> (Integer) edge.get("weight")).sum());
return result;
}
// Prim's with adjacency matrix
public static Map<String, Object> primWithMatrix(int[][] adjacencyMatrix, int start) {
int n = adjacencyMatrix.length;
boolean[] visited = new boolean[n];
List<Map<String, Object>> mst = new ArrayList<>();
int[] key = new int[n];
int[] parent = new int[n];
Arrays.fill(key, Integer.MAX_VALUE);
key[start] = 0;
Arrays.fill(parent, -1);
for (int count = 0; count < n - 1; count++) {
// Find vertex with minimum key value
int minKey = Integer.MAX_VALUE;
int minIndex = -1;
for (int v = 0; v < n; v++) {
if (!visited[v] && key[v] < minKey) {
minKey = key[v];
minIndex = v;
}
}
if (minIndex == -1) break;
visited[minIndex] = true;
if (parent[minIndex] != -1) {
Map<String, Object> edge = new HashMap<>();
edge.put("from", parent[minIndex]);
edge.put("to", minIndex);
edge.put("weight", key[minIndex]);
mst.add(edge);
}
// Update key values of adjacent vertices
for (int v = 0; v < n; v++) {
if (!visited[v] && adjacencyMatrix[minIndex][v] != 0 &&
adjacencyMatrix[minIndex][v] < key[v]) {
key[v] = adjacencyMatrix[minIndex][v];
parent[v] = minIndex;
}
}
}
Map<String, Object> result = new HashMap<>();
result.put("mst", mst);
result.put("totalWeight", mst.stream().mapToInt(edge -> (Integer) edge.get("weight")).sum());
return result;
}
// Prim's for forest (multiple components)
public static Map<String, Object> primForest(Map<Integer, Map<Integer, Integer>> graph) {
Set<Integer> visited = new HashSet<>();
List<Map<String, Object>> mst = new ArrayList<>();
List<List<Map<String, Object>>> components = new ArrayList<>();
for (int vertex : graph.keySet()) {
if (!visited.contains(vertex)) {
List<Map<String, Object>> component = new ArrayList<>();
Map<String, Object> componentMST = primAlgorithm(graph, vertex);
@SuppressWarnings("unchecked")
List<Map<String, Object>> componentEdges = (List<Map<String, Object>>) componentMST.get("mst");
// Add all vertices in this component to visited
for (Map<String, Object> edge : componentEdges) {
visited.add((Integer) edge.get("from"));
visited.add((Integer) edge.get("to"));
component.add(edge);
}
components.add(component);
mst.addAll(componentEdges);
}
}
Map<String, Object> result = new HashMap<>();
result.put("mst", mst);
result.put("components", components);
result.put("totalWeight", mst.stream().mapToInt(edge -> (Integer) edge.get("weight")).sum());
return result;
}
}JAVASCRIPT Implementation
// Prim's Algorithm Implementation in JavaScript
class PriorityQueue {
constructor() {
this.values = [];
}
enqueue(element, priority) {
this.values.push({ element, priority });
this.sort();
}
dequeue() {
return this.values.shift();
}
isEmpty() {
return this.values.length === 0;
}
sort() {
this.values.sort((a, b) => a.priority - b.priority);
}
}
function primAlgorithm(graph, start) {
const visited = new Set();
const mst = [];
const pq = new PriorityQueue();
const parent = {};
const key = {};
// Initialize keys
for (const vertex in graph) {
key[vertex] = Infinity;
}
key[start] = 0;
pq.enqueue(start, 0);
while (!pq.isEmpty()) {
const { element: current } = pq.dequeue();
if (visited.has(current)) continue;
visited.add(current);
if (parent[current] !== undefined) {
mst.push({
from: parent[current],
to: current,
weight: key[current]
});
}
const neighbors = graph[current] || {};
for (const neighbor in neighbors) {
const weight = neighbors[neighbor];
if (!visited.has(neighbor) && weight < key[neighbor]) {
key[neighbor] = weight;
parent[neighbor] = current;
pq.enqueue(neighbor, weight);
}
}
}
return {
mst,
totalWeight: mst.reduce((sum, edge) => sum + edge.weight, 0)
};
}
// Prim's with adjacency matrix
function primWithMatrix(adjacencyMatrix, start) {
const n = adjacencyMatrix.length;
const visited = new Array(n).fill(false);
const mst = [];
const key = new Array(n).fill(Infinity);
const parent = new Array(n).fill(-1);
key[start] = 0;
for (let count = 0; count < n - 1; count++) {
// Find vertex with minimum key value
let minKey = Infinity;
let minIndex = -1;
for (let v = 0; v < n; v++) {
if (!visited[v] && key[v] < minKey) {
minKey = key[v];
minIndex = v;
}
}
if (minIndex === -1) break;
visited[minIndex] = true;
if (parent[minIndex] !== -1) {
mst.push({
from: parent[minIndex],
to: minIndex,
weight: key[minIndex]
});
}
// Update key values of adjacent vertices
for (let v = 0; v < n; v++) {
if (!visited[v] && adjacencyMatrix[minIndex][v] !== 0 &&
adjacencyMatrix[minIndex][v] < key[v]) {
key[v] = adjacencyMatrix[minIndex][v];
parent[v] = minIndex;
}
}
}
return {
mst,
totalWeight: mst.reduce((sum, edge) => sum + edge.weight, 0)
};
}
// Prim's with priority queue optimization
function primWithPriorityQueue(graph, start) {
const visited = new Set();
const mst = [];
const pq = new PriorityQueue();
const parent = {};
const key = {};
// Initialize
for (const vertex in graph) {
key[vertex] = Infinity;
}
key[start] = 0;
pq.enqueue(start, 0);
while (!pq.isEmpty() && visited.size < Object.keys(graph).length) {
const { element: current } = pq.dequeue();
if (visited.has(current)) continue;
visited.add(current);
if (parent[current] !== undefined) {
mst.push({
from: parent[current],
to: current,
weight: key[current]
});
}
const neighbors = graph[current] || {};
for (const neighbor in neighbors) {
const weight = neighbors[neighbor];
if (!visited.has(neighbor) && weight < key[neighbor]) {
key[neighbor] = weight;
parent[neighbor] = current;
pq.enqueue(neighbor, weight);
}
}
}
return {
mst,
totalWeight: mst.reduce((sum, edge) => sum + edge.weight, 0),
isComplete: visited.size === Object.keys(graph).length
};
}
// Prim's for forest (multiple components)
function primForest(graph) {
const visited = new Set();
const mst = [];
const components = [];
for (const vertex in graph) {
if (!visited.has(vertex)) {
const component = [];
const componentMST = primAlgorithm(graph, vertex);
// Add all vertices in this component to visited
for (const edge of componentMST.mst) {
visited.add(edge.from);
visited.add(edge.to);
component.push(edge);
}
components.push(component);
mst.push(...componentMST.mst);
}
}
return {
mst,
components,
totalWeight: mst.reduce((sum, edge) => sum + edge.weight, 0)
};
}PYTHON Implementation
# Prim's Algorithm Implementation in Python
import heapq
from collections import defaultdict
def prim_algorithm(graph, start):
visited = set()
mst = []
pq = [(0, start, None)] # (weight, vertex, parent)
parent = {}
key = defaultdict(lambda: float('inf'))
key[start] = 0
while pq and len(visited) < len(graph):
weight, current, parent_vertex = heapq.heappop(pq)
if current in visited:
continue
visited.add(current)
if parent_vertex is not None:
mst.append({
'from': parent_vertex,
'to': current,
'weight': weight
})
neighbors = graph.get(current, {})
for neighbor, edge_weight in neighbors.items():
if neighbor not in visited and edge_weight < key[neighbor]:
key[neighbor] = edge_weight
parent[neighbor] = current
heapq.heappush(pq, (edge_weight, neighbor, current))
return {
'mst': mst,
'total_weight': sum(edge['weight'] for edge in mst)
}
# Prim's with adjacency matrix
def prim_with_matrix(adjacency_matrix, start):
n = len(adjacency_matrix)
visited = [False] * n
mst = []
key = [float('inf')] * n
parent = [-1] * n
key[start] = 0
for count in range(n - 1):
# Find vertex with minimum key value
min_key = float('inf')
min_index = -1
for v in range(n):
if not visited[v] and key[v] < min_key:
min_key = key[v]
min_index = v
if min_index == -1:
break
visited[min_index] = True
if parent[min_index] != -1:
mst.append({
'from': parent[min_index],
'to': min_index,
'weight': key[min_index]
})
# Update key values of adjacent vertices
for v in range(n):
if (not visited[v] and adjacency_matrix[min_index][v] != 0 and
adjacency_matrix[min_index][v] < key[v]):
key[v] = adjacency_matrix[min_index][v]
parent[v] = min_index
return {
'mst': mst,
'total_weight': sum(edge['weight'] for edge in mst)
}
# Prim's with priority queue optimization
def prim_with_priority_queue(graph, start):
visited = set()
mst = []
pq = [(0, start, None)]
parent = {}
key = defaultdict(lambda: float('inf'))
key[start] = 0
while pq and len(visited) < len(graph):
weight, current, parent_vertex = heapq.heappop(pq)
if current in visited:
continue
visited.add(current)
if parent_vertex is not None:
mst.append({
'from': parent_vertex,
'to': current,
'weight': weight
})
neighbors = graph.get(current, {})
for neighbor, edge_weight in neighbors.items():
if neighbor not in visited and edge_weight < key[neighbor]:
key[neighbor] = edge_weight
parent[neighbor] = current
heapq.heappush(pq, (edge_weight, neighbor, current))
return {
'mst': mst,
'total_weight': sum(edge['weight'] for edge in mst),
'is_complete': len(visited) == len(graph)
}
# Prim's for forest (multiple components)
def prim_forest(graph):
visited = set()
mst = []
components = []
for vertex in graph:
if vertex not in visited:
component = []
component_mst = prim_algorithm(graph, vertex)
# Add all vertices in this component to visited
for edge in component_mst['mst']:
visited.add(edge['from'])
visited.add(edge['to'])
component.append(edge)
components.append(component)
mst.extend(component_mst['mst'])
return {
'mst': mst,
'components': components,
'total_weight': sum(edge['weight'] for edge in mst)
}
# Prim's with custom weight function
def prim_with_weight_function(graph, start, weight_func):
visited = set()
mst = []
pq = [(0, start, None)]
parent = {}
key = defaultdict(lambda: float('inf'))
key[start] = 0
while pq and len(visited) < len(graph):
weight, current, parent_vertex = heapq.heappop(pq)
if current in visited:
continue
visited.add(current)
if parent_vertex is not None:
mst.append({
'from': parent_vertex,
'to': current,
'weight': weight
})
neighbors = graph.get(current, {})
for neighbor in neighbors:
if neighbor not in visited:
edge_weight = weight_func(current, neighbor)
if edge_weight < key[neighbor]:
key[neighbor] = edge_weight
parent[neighbor] = current
heapq.heappush(pq, (edge_weight, neighbor, current))
return {
'mst': mst,
'total_weight': sum(edge['weight'] for edge in mst)
}