Lecture 377:- Prim's Program

here's a C++ program for Prim's algorithm to find the Minimum Spanning Tree (MST) of a connected, undirected graph with weighted edges:

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 vector<pii> 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});            }        }    }    // Construct the MST as a vector of edges with their weights    vector<pii> mst;    for (int i = 1; i < vertices; ++i) {        mst.push_back({parent[i], i});    }    return mst; } 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;    vector<pii> mst = primMST(graph, startVertex);    // Print the MST    cout << "Minimum Spanning Tree using Prim's Algorithm:\n";    for (pii edge : mst) {        cout << "Edge: " << edge.first << " - " << edge.second << endl;    }    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 MST starting from the specified startVertex. The MST is represented as a vector of pairs, where each pair represents an edge in the MST along with its weight. The algorithm uses a priority queue to efficiently find the minimum-weight edge in each iteration.