Scribd
Upload
5 views2 pages

Program 1

The document provides a C program that implements Kruskal's algorithm to find the Minimum Cost Spanning Tree of a connected undirected graph. It includes an algorithm outline, code for sorting edges, and functions for union and find operations. The program prompts the user for the number of vertices and edges, inputs the edges, and outputs the edges in the Minimum Spanning Tree along with the minimum cost.

Uploaded by

chinmayar0112
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
5 views2 pages

Program 1

The document provides a C program that implements Kruskal's algorithm to find the Minimum Cost Spanning Tree of a connected undirected graph. It includes an algorithm outline, code for sorting edges, and functions for union and find operations. The program prompts the user for the number of vertices and edges, inputs the edges, and outputs the edges in the Minimum Spanning Tree along with the minimum cost.

Uploaded by

chinmayar0112
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

1.

Design and implement a C program to find Minimum cost Spanning tree of a


given connected undirected graphp using kruskal's algorithm

ALGORITHM:

Input: A weighted connected graph G = (V, E)


Output: ET, the set of edges of a minimum spanning tree

1. Sort E in non-decreasing order of weights


2. ET ← ∅
3. edge_count ← 0
4. k ← 0

5. while edge_count < |V| − 1 do


k←k+1
if adding ek does not form a cycle then
ET ← ET ∪ {ek}
edge_count ← edge_count + 1
6. return ET

PROGRAM:

#include <stdio.h>
#define MAX 100

struct Edge {
int u, v, weight;
};

int parent[MAX];

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

void unionSet(int u, int v) {


parent[u] = v;
}

int main() {
int V, E;
struct Edge edges[MAX], temp;

printf("Enter number of vertices: ");


scanf("%d", &V);

printf("Enter number of edges: ");


scanf("%d", &E);

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


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

for (int i = 0; i < V; i++)


parent[i] = i;

for (int i = 0; i < E - 1; i++) {


for (int j = 0; j < E - i - 1; j++) {
if (edges[j].weight > edges[j + 1].weight) {
temp = edges[j];
edges[j] = edges[j + 1];
edges[j + 1] = temp;
}
}
}

int count = 0;
int minCost = 0;

printf("\nEdges in MST:\n");

for (int i = 0; i < E && count < V - 1; i++) {

int u = find(edges[i].u);
int v = find(edges[i].v);

if (u != v) {
printf("%d -- %d = %d\n",
edges[i].u, edges[i].v, edges[i].weight);

minCost += edges[i].weight;
unionSet(u, v);
count++;
}
}

printf("\nMinimum Cost = %d\n", minCost);


return 0;
}

You might also like