Scribd
Upload
4 views2 pages

DAA Pract 4.cpp

The document contains C++ code implementing Prim's algorithm to find the Minimum Spanning Tree (MST) of a graph represented as an adjacency matrix. It defines a custom priority queue and includes functions to print the MST and execute the algorithm. An example graph is provided, and the output displays the edges and their weights in the MST.

Uploaded by

Parsh Yadav
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

DAA Pract 4.cpp

The document contains C++ code implementing Prim's algorithm to find the Minimum Spanning Tree (MST) of a graph represented as an adjacency matrix. It defines a custom priority queue and includes functions to print the MST and execute the algorithm. An example graph is provided, and the output displays the edges and their weights in the MST.

Uploaded by

Parsh Yadav
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

3/20/25, 2:14 PM DAA Pract 4.

cpp

DAA Pract [Link]

1 #include <iostream>
2 #include <vector>
3 #include <queue>
4 #include <climits>
5
6 using namespace std;
7
8 #define V 5 // Number of vertices in the graph
9
10 // Custom data structure for the priority queue (Min Heap)
11 typedef pair<int, int> pii; // (weight, vertex)
12
13 // Function to print the constructed MST
14 void printMST(vector<int>& parent, vector<vector<int>>& graph) {
15 cout << "Minimum Spanning Tree (MST) Edges:\n";
16 cout << "Edge \tWeight\n";
17 for (int i = 1; i < V; i++) {
18 cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << endl;
19 }
20 }
21
22 // Function to implement Prim's MST using a priority queue
23 void primMST(vector<vector<int>>& graph) {
24 priority_queue<pii, vector<pii>, greater<pii>> pq; // Min Heap
25
26 vector<int> key(V, INT_MAX); // Stores the minimum weight edge for each vertex
27 vector<int> parent(V, -1); // Stores the MST structure
28 vector<bool> inMST(V, false); // Keeps track of vertices included in MST
29
30 // Start from vertex 0
31 key[0] = 0;
32 [Link]({0, 0}); // (weight, vertex)
33
34 while (![Link]()) {
35 int u = [Link]().second; // Get the vertex with the smallest weight
36 [Link]();
37
38 if (inMST[u]) continue; // Skip if already in MST
39 inMST[u] = true; // Mark as included in MST
40
41 // Update adjacent vertices
42 for (int v = 0; v < V; v++) {
43 if (graph[u][v] && !inMST[v] && graph[u][v] < key[v]) {
44 key[v] = graph[u][v]; // Update key with the smaller weight
45 parent[v] = u; // Update parent
46 [Link]({key[v], v}); // Push updated vertex into Min Heap
47 }
48 }
49 }
50
51 // Print the MST

localhost:49630/759e3065-6811-415a-b39b-1e53f3f5caf4/ 1/2
3/20/25, 2:14 PM DAA Pract [Link]

52 printMST(parent, graph);
53 }
54
55 int main() {
56 // Example graph as an adjacency matrix
57 vector<vector<int>> graph = {
58 {0, 2, 0, 6, 0},
59 {2, 0, 3, 8, 5},
60 {0, 3, 0, 0, 7},
61 {6, 8, 0, 0, 9},
62 {0, 5, 7, 9, 0}
63 };
64
65 // Call the function to find MST
66 primMST(graph);
67
68 return 0;
69 }
70
71
72 OUTPUT :-
73
74 Minimum Spanning Tree (MST) Edges:
75 Edge Weight
76 0 - 1 2
77 1 - 2 3
78 0 - 3 6
79 1 - 4 5

localhost:49630/759e3065-6811-415a-b39b-1e53f3f5caf4/ 2/2

You might also like