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).

									Public Structure Edge
	Public Source As Integer
	Public Destination As Integer
	Public Weight As Integer
End Structure

Public Structure Graph
	Public VerticesCount As Integer
	Public EdgesCount As Integer
	Public edge As Edge()
End Structure

Public Structure Subset
	Public Parent As Integer
	Public Rank As Integer
End Structure

Public Shared Function CreateGraph(verticesCount As Integer, edgesCoun As Integer) As Graph
	Dim graph As New Graph()
	graph.VerticesCount = verticesCount
	graph.EdgesCount = edgesCoun
	graph.edge = New Edge(graph.EdgesCount - 1) {}

	Return graph
End Function

Private Shared Function Find(subsets As Subset(), i As Integer) As Integer
	If subsets(i).Parent <> i Then
		subsets(i).Parent = Find(subsets, subsets(i).Parent)
	End If

	Return subsets(i).Parent
End Function

Private Shared Sub Union(subsets As Subset(), x As Integer, y As Integer)
	Dim xroot As Integer = Find(subsets, x)
	Dim yroot As Integer = Find(subsets, y)

	If subsets(xroot).Rank < subsets(yroot).Rank Then
		subsets(xroot).Parent = yroot
	ElseIf subsets(xroot).Rank > subsets(yroot).Rank Then
		subsets(yroot).Parent = xroot
	Else
		subsets(yroot).Parent = xroot
		subsets(xroot).Rank += 1
	End If
End Sub

Private Shared Sub Print(result As Edge(), e As Integer)
	For i As Integer = 0 To e - 1
		Console.WriteLine("{0} -- {1} == {2}", result(i).Source, result(i).Destination, result(i).Weight)
	Next
End Sub

Public Shared Sub Kruskal(graph As Graph)
	Dim verticesCount As Integer = graph.VerticesCount
	Dim result As Edge() = New Edge(verticesCount - 1) {}
	Dim i As Integer = 0
	Dim e As Integer = 0

	Array.Sort(graph.edge, Function(a As Edge, b As Edge) a.Weight.CompareTo(b.Weight))

	Dim subsets As Subset() = New Subset(verticesCount - 1) {}

	For v As Integer = 0 To verticesCount - 1
		subsets(v).Parent = v
		subsets(v).Rank = 0
	Next

	While e < verticesCount - 1
		Dim nextEdge As Edge = graph.edge(i)
		Dim x As Integer = Find(subsets, nextEdge.Source)
		Dim y As Integer = Find(subsets, nextEdge.Destination)
		i += 1

		If x <> y Then
			result(e) = nextEdge
			e += 1
			Union(subsets, x, y)
		End If
	End While

	Print(result, e)
End Sub

Example

									Dim verticesCount As Integer = 4
Dim edgesCount As Integer = 5
Dim graph As 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