2.
Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given
connected undirected graph using Prim’s algorithm.
PROGRAM:
#include <stdio.h>
#define INF 999 // Representing no edge
#define MAX_VERTICES 11 // Maximum number of vertices
// DFS Function to Check Connectivity
void dfs(int cost[MAX_VERTICES][MAX_VERTICES], int n, int visited[], int node) {
visited[node] = 1;
for (inti = 1; i<= n; i++) {
if (cost[node][i] != INF && !visited[i]) { // If connected and not visited
dfs(cost, n, visited, i);
}
}
}
// Function to Check if the Graph is Connected
intisConnected(int cost[MAX_VERTICES][MAX_VERTICES], int n) {
int visited[MAX_VERTICES] = {0}; // All nodes initially unvisited
dfs(cost, n, visited, 1); // Start DFS from vertex 1
// Check if all nodes were visited
for (inti = 1; i<= n; i++) {
if (!visited[i]) {
return 0; // Graph is disconnected
}
}
return 1; // Graph is connected
}
// Prim’s Algorithm to find MST
void prims(int cost[MAX_VERTICES][MAX_VERTICES], int n) {
int selected[MAX_VERTICES] = {0}; // Track selected vertices
int edges = 0, min, u, v, totalCost = 0;
selected[1] = 1; // Start with first vertex (1)
printf("\nThe Minimum Spanning Tree (MST) edges are:\n");
while (edges < n - 1) {
min = INF;
u = v = -1;
// Find the minimum weight edge
for (inti = 1; i<= n; i++) {
if (selected[i]) { // Only consider already selected vertices
for (int j = 1; j <= n; j++) {
if (!selected[j] && cost[i][j] < min) { // Edge to unvisited vertex
min = cost[i][j];
u = i;
v = j;
}
}
}
}
// If no valid edge is found, break (Graph is disconnected)
if (u == -1 || v == -1) {
break;
}
// Select the new vertex and print the selected edge
selected[v] = 1;
printf("%d -> %d with cost %d\n", u, v, min);
totalCost += min;
edges++;
}
// Check if MST was formed correctly
if (edges != n - 1) {
printf("\n Spanning Tree does NOT exist (Graph is disconnected) \n");
} else {
printf("\n Total Cost of Minimum Spanning Tree: %d\n", totalCost);
}
}
intmain() {
int cost[MAX_VERTICES][MAX_VERTICES], n;
printf("\nEnter the number of vertices: ");
scanf("%d", &n);
printf("\nEnter the cost adjacency matrix (use 999 for no edge):\n");
for (inti = 1; i<= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0 &&i != j)
cost[i][j] = INF; // Replace 0 with INF except diagonal
}
}
// Check if graph is connected before running Prim’s Algorithm
if (!isConnected(cost, n)) {
printf("\n Spanning Tree does NOT exist (Graph is disconnected) \n");
return 0; // Exit early
}
prims(cost, n); // Run Prim’s algorithm
return 0;
}
OUTPUT:
RUN 1:
Enter the number of vertices: 5
Enter the cost adjacency matrix (use 0 for no edge):
999 5 7 999 2
5 999 999 6 3
7 999 999 4 4
999 6 4 999 6
2 3 4 5 999
The Minimum Spanning Tree (MST) edges are:
1 -> 5 with cost 2
5 -> 2 with cost 3
5 -> 3 with cost 4
3 -> 4 with cost 4
Total Cost of Minimum Spanning Tree: 13
RUN 2:
Enter the number of vertices: 4
Enter the cost adjacency matrix (use 0 for no edge):
999 5 7 999 2
5 999 999 6 3
7 999 999 4 4
999 6 4 999 5
Spanning Tree does NOT exist (Graph is disconnected)