Lecture 376:- Prim's Minimum Cost Spanning Tree

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree (MST) for a connected, undirected graph with weighted edges. The minimum spanning tree is a subgraph that includes all the vertices of the original graph and has the minimum possible total edge weight. Prim's algorithm works by starting from an arbitrary vertex and repeatedly adding the minimum-weight edge that connects a vertex in the MST to a vertex outside the MST, until all vertices are included in the MST.

The steps of Prim's algorithm are as follows:

1. Initialize an empty MST and a set of visited vertices.
2. Choose an arbitrary vertex as the starting point and add it to the MST and the visited set.
3. While the MST does not include all vertices: a. Find the minimum-weight edge that connects a vertex in the MST to a vertex outside the MST. b. Add the selected edge and the corresponding vertex to the MST and the visited set.

Here's a C++ implementation of Prim's algorithm:

cppCopy code

#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; typedef pair<int, int> pii; // pair<weight, vertex> // Function to find the minimum cost spanning tree using Prim's algorithm void primMST(vector<vector<pii>>& graph, int startVertex) {    int vertices = graph.size();    vector<bool> visited(vertices, false);    vector<int> key(vertices, INT_MAX);    vector<int> parent(vertices, -1);    priority_queue<pii, vector<pii>, greater<pii>> pq;    pq.push({0, startVertex}); // Start from the specified startVertex with weight 0.    while (!pq.empty()) {        int u = pq.top().second;        pq.pop();        if (visited[u]) {            continue;        }        visited[u] = true;        for (pii& edge : graph[u]) {            int v = edge.first;            int weight = edge.second;            if (!visited[v] && weight < key[v]) {                key[v] = weight;                parent[v] = u;                pq.push({key[v], v});            }        }    }    // Print the MST    cout << "Minimum Spanning Tree using Prim's Algorithm:\n";    for (int i = 1; i < vertices; ++i) {        cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] << endl;    } } int main() {    int vertices, edges;    cout << "Enter the number of vertices and edges: ";    cin >> vertices >> edges;    vector<vector<pii>> graph(vertices);    cout << "Enter the edges (source, destination, weight):" << endl;    for (int i = 0; i < edges; ++i) {        int src, dest, weight;        cin >> src >> dest >> weight;        graph[src].push_back({dest, weight});        graph[dest].push_back({src, weight}); // For undirected graph    }    int startVertex;    cout << "Enter the start vertex for MST: ";    cin >> startVertex;    primMST(graph, startVertex);    return 0; }

In this implementation, the graph is represented as a vector of vectors of pairs, where each pair represents an edge with its weight. The primMST function performs Prim's algorithm to find the minimum cost spanning tree starting from the specified startVertex. The MST is printed as a set of edges along with their weights. The algorithm uses a priority queue to efficiently find the minimum-weight edge in each iteration.