Prim's Algorithm: Find Minimum Spanning Tree

Description

Prim's Algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree including every vertex, where the total weight of all the edges in the tree is minimized.

Starts with a single vertex and grows the spanning tree
Always adds the smallest edge that connects a vertex in the tree to a vertex outside the tree
Uses a priority queue to efficiently select the next edge

History

Prim's Algorithm was developed by Czech mathematician Vojtěch Jarník in 1930 and later independently rediscovered and popularized by computer scientist Robert C. Prim in 1957. It is a fundamental algorithm in computer science, used for finding the minimum spanning tree of a graph, which is a crucial problem in network design, circuit design, and other fields. The algorithm is named after Prim, who was working at Bell Labs when he published his version of the algorithm. It is also sometimes referred to as the DJP algorithm, after its discoverers Dijkstra, Jarník, and Prim.

How It Works

Initialize a priority queue with all edges from an arbitrary starting vertex.
While the priority queue is not empty:
- Extract the edge with the smallest weight.
- If the edge connects a new vertex, add it to the MST and add all edges from this vertex to the queue.
Repeat until all vertices are included in the MST.

Visualization

Speed:

Click Start to begin Prim's algorithm

Implementation

import heapq

def prim(graph, start=0):
    mst = []
    visited = set()
    min_heap = [(0, start, None)]  # (weight, vertex, parent)
    
    while min_heap:
        weight, vertex, parent = heapq.heappop(min_heap)
        if vertex not in visited:
            visited.add(vertex)
            if parent is not None:
                mst.append((parent, vertex, weight))
            
            for neighbor, edge_weight in graph[vertex]:
                if neighbor not in visited:
                    heapq.heappush(min_heap, (edge_weight, neighbor, vertex))
    
    return mst

#include <vector>
#include <queue>
#include <utility>
#include <limits>

using namespace std;

typedef pair<int, int> Edge; // (weight, vertex)

vector<Edge> prim(const vector<vector<Edge>>& graph, int start = 0) {
    vector<Edge> mst;
    vector<bool> visited(graph.size(), false);
    priority_queue<Edge, vector<Edge>, greater<Edge>> min_heap;
    min_heap.push({0, start});
    
    while (!min_heap.empty()) {
        auto [weight, vertex] = min_heap.top();
        min_heap.pop();
        
        if (!visited[vertex]) {
            visited[vertex] = true;
            if (vertex != start) {
                mst.push_back({weight, vertex});
            }
            
            for (const auto& [edge_weight, neighbor] : graph[vertex]) {
                if (!visited[neighbor]) {
                    min_heap.push({edge_weight, neighbor});
                }
            }
        }
    }
    
    return mst;
}

using System;
using System.Collections.Generic;

public class PrimAlgorithm
{
    public static List<(int, int, int)> Prim(Dictionary<int, List<(int, int)>> graph, int start = 0)
    {
        var mst = new List<(int, int, int)>();
        var visited = new HashSet<int>();
        var minHeap = new SortedSet<(int, int, int)>();
        minHeap.Add((0, start, -1)); // (weight, vertex, parent)
        
        while (minHeap.Count > 0)
        {
            var (weight, vertex, parent) = minHeap.Min;
            minHeap.Remove(minHeap.Min);
            
            if (!visited.Contains(vertex))
            {
                visited.Add(vertex);
                if (parent != -1)
                {
                    mst.Add((parent, vertex, weight));
                }
                
                foreach (var (neighbor, edgeWeight) in graph[vertex])
                {
                    if (!visited.Contains(neighbor))
                    {
                        minHeap.Add((edgeWeight, neighbor, vertex));
                    }
                }
            }
        }
        
        return mst;
    }
}

Complexity Analysis

Operation	Time Complexity	Space Complexity
Worst Case	O(E log V)	O(V)
Average Case	O(E log V)	O(V)
Best Case	O(E log V)	O(V)

Where V is the number of vertices and E is the number of edges in the graph.

Advantages and Disadvantages

Advantages

Efficient for dense graphs
Simple to implement
Produces a minimum spanning tree
Can handle graphs with negative weights

Disadvantages

Not suitable for very large graphs
Requires a priority queue for efficiency
May not be as fast as Kruskal's for sparse graphs

Quick Info

Prim's Algorithm