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 Shared Function MinKey(key As Integer(), [set] As Boolean(), verticesCount As Integer) As Integer
	Dim min As Integer = Integer.MaxValue, minIndex As Integer = 0

	For v As Integer = 0 To verticesCount - 1
		If [set](v) = False AndAlso key(v) < min Then
			min = key(v)
			minIndex = v
		End If
	Next

	Return minIndex
End Function

Private Shared Sub Print(parent As Integer(), graph As Integer(,), verticesCount As Integer)
	Console.WriteLine("Edge     Weight")
	For i As Integer = 1 To verticesCount - 1
		Console.WriteLine("{0} - {1}    {2}", parent(i), i, graph(i, parent(i)))
	Next
End Sub

Public Shared Sub Prim(graph As Integer(,), verticesCount As Integer)
	Dim parent As Integer() = New Integer(verticesCount - 1) {}
	Dim key As Integer() = New Integer(verticesCount - 1) {}
	Dim mstSet As Boolean() = New Boolean(verticesCount - 1) {}

	For i As Integer = 0 To verticesCount - 1
		key(i) = Integer.MaxValue
		mstSet(i) = False
	Next

	key(0) = 0
	parent(0) = -1

	For count As Integer = 0 To verticesCount - 2
		Dim u As Integer = MinKey(key, mstSet, verticesCount)
		mstSet(u) = True

		For v As Integer = 0 To verticesCount - 1
			If Convert.ToBoolean(graph(u, v)) AndAlso mstSet(v) = False AndAlso graph(u, v) < key(v) Then
				parent(v) = u
				key(v) = graph(u, v)
			End If
		Next
	Next

	Print(parent, graph, verticesCount)
End Sub

Example

									Dim graph As Integer(,) = {{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