Kruskal algorithm in C
Given a weighted graph, Kruskal's algorithm generates a spanning tree with the lowest possible weights. Start by creating an edge list for the given graph, including the weights. Sort the edge list based on the weight in ascending order. Attach each hub to create a skeleton and traverse thetree.
Select the edge with the lowest weight at the top of the list of edges. Get this edge from the list of edges. The specified edges connect the vertices of the skeleton. If the skeleton connects vertices to form a circle, discard this edge. Steps 5 through 7 can be repeated until n-1 edges have been added or the edge listis complete. To go back.
What is a Spanner Tree?
A subset of a connected graph G, called a ``distance tree'', is a subset of a connected graph G in which alledges are connected so that it can go from any edge to any edge, with or without intermediate levels. You can move. Similarly, do not include cycles in the traversing tree. So if your connected graph has N vertices, the answer is no. The maximum number of edges a spanning tree can have is N-1.
What is a Minimal-spanning Tree?
A spanning tree in a connectedundirected graph is a subgraph that connects allthe vertices of the graph multiple spanning trees can exist in one graph. For weighted connected undirected graphs, a spanning tree with a weightless than or equal to the weight of all other spanning trees is called a minimum spanning tree (MST). The sum of the weights assigned to each edge of the spanning tree is the spanning tree weight.
How many edges does theminimum spanning tree have?
The minimum spanning tree has (V - 1) edges where V is the number of vertices in the graph.
It belongs to the class of greedy algorithms that try to find the global optimum by finding the local optimum Start with the edge with the lowest weight and add more edges until you reach your goal. Below are the steps to put Kruskal's algorithm into practice.
Add the edge with the lowest weight to the spanning tree and sort alledges from lowest to highest. Discard this edge if adding it causes a cycle. Continue adding edges until allvertices are placed.
#include <stdio.h>
#define MAX 30
typedef struct edge {
int u, v, w;
} edge;
typedef struct edge_list {
edge data[MAX];
int n;
} edge_list;
edge_listelist;
int Graph[MAX][MAX], n;
edge_listspanlist;
void kruskalAlgo();
int find(int belongs[], int vertexno);
void applyUnion(int belongs[], int c1, int c2);
void sort();
void print();
void kruskalAlgo() {
int belongs[MAX], i, j, cno1, cno2;
elist.n = 0;
for (i = 1; i< n; i++)
for (j = 0; j <i; j++) {
if (Graph[i][j] != 0)
elist.data[elist.n].u = i;
elist.data[elist.n].v = j;
elist.data[elist.n].w = Graph[i][j];
elist.n++; } }
sort();
for (i = 0; i< n; i++)
belongs[i] = i;
spanlist.n = 0;
for (i = 0; i<elist.n; i++) {
cno1 = find(belongs, elist.data[i].u);
cno2 = find(belongs, elist.data[i].v);
if (cno1 != cno2) {
spanlist.data[spanlist.n] = elist.data[i];
spanlist.n = spanlist.n + 1;
applyUnion(belongs, cno1, cno2); } } }
int find(int belongs[], int vertexno) {
return (belongs[vertexno]);
}
void applyUnion(int belongs[], int c1, int c2) {
int i;
for (i = 0; i< n; i++)
if (belongs[i] == c2)
belongs[i] = c1;
}
// Sorting algo
void sort() {
int i, j;
edge temp;
for (i = 1; i<elist.n; i++)
for (j = 0; j <elist.n - 1; j++)
if (elist.data[j].w>elist.data[j + 1].w) {
temp = elist.data[j];
elist.data[j] = elist.data[j + 1];
elist.data[j + 1] = temp; } }
// Printing the result
void print() {
int i, cost = 0;
for (i = 0; i<spanlist.n; i++) {
printf("\n%d - %d : %d", spanlist.data[i].u, spanlist.data[i].v, spanlist.data[i].w);
cost = cost + spanlist.data[i].w; }
printf("\nSpanning tree cost: %d", cost) ; }
int main() {
int i, j, total_cost;
n = 6;
Graph[0][0] = 0;
Graph[0][1] = 4;
Graph[0][2] = 4;
Graph[0][3] = 0;
Graph[0][4] = 0;
Graph[0][5] = 0;
Graph[0][6] = 0;
Graph[1][0] = 4;
Graph[1][1] = 0;
Graph[1][2] = 2;
Graph[1][3] = 0;
Graph[1][4] = 0;
Graph[1][5] = 0;
Graph[1][6] = 0;
Graph[2][0] = 4;
Graph[2][1] = 2;
Graph[2][2] = 0;
Graph[2][3] = 3;
Graph[2][4] = 4;
Graph[2][5] = 0;
Graph[2][6] = 0;
Graph[3][0] = 0;
Graph[3][1] = 0;
Graph[3][2] = 3;
Graph[3][3] = 0;
Graph[3][4] = 3;
Graph[3][5] = 0;
Graph[3][6] = 0;
Graph[4][0] = 0;
Graph[4][1] = 0;
Graph[4][2] = 4;
Graph[4][3] = 3;
Graph[4][4] = 0;
Graph[4][5] = 0;
Graph[4][6] = 0;
Graph[5][0] = 0;
Graph[5][1] = 0;
Graph[5][3] = 0;
Graph[5][4] = 3;
Graph[5][5] = 0;
Graph[5][6] = 0;
kruskalAlgo();
print();
}
The time complexity Of Kruskal's Algorithm is O(E log E).