kruskal's minimum spanning tree algorithn' code example

Example: Kruskal's Algorithm for minimum spanning tree

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

typedef struct node
{
	int source;
	int destination;
	int weight;
} Edge;

typedef struct Graph
{
	int num_of_vertex;
	int num_of_edge;
	Edge *edge;
} Graph;

typedef struct subset
{
	int parent;
	int rank;
} Subset;



Graph *create_graph (int V, int E)
{
	Graph *new_graph = (Graph *) malloc (sizeof (Graph));
	new_graph -> num_of_vertex = V;
	new_graph -> num_of_edge = E;

	new_graph -> edge = (Edge *) malloc (new_graph -> num_of_edge * sizeof (Edge));
	return new_graph;
}


int find_set (Subset subset[], int i)
{
	if (subset[i]. parent != i)
	{
		subset[i]. parent = find_set (subset, subset[i]. parent);
	}

	return subset[i]. parent;
}


void Union (Subset subset[], int x, int y)
{
	int x_parent = find_set (subset, x);
	int y_parent = find_set (subset, y);

	if (subset [x_parent]. rank < subset [y_parent]. rank)
	{
		subset [x_parent]. parent = y_parent;
		subset [y_parent]. rank += 1;
	}

	else
	{
		subset [y_parent]. parent = x_parent;
		subset [x_parent]. rank += 1;
	}
}


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


void KruskalMST (Graph *graph)
{
	int V = graph -> num_of_vertex;
	Edge result [V];
	qsort (graph -> edge, graph -> num_of_edge, sizeof (graph -> edge [0]), comparison);

	Subset *subset = (Subset *) malloc (V * sizeof (Subset));
	for (int i = 0; i < V; i++)
	{
		subset [i]. parent = i;
		subset [i]. rank = 0;
	}

	int e = 0;
	int i = 0;
	while (e < V-1)
	{
		Edge temp_edge = graph -> edge[i];
		i++;

		int parent_src = find_set (subset, temp_edge. source);
		int parent_dest = find_set (subset, temp_edge. destination);

		if (parent_src != parent_dest)
		{
			result [e] = temp_edge;
			e++;
			Union (subset, parent_src, parent_dest);
		}
	}

	printf("Following are the edges in the constructed MST\n");
    for (i = 0; i < e; i++)
        printf("%d -- %d == %d\n", result[i]. source, result[i]. destination, result[i]. weight);
}




void main()
{
    int V = 4;
    int E = 5;
    Graph* graph = create_graph(V, E);


    // add edge 0-1
    graph->edge[0].source = 0;
    graph->edge[0].destination = 1;
    graph->edge[0].weight = 10;

    // add edge 0-2
    graph->edge[1].source = 0;
    graph->edge[1].destination = 2;
    graph->edge[1].weight = 6;

    // add edge 0-3
    graph->edge[2].source = 0;
    graph->edge[2].destination = 3;
    graph->edge[2].weight = 5;

    // add edge 1-3
    graph->edge[3].source = 1;
    graph->edge[3].destination = 3;
    graph->edge[3].weight = 15;

    // add edge 2-3
    graph->edge[4].source = 2;
    graph->edge[4].destination = 3;
    graph->edge[4].weight = 4;

    KruskalMST(graph);
}