# Minimum Spanning Tree in C

Published on 28 April 2022 (Updated: 02 February 2023) Welcome to the Minimum Spanning Tree in C page! Here, you’ll find the source code for this program as well as a description of how the program works.

## Current Solution

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

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

long long get_val(int tmp[],int len){
long long value=0,mult=1;
for(int i=len-1;i>-1;--i){
if(tmp[i]==' '-'0'){
printf("Usage: please provide a list of at least two integers to sort in the format \"1, 2, 3, 4, 5\"\n");
exit(0);
}
value+=tmp[i]*mult;
mult*=10;
}
return value;
}

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

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

struct subset{
int parent;
int rank;
};

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

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++;
}
}

int myComp(const void* a, const void* b){
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
return a1->weight > b1->weight;
}

void KruskalMST(struct Graph* graph){
int V = graph->V;
long long res=0;
int e = 0;
int i = 0;
qsort(graph->edge, graph->E, sizeof(graph->edge), myComp);

struct subset *subsets =(struct subset*)malloc( V * sizeof(struct subset) );
for(int v = 0; v < V; ++v){
subsets[v].parent = v;
subsets[v].rank = 0;
}
while (e < V - 1 && i < graph->E){
struct Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y){
res = res + next_edge.weight;
Union(subsets, x, y);
}
}
printf("%lld",res);
return;
}

int floorSqrt(int x){
if (x == 0 || x == 1)return x;
int i = 1,result = 1;
while (result <= x){
i++;
result = i * i;
}
return i - 1;
}

int main(int argc,char **argv)
{
if(argv==NULL||strlen(argv)==0){
printf("Usage: please provide a comma-separated list of integers");
return 0;
}

int len = strlen(argv);
int tmp;
int ind=0;
int pos=0;
long long arr;
int E=0;
for(int i=0;i<len;++i){
if(argv[i]==','){
long long val = get_val(tmp,ind);
ind=0;
i++;
arr[pos++]=val;
if(val!=0)E++;
continue;
}
tmp[ind++]=argv[i]-'0';
}
arr[pos++]=get_val(tmp,ind);
int sq=floorSqrt(pos);
if(pos!=sq*sq){
printf("Usage: please provide a comma-separated list of integers");
return 0;
}
int V=sq;

struct Graph* graph = createGraph(V, E);
int index=0;
for(int i=0;i<pos;++i){
if(arr[i]==0)continue;
graph->edge[index].src = i/V;
graph->edge[index].dest = i-(i/V)*V;
graph->edge[index++].weight = arr[i];
}
KruskalMST(graph);
}
``````

Minimum Spanning Tree in C was written by:

• Jeremy Grifski
• LezendarySandwich

If you see anything you’d like to change or update, please consider contributing.

Note: The solution shown above is the current solution in the Sample Programs repository as of Apr 28 2022 18:14:37. The solution was first committed on Oct 20 2019 01:25:16. As a result, documentation below may be outdated.

## How to Implement the Solution

No ‘How to Implement the Solution’ section available. Please consider contributing.

## How to Run the Solution

No ‘How to Run the Solution’ section available. Please consider contributing.