Scribd
Upload
14 views

Kruskal's Algorithm for minimum spanning tree

The document presents an implementation of Kruskal's Algorithm in C for finding the minimum spanning tree of a graph. It includes the necessary data structures, functions for union-find, sorting edges, and the main function to create a graph and execute the algorithm. The output displays the edges included in the resulting minimum spanning tree.

Uploaded by

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

Kruskal's Algorithm for minimum spanning tree

The document presents an implementation of Kruskal's Algorithm in C for finding the minimum spanning tree of a graph. It includes the necessary data structures, functions for union-find, sorting edges, and the main function to create a graph and execute the algorithm. The output displays the edges included in the resulting minimum spanning tree.

Uploaded by

Kedar Ghadge
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Assignment 20

Name: Archit Bhandare Roll No: 66 Batch: F3

Title: Implementation of Kruskal's Algorithm for minimum spanning tree in


C
CODE:

#include <stdio.h>
#include <stdlib.h>

// Structure to represent an edge


struct Edge {
int src, dest, weight;
};

// Structure to represent a graph


struct Graph {
int V, E;
struct Edge* edges;
};

// Structure to represent a subset for union-find


struct Subset {
int parent;
int rank;
};

// Function to create a graph with V vertices and E edges


struct Graph* createGraph(int V, int E) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edges = (struct Edge*)malloc(E * sizeof(struct Edge));
return graph;
}

// Function to find set of an element i (uses path compression)


int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}

// Function to do union of two sets (uses union by rank)


void Union(struct Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);

if (subsets[xroot].rank < subsets[yroot].rank) {


subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}

// Comparison function to sort edges by weight


int compareEdges(const void* a, const void* b) {
struct Edge* edgeA = (struct Edge*)a;
struct Edge* edgeB = (struct Edge*)b;
return edgeA->weight - edgeB->weight;
}

// Function to implement Kruskal's algorithm


void KruskalMST(struct Graph* graph) {
int V = graph->V;
struct Edge result[V]; // This will store the resulting MST
int e = 0; // Index variable for result[]
int i = 0; // Index variable for sorted edges

// Step 1: Sort all the edges in non-decreasing order of their weight


qsort(graph->edges, graph->E, sizeof(graph->edges[0]), compareEdges);
// Allocate memory for creating V subsets
struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));

// Create V subsets with single elements


for (int v = 0; v < V; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}

// Number of edges to be taken is equal to V-1


while (e < V - 1 && i < graph->E) {
// Step 2: Pick the smallest edge. Check if it forms a cycle
struct Edge nextEdge = graph->edges[i++];

int x = find(subsets, nextEdge.src);


int y = find(subsets, nextEdge.dest);

// If including this edge does not cause a cycle, include it in result


// and move to the next edge
if (x != y) {
result[e++] = nextEdge;
Union(subsets, x, y);
}
}

// Print the resulting MST


printf("Edges in the Minimum Spanning Tree:\n");
printf("Src - Dest : Weight\n");
for (i = 0; i < e; i++) {
printf("%d - %d : %d\n", result[i].src, result[i].dest, result[i].weight);
}

// Free allocated memory


free(subsets);
}
// Main function to test the Kruskal's algorithm
int main() {
int V = 4; // Number of vertices in graph
int E = 5; // Number of edges in graph
struct Graph* graph = createGraph(V, E);

// Add edges to the graph


graph->edges[0].src = 0;
graph->edges[0].dest = 1;
graph->edges[0].weight = 10;

graph->edges[1].src = 0;
graph->edges[1].dest = 2;
graph->edges[1].weight = 6;

graph->edges[2].src = 0;
graph->edges[2].dest = 3;
graph->edges[2].weight = 5;

graph->edges[3].src = 1;
graph->edges[3].dest = 3;
graph->edges[3].weight = 15;

graph->edges[4].src = 2;
graph->edges[4].dest = 3;
graph->edges[4].weight = 4;

// Function call
KruskalMST(graph);

// Free allocated memory for edges


free(graph->edges);
free(graph);

return 0;
}
OUTPUT:

You might also like