Prim’s Algorithm

Prim’s algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, undirected graph. The purpose of the algorithm is to connect all vertices in the graph with the minimum possible total edge weight, ensuring there are no cycles and that each vertex is reachable from any other vertex. This is particularly useful in scenarios where you need to minimize costs, like connecting points or nodes using the least amount of resources.
Ref: Prim’s Algorithm

How Prim’s Algorithm Works

Prim’s algorithm starts with a single vertex and expands the MST by adding the shortest edge connecting a vertex in the MST to a vertex outside of it. It repeats this process until all vertices are included in the MST, ensuring that each addition minimizes the overall edge weight.

Real-World Applications of Prim’s Algorithm

  1. Network Design: Connecting infrastructure in an optimized way:
    • Telecommunication Networks: Prim’s algorithm can be used to lay out cables or fiber-optic networks that connect multiple locations (like cities or neighborhoods) in a way that minimizes the total cable length or cost.
    • Road and Railway Networks: When constructing roads, railways, or electrical grids to connect cities or towns, Prim’s algorithm can help identify the minimum road or rail length needed to connect all locations.
  2. Circuit Design:
    • Prim’s algorithm can be applied in designing circuit board layouts to minimize the total length of wiring. This minimizes both manufacturing costs and potential electrical resistance across the circuit.
  3. Computer Network Design:
    • In data centers, it’s important to have multiple computers and servers interconnected while minimizing the wiring length and associated costs. Prim’s algorithm can be used to design a local area network (LAN) that connects all devices with the minimum wiring required.
  4. Clustering in Data Analysis:
    • Prim’s algorithm can also be applied in data clustering tasks. For example, in geographic or social network analysis, Prim’s algorithm can help form clusters by connecting nodes with minimal distances while avoiding redundant or excessive connections.
  5. Approximation Algorithms for NP-Hard Problems:
    • In problems like the Traveling Salesman Problem (TSP), Prim’s algorithm can be used as part of an approximation solution by constructing an MST and using it as a basis to approximate the shortest path that visits each vertex.
  6. Power Grid Optimization:
    • Prim’s algorithm can help design an efficient electrical grid by minimizing the amount of cabling needed to connect multiple distribution points, thus reducing both the construction and maintenance costs of power lines.

Example Scenario

Consider a scenario where a company needs to connect several office buildings in a metropolitan area with a high-speed internet backbone. Using Prim’s algorithm, the company can find the optimal way to lay out the network cables to connect all the buildings with minimal cost. This way, each building can access the network without redundant connections, ensuring cost-efficiency.

By choosing minimal-cost connections, Prim’s algorithm ensures that the final infrastructure is both efficient and cost-effective, which is valuable in real-world scenarios involving resource management.

Program: prims_algorithm.cpp (Github)

include <iostream>
#include <vector>
#include <climits>  // For INT_MAX
using namespace std;

// Number of vertices in the graph
#define V 5

// Function to find the vertex with minimum key value, from
// the set of vertices not yet included in the MST
int minKey(const vector<int>& key, const vector<bool>& mstSet) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (!mstSet[v] && key[v] < min)
            min = key[v], min_index = v;

    return min_index;
}

// Function to print the constructed MST stored in parent[]
void printMST(const vector<int>& parent, const vector<vector<int>>& graph) {
    cout << "Edge \tWeight\n";
    for (int i = 1; i < V; i++)
        cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << " \n";
}

// Function to construct and print the MST for a graph
// represented using adjacency matrix representation
void primMST(const vector<vector<int>>& graph) {
    // Array to store constructed MST
    vector<int> parent(V);
    
    // Key values used to pick minimum weight edge in cut
    vector<int> key(V, INT_MAX);
    
    // To represent set of vertices included in MST
    vector<bool> mstSet(V, false);

    // Initialize the first vertex key as 0 so that it is picked first
    key[0] = 0;
    parent[0] = -1;  // First node is always the root of MST

    // The MST will have V vertices
    for (int count = 0; count < V - 1; count++) {
        // Pick the minimum key vertex from the set of vertices
        // not yet included in MST
        int u = minKey(key, mstSet);

        // Add the picked vertex to the MST Set
        mstSet[u] = true;

        // Update key value and parent index of the adjacent vertices
        // of the picked vertex. Consider only those vertices which are
        // not yet included in MST
        for (int v = 0; v < V; v++)
            // graph[u][v] is non-zero only for adjacent vertices of u
            // mstSet[v] is false for vertices not yet included in MST
            // Update the key only if graph[u][v] is smaller than key[v]
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
    }

    // Print the constructed MST
    printMST(parent, graph);
}

int main() {
    // Example graph represented as an adjacency matrix
    vector<vector<int>> graph = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };

    // Display the Minimum Spanning Tree
    primMST(graph);

    return 0;
}

Explanation

  1. Graph Representation:
    • The graph is represented as an adjacency matrix, where graph[i][j] represents the weight of the edge between vertices i and j.
    • A value of 0 indicates no direct edge between the vertices.
  2. Prim’s Algorithm:
    • minKey Function: Finds the vertex with the minimum key value from the set of vertices not yet included in the MST.
    • primMST Function: Constructs the MST by repeatedly selecting the minimum weight edge that connects a vertex in the MST to a vertex outside the MST.
    • Key Array: Stores the minimum edge weight needed to connect each vertex to the MST.
    • Parent Array: Stores the parent of each vertex in the MST.
  3. Printing the MST:
    • printMST Function: Displays the edges in the MST along with their weights by iterating through the parent array.

Scroll to Top