Kruskal's Algorithm

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

• C#
• VB.Net
• C
• C++
• PHP

									/*****Please include following header files*****/
// stdio.h
// stdlib.h
/***********************************************/

struct Edge
{
	int Source;
	int Destination;
	int Weight;
};

struct Graph
{
	int VerticesCount;
	int EdgesCount;
	struct Edge* Edge;
};

struct Subset
{
	int Parent;
	int Rank;
};

static struct Graph* CreateGraph(int verticesCount, int edgesCoun)
{
	struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
	graph->VerticesCount = verticesCount;
	graph->EdgesCount = edgesCoun;
	graph->Edge = (struct Edge*)malloc(graph->EdgesCount * sizeof(struct Edge));

	return graph;
}

static int Find(struct Subset subsets[], int i)
{
	if (subsets[i].Parent != i)
		subsets[i].Parent = Find(subsets, subsets[i].Parent);

	return subsets[i].Parent;
}

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

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

static void Print(struct Edge* result, int e)
{
	for (int i = 0; i < e; ++i)
		printf("%d -- %d == %d\n", result[i].Source, result[i].Destination, result[i].Weight);
}

static void Kruskal(struct Graph* graph)
{
	int verticesCount = graph->VerticesCount;
	struct Edge* result = (struct Edge*)malloc(sizeof(result) * verticesCount);
	int i = 0;
	int e = 0;

	qsort(graph->Edge, graph->EdgesCount, sizeof(graph->Edge[0]), CompareEdges);

	struct Subset* subsets = (struct Subset*) malloc(verticesCount * sizeof(struct Subset));

	for (int v = 0; v < verticesCount; ++v)
	{
		subsets[v].Parent = v;
		subsets[v].Rank = 0;
	}

	while (e < verticesCount - 1)
	{
		struct Edge nextEdge = graph->Edge[i++];
		int x = Find(subsets, nextEdge.Source);
		int y = Find(subsets, nextEdge.Destination);

		if (x != y)
		{
			result[e++] = nextEdge;
			Union(subsets, x, y);
		}
	}

	Print(result, e);
}
								

Example

									int verticesCount = 4;
int edgesCount = 5;
struct Graph* graph = CreateGraph(verticesCount, edgesCount);

// Edge 0-1
graph->Edge[0].Source = 0;
graph->Edge[0].Destination = 1;
graph->Edge[0].Weight = 10;

// Edge 0-2
graph->Edge[1].Source = 0;
graph->Edge[1].Destination = 2;
graph->Edge[1].Weight = 6;

// Edge 0-3
graph->Edge[2].Source = 0;
graph->Edge[2].Destination = 3;
graph->Edge[2].Weight = 5;

// Edge 1-3
graph->Edge[3].Source = 1;
graph->Edge[3].Destination = 3;
graph->Edge[3].Weight = 15;

// Edge 2-3
graph->Edge[4].Source = 2;
graph->Edge[4].Destination = 3;
graph->Edge[4].Weight = 4;

Kruskal(graph);
								

Output

									2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10