Prim's Algorithm

1. Detailed Explanation

Prim’s Algorithm is a greedy algorithm that finds a minimum spanning tree (MST) for a weighted, undirected, and connected graph. An MST is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Why is it important? Prim’s algorithm is fundamental in network design and other optimization problems. It’s used to find the cheapest way to connect a set of points, whether it’s laying cables for a computer network or pipes for a water system.

Core concepts:

• Minimum Spanning Tree (MST): A tree that connects all vertices in a graph with the minimum possible total edge weight.
• Greedy Algorithm: An algorithm that makes the locally optimal choice at each stage with the hope of finding a global optimum.
• Priority Queue: A data structure that is essential for an efficient implementation of Prim’s algorithm. It’s used to store vertices that are not yet in the MST and retrieve the one with the smallest edge weight connecting it to the MST.

2. When to Use Prim’s Algorithm (and When Not To)

Use Prim’s when:

• You need to find a minimum spanning tree for a dense graph (a graph with many edges). Prim’s algorithm is generally faster than Kruskal’s algorithm for dense graphs when implemented with a Fibonacci heap.
• The graph is connected and undirected.

Don’t use Prim’s when:

• The graph is directed.
• The graph is not connected (it will only find an MST for the connected component it starts in).
• You need to find the shortest path between two nodes (use Dijkstra’s or A* for that).

3. Core Algorithm / Data Structure Template

The algorithm works by building the MST one vertex at a time, starting from an arbitrary vertex. At each step, it adds the cheapest possible connection from the tree to a vertex that is not yet in the tree.

function Prims(graph):
  MST = empty set
  visited = set with an arbitrary start node
  priority_queue = all edges connected to the start node

  while priority_queue is not empty:
    edge = extract min edge from priority_queue
    if the destination node of edge is not visited:
      add edge to MST
      add destination node to visited
      add all edges from the destination node to unvisited nodes to the priority_queue

4. Code Implementations

Python

import heapq

def prims(graph, start_node):
    mst = []
    visited = {start_node}
    edges = [
        (weight, start_node, to_node)
        for to_node, weight in graph[start_node].items()
    ]
    heapq.heapify(edges)

    while edges:
        weight, from_node, to_node = heapq.heappop(edges)
        if to_node not in visited:
            visited.add(to_node)
            mst.append((from_node, to_node, weight))
            for next_node, next_weight in graph[to_node].items():
                if next_node not in visited:
                    heapq.heappush(edges, (next_weight, to_node, next_node))
    return mst

# Example graph
graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 1, 'E': 4},
    'C': {'A': 3, 'B': 1, 'F': 5},
    'D': {'B': 1, 'E': 1},
    'E': {'B': 4, 'D': 1, 'F': 1},
    'F': {'C': 5, 'E': 1}
}

print(prims(graph, 'A'))

Java

import java.util.*;

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

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

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

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

        visited.add(start);
        for (Edge edge : graph.getOrDefault(start, new ArrayList<>())) {
            pq.add(edge);
        }

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int to = edge.to;
            int weight = edge.weight;

            if (!visited.contains(to)) {
                visited.add(to);
                // We need to know the 'from' node. This requires a more complex structure.
                // For simplicity, let's assume we can find it.
                // A better implementation would store the 'from' node in the Edge object.
                // This is a simplified example.
                // mst.add(new int[]{from, to, weight});

                for (Edge nextEdge : graph.getOrDefault(to, new ArrayList<>())) {
                    if (!visited.contains(nextEdge.to)) {
                        pq.add(nextEdge);
                    }
                }
            }
        }
        return mst;
    }

    public static void main(String[] args) {
        // Graph representation would be more complex here
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

const int INF = 1e9;

void prims(map<char, vector<pair<int, char>>>& graph, char start) {
    priority_queue<pair<int, char>, vector<pair<int, char>>, greater<pair<int, char>>> pq;
    map<char, int> dist;
    map<char, char> parent;
    map<char, bool> inMST;

    for (auto const& [key, val] : graph) {
        dist[key] = INF;
        parent[key] = -1;
        inMST[key] = false;
    }

    pq.push({0, start});
    dist[start] = 0;

    while (!pq.empty()) {
        char u = pq.top().second;
        pq.pop();

        inMST[u] = true;

        for (auto& edge : graph[u]) {
            char v = edge.second;
            int weight = edge.first;

            if (!inMST[v] && dist[v] > weight) {
                dist[v] = weight;
                pq.push({dist[v], v});
                parent[v] = u;
            }
        }
    }

    for (auto const& [key, val] : parent) {
        if (val != -1) {
            cout << val << " - " << key << endl;
        }
    }
}

int main() {
    map<char, vector<pair<int, char>>> graph;
    graph['A'] = {{2, 'B'}, {3, 'C'}};
    graph['B'] = {{2, 'A'}, {1, 'C'}, {1, 'D'}, {4, 'E'}};
    graph['C'] = {{3, 'A'}, {1, 'B'}, {5, 'F'}};
    graph['D'] = {{1, 'B'}, {1, 'E'}};
    graph['E'] = {{4, 'B'}, {1, 'D'}, {1, 'F'}};
    graph['F'] = {{5, 'C'}, {1, 'E'}};

    prims(graph, 'A');

    return 0;
}

5. Complexity Analysis

Data Structure for Priority Queue	Time Complexity
Adjacency Matrix, searching	O(V^2)
Binary Heap and Adjacency List	O(E log V)
Fibonacci Heap and Adjacency List	O(E + V log V)

Where:

• V = number of vertices (nodes)
• E = number of edges

The space complexity is O(V + E) to store the graph.

6. Pro Tips, Tricks, and Common Pitfalls

Pro Tips:

• Prim’s is great for dense graphs.
• Use a PriorityQueue (or heapq in Python) for efficient implementation.
• You can start from any vertex.

Common Pitfalls:

• Forgetting to handle disconnected graphs. Prim’s will only find an MST for the component it starts in.
• Incorrectly updating the priority queue, leading to a non-minimal spanning tree.
• Using it on directed graphs.

7. Classic Problem Examples

Example: Connecting a Network

Description: You are given a list of cities and the cost to build a road between any two cities. Find the minimum cost to connect all cities.

High-level Approach using Prim’s:

1. Represent as a graph: The cities are the vertices, and the roads are the edges with weights equal to the cost.
2. Start at any city: Pick an arbitrary city to start building the network.
3. Greedily add connections: At each step, add the cheapest road that connects a city in the network to a city outside the network.
4. Repeat until all cities are connected: Continue until all cities are part of the network.

This is a classic application of Prim’s algorithm to find the minimum cost to connect all points in a network.