Prim's Algorithm

Prim's algorithm, also known as DJP algorithm, Jarník's algorithm, Prim–Jarník algorithm or Prim–Dijkstra algorithm, is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. 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. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

									/*****Please include following header files*****/
// stdio.h
// limits.h
// stdbool.h
/***********************************************/

#define VERTICES_COUNT 5

int MinKey(int key[], bool set[])
{
	int min = INT_MAX, minIndex;

	for (int v = 0; v < VERTICES_COUNT; ++v)
	{
		if (set[v] == false && key[v] < min)
		{
			min = key[v];
			minIndex = v;
		}
	}

	return minIndex;
}

void Print(int parent[], int graph[VERTICES_COUNT][VERTICES_COUNT])
{
	printf("Edge     Weight\n");
	for (int i = 1; i < VERTICES_COUNT; ++i)
		printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);
}

void Prim(int graph[VERTICES_COUNT][VERTICES_COUNT])
{
	int parent[VERTICES_COUNT];
	int key[VERTICES_COUNT];
	bool mstSet[VERTICES_COUNT];

	for (int i = 0; i < VERTICES_COUNT; ++i)
		key[i] = INT_MAX, mstSet[i] = false;

	key[0] = 0;
	parent[0] = -1;

	for (int count = 0; count < VERTICES_COUNT - 1; ++count)
	{
		int u = MinKey(key, mstSet);
		mstSet[u] = true;

		for (int v = 0; v < VERTICES_COUNT; ++v)
		{
			if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
			{
				parent[v] = u;
				key[v] = graph[u][v];
			}
		}
	}

	Print(parent, graph);
}

Example

									int graph[VERTICES_COUNT][VERTICES_COUNT] = {
	{ 0, 2, 0, 6, 0 },
	{ 2, 0, 3, 8, 5 },
	{ 0, 3, 0, 0, 7 },
	{ 6, 8, 0, 0, 9 },
	{ 0, 5, 7, 9, 0 },
};

Prim(graph);

Output

									Edge     Weight
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5