Prim's Algorithm

---

Prim's Algorithm is a well-known algorithm in graph theory used to find the Minimum Spanning Tree (MST) of a connected, weighted graph. A Minimum Spanning Tree is a subset of the edges that connects all vertices together, without forming any cycles, and with the minimum possible total edge weight.

Unlike Kruskal’s Algorithm, which operates on edges, Prim’s Algorithm operates on vertices and incrementally grows the MST by adding the smallest edge that connects a vertex in the MST to a vertex outside it. It’s a greedy algorithm, meaning it makes the locally optimal choice at each step with the hope of finding the global optimum.

What is a Spanning Tree?

A spanning tree of a graph is a tree that includes all the vertices of the graph. Since a tree with $V$ vertices has exactly $V-1$ edges, the minimum spanning tree (MST) is the spanning tree that has the smallest total edge weight.

How Prim’s Algorithm Works

Prim’s Algorithm starts with an arbitrary vertex and grows the MST by continuously adding the minimum-weight edge that connects the tree to a vertex outside the tree. Here's how it works:

1. Initialize: Start with an arbitrary vertex and mark it as part of the MST. Set the key values (which represent the minimum edge weights) of all other vertices to infinity.

2. Iterate:

   • Choose the vertex with the smallest key value (i.e., the vertex that is closest to the MST).
   • Update the key values of all adjacent vertices.

3. Repeat the process until all vertices are included in the MST.

4. Result: Once all vertices are part of the MST, the algorithm terminates, and we have the Minimum Spanning Tree.

Steps of Prim’s Algorithm:

1. Initialization: Choose any vertex as the starting point and set its key value to 0. Set all other vertices’ key values to infinity.
2. Priority Queue: Use a priority queue (min-heap) to always choose the vertex with the smallest key value.
3. Update the Key Values: For the chosen vertex, update the key values of its adjacent vertices if the new edge offers a smaller weight than the current key value.
4. Mark the Vertex: Mark the chosen vertex as visited (included in the MST) and repeat the process.

Prim’s Algorithm Example

Consider the following graph with 5 nodes:

       2       3
A -------- B -------- C
|           |         |
| 6         | 5       | 7
|           |         |
D -------- E -------- F
        1

• Nodes: A, B, C, D, E, F
• Edges: (A, B, 2), (A, D, 6), (B, C, 3), (B, E, 5), (C, F, 7), (D, E, 1), (E, F, 4)

Prim’s Algorithm Implementation

Let's look at how to implement Prim’s Algorithm in both Python and C++.

1. Prim’s Algorithm in Python

import heapq

def prim(graph, start):
    # Initialize a priority queue and the visited set
    min_heap = [(0, start)]  # (weight, vertex)
    mst = []
    visited = set()
    total_weight = 0
    
    while min_heap:
        weight, u = heapq.heappop(min_heap)  # Get the vertex with the smallest edge
        
        if u not in visited:
            visited.add(u)
            mst.append((u, weight))
            total_weight += weight
            
            # Add the adjacent vertices to the priority queue
            for v, w in graph[u]:
                if v not in visited:
                    heapq.heappush(min_heap, (w, v))
    
    return mst, total_weight


# Sample graph (adjacency list representation)
graph = {
    'A': [('B', 2), ('D', 6)],
    'B': [('A', 2), ('C', 3), ('E', 5)],
    'C': [('B', 3), ('F', 7)],
    'D': [('A', 6), ('E', 1)],
    'E': [('B', 5), ('D', 1), ('F', 4)],
    'F': [('C', 7), ('E', 4)],
}

start_node = 'A'
mst, total_weight = prim(graph, start_node)
print("Edges in the Minimum Spanning Tree:", mst)
print("Total weight of the MST:", total_weight)

Explanation:

• The graph is represented as an adjacency list, where each key is a vertex, and the value is a list of tuples representing its adjacent vertices and the weights of the connecting edges.
• The priority queue (min_heap) is used to always pick the next vertex with the smallest edge weight.
• The algorithm iterates over the vertices, adding the minimum-weight edge to the MST and updating the adjacent vertices' key values accordingly.

2. Prim’s Algorithm in C++

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <unordered_map>
using namespace std;

typedef pair<int, char> pii;

void prim(unordered_map<char, vector<pii>>& graph, char start) {
    unordered_map<char, int> key;
    unordered_map<char, char> parent;
    unordered_map<char, bool> inMST;

    for (auto& node : graph) {
        key[node.first] = INT_MAX;
        inMST[node.first] = false;
    }
    key[start] = 0;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});

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

        inMST[u] = true;

        // Update the adjacent vertices
        for (auto& neighbor : graph[u]) {
            char v = neighbor.first;
            int weight = neighbor.second;

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

    // Print the MST
    cout << "Edges in the Minimum Spanning Tree:" << endl;
    int totalWeight = 0;
    for (auto& node : parent) {
        if (node.second != 0) {
            cout << node.second << " - " << node.first << " with weight " << key[node.first] << endl;
            totalWeight += key[node.first];
        }
    }
    cout << "Total weight of the MST: " << totalWeight << endl;
}

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

    char start = 'A';
    prim(graph, start);
    return 0;
}

Explanation:

• The graph is represented as an adjacency list where each vertex points to a list of pairs (adjacent vertex, edge weight).
• A priority queue (min-heap) is used to always select the next vertex with the smallest edge weight.
• The key stores the minimum edge weight for each vertex, and parent keeps track of the vertex from which it was added to the MST.
• After the algorithm finishes, the edges in the MST are printed along with their total weight.

---

Performance Analysis of Prim’s Algorithm

• Time Complexity:

  • Sorting the edges or using a priority queue takes O(E log V), where E is the number of edges and V is the number of vertices.
  • The V extra work to update the adjacent vertices in each iteration contributes to an overall time complexity of O(E log V).

• Space Complexity: O(V + E), where V is the number of vertices and E is the number of edges. We need space to store the graph, the key values, the parent pointers, and the priority queue.

---

Applications of Prim’s Algorithm

Prim's Algorithm is used in several real-world applications, such as:

1. Network Design: To design the least-cost network that connects all nodes, such as connecting computers or routers in a network.
2. Cluster Analysis: In data science, Prim’s Algorithm helps form clusters based on minimum distances between data points.
3. Cable Layout Design: In telecommunication and electrical wiring, it minimizes the total length of cable used to connect a set of points.
4. Flight Scheduling: Airlines can use Prim's algorithm to find the minimum-cost connection between airports.

---

---