AntInLoop

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