Prim's Algorithm

import heapq

def prims_mst(graph, start=0):
    """
    Find Minimum Spanning Tree using Prim's Algorithm
    
    Args:
        graph: Adjacency list { node: [(neighbor, weight), ...] }
        start: Starting vertex (default 0)
    
    Returns:
        List of edges in MST: [(from, to, weight), ...]
    """
    mst = []  # Store MST edges
    visited = set([start])  # Track visited vertices
    
    # Priority queue: (weight, from_vertex, to_vertex)
    edges = [
        (weight, start, neighbor)
        for neighbor, weight in graph[start]
    ]
    heapq.heapify(edges)  # Convert to min-heap
    
    while edges and len(visited) < len(graph):
        weight, frm, to = heapq.heappop(edges)
        
        # Skip if vertex already visited (would create cycle)
        if to in visited:
            continue
        
        # Add edge to MST
        visited.add(to)
        mst.append((frm, to, weight))
        
        # Add all edges from new vertex to unvisited vertices
        for neighbor, edge_weight in graph[to]:
            if neighbor not in visited:
                heapq.heappush(edges, (edge_weight, to, neighbor))
    
    return mst

# Example Usage
graph = {
    0: [(1, 4), (2, 2)],
    1: [(0, 4), (2, 1), (3, 5)],
    2: [(0, 2), (1, 1), (3, 8), (4, 10)],
    3: [(1, 5), (2, 8), (4, 2)],
    4: [(2, 10), (3, 2)]
}

mst = prims_mst(graph, start=0)
print("MST Edges:", mst)
# Output: [(0, 2, 2), (2, 1, 1), (1, 3, 5), (3, 4, 2)]

total_weight = sum(weight for _, _, weight in mst)
print(f"Total MST Weight: {total_weight}")
# Output: Total MST Weight: 10

import java.util.*;

class Edge implements Comparable<Edge> {
    int weight;
    int from;
    int to;

    public Edge(int weight, int from, int to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

public class Prims {
    public static void primsMST(Map<Integer, List<int[]>> graph, int start) {
        List<String> mst = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        PriorityQueue<Edge> pq = new PriorityQueue<>();

        // Initialize with start node
        visited.add(start);
        if (graph.containsKey(start)) {
            for (int[] neighbor : graph.get(start)) {
                pq.offer(new Edge(neighbor[1], start, neighbor[0]));
            }
        }

        int totalWeight = 0;

        while (!pq.isEmpty() && visited.size() < graph.size()) {
            Edge edge = pq.poll();
            
            if (visited.contains(edge.to)) {
                continue;
            }

            visited.add(edge.to);
            mst.add("(" + edge.from + ", " + edge.to + ", " + edge.weight + ")");
            totalWeight += edge.weight;

            if (graph.containsKey(edge.to)) {
                for (int[] neighbor : graph.get(edge.to)) {
                    if (!visited.contains(neighbor[0])) {
                        pq.offer(new Edge(neighbor[1], edge.to, neighbor[0]));
                    }
                }
            }
        }

        System.out.println("MST Edges: " + mst);
        System.out.println("Total MST Weight: " + totalWeight);
        if (visited.size() != graph.size()) {
            System.out.println("No MST: output covers only the start component");
        }
    }

    public static void main(String[] args) {
        // Graph representation: Map<Node, List<[Neighbor, Weight]>>
        Map<Integer, List<int[]>> graph = new HashMap<>();
        
        // Helper to add edges easily
        graph.put(0, Arrays.asList(new int[]{1, 4}, new int[]{2, 2}));
        graph.put(1, Arrays.asList(new int[]{0, 4}, new int[]{2, 1}, new int[]{3, 5}));
        graph.put(2, Arrays.asList(new int[]{0, 2}, new int[]{1, 1}, new int[]{3, 8}, new int[]{4, 10}));
        graph.put(3, Arrays.asList(new int[]{1, 5}, new int[]{2, 8}, new int[]{4, 2}));
        graph.put(4, Arrays.asList(new int[]{2, 10}, new int[]{3, 2}));

        primsMST(graph, 0);
        // Output:
        // MST Edges: [(0, 2, 2), (2, 1, 1), (1, 3, 5), (3, 4, 2)]
        // Total MST Weight: 10
    }
}