Scribd
Upload
2 views3 pages

Program - 1

The document outlines a C/C++ program designed to find the Minimum Cost Spanning Tree (MST) of a connected undirected graph using Kruskal's algorithm. It includes a step-by-step algorithm, code implementation, and user input for vertices and edges. The program sorts edges by weight, utilizes a disjoint set for cycle detection, and prints the edges included in the MST along with the total weight.

Uploaded by

rohancta57
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
2 views3 pages

Program - 1

The document outlines a C/C++ program designed to find the Minimum Cost Spanning Tree (MST) of a connected undirected graph using Kruskal's algorithm. It includes a step-by-step algorithm, code implementation, and user input for vertices and edges. The program sorts edges by weight, utilizes a disjoint set for cycle detection, and prints the edges included in the MST along with the total weight.

Uploaded by

rohancta57
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

Aim:

Design and implement C/C++ Program to find Minimum Cost Spanning Tree of
a given connected undirected graph using Kruskal's algorithm.

Algorithm:

Step 1: Represent the graph using an adjacency matrix or edge list.


Step 2: Sort all edges in non - decreasing order of weight.
Step 3: Initialize parent[] for each vertex (Disjoint Set Union).
Step 4:
• For each edge in sorted order:
• Find the parent of both vertices using find().
• If they belong to different sets, include the edge in MST and perform
union().
Step 5: Repeat until (n - 1) edges are included
Step 6: Print the MST edges and the total minimum cost.

Code:

#include <stdio.h>

#define MAX 30

int parent[MAX];

// Find function with path compression


int find(int i) {
if (parent[i] == i)
return i;
return parent[i] = find(parent[i]);
}

// Union function
void unionSet(int u, int v) {
parent[find(u)] = find(v);
}

int main() {
int V, E;
int u[MAX], v[MAX], w[MAX]; // arrays for edges
int i, j, total = 0;

printf("Enter number of vertices: ");


scanf("%d", &V);
printf("Enter number of edges: ");
scanf("%d", &E);

printf("Enter edges (u v weight): \n");


for (i = 0; i < E; i++) {
scanf("%d %d %d", &u[i], &v[i], &w[i]);
}

// Initialize parent array


for (i = 0; i < V; i++)
parent[i] = i;

// Sort edges by weight (simple bubble sort)


for (i = 0; i < E - 1; i++) {
for (j = 0; j < E - i - 1; j++) {
if (w[j] > w[j + 1]) {
int temp;
temp = w[j]; w[j] = w[j + 1]; w[j + 1] = temp;
temp = u[j]; u[j] = u[j + 1]; u[j + 1] = temp;
temp = v[j]; v[j] = v[j + 1]; v[j + 1] = temp;
}
}
}

printf("Edges in the Minimum Spanning Tree: \n");


for (i = 0; i < E; i++) {
int rootU = find(u[i]);
int rootV = find(v[i]);

if (rootU != rootV) {
printf("%d -- %d == %d \n", u[i], v[i], w[i]);
total += w[i];
unionSet(rootU, rootV);
}
}

printf("Total weight of MST = %d \n", total);

return 0;
}
Out put:

You might also like