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.

									private static int MinKey(int[] key, bool[] set, int verticesCount)
{
	int min = int.MaxValue, minIndex = 0;

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

	return minIndex;
}

private static void Print(int[] parent, int[,] graph, int verticesCount)
{
	Console.WriteLine("Edge     Weight");
	for (int i = 1; i < verticesCount; ++i)
		Console.WriteLine("{0} - {1}    {2}", parent[i], i, graph[i, parent[i]]);
}

public static void Prim(int[,] graph, int verticesCount)
{
	int[] parent = new int[verticesCount];
	int[] key = new int[verticesCount];
	bool[] mstSet = new bool[verticesCount];

	for (int i = 0; i < verticesCount; ++i)
	{
		key[i] = int.MaxValue;
		mstSet[i] = false;
	}

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

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

		for (int v = 0; v < verticesCount; ++v)
		{
			if (Convert.ToBoolean(graph[u, v]) && mstSet[v] == false && graph[u, v] < key[v])
			{
				parent[v] = u;
				key[v] = graph[u, v];
			}
		}
	}

	Print(parent, graph, verticesCount);
}

Example

									int[,] graph = {
	{ 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, 5);

Output

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