Kruskal MST Algorithm
The Kruskal's Minimum Spanning Tree (MST) Algorithm is an efficient and popular graph algorithm used for finding the minimum spanning tree of an undirected, connected, and weighted graph. This algorithm was developed by Joseph Kruskal in 1956 and is widely used in the field of network design, computer science, and operations research. The primary objective of the Kruskal's MST Algorithm is to find a tree that spans all the vertices in the graph while minimizing the total weight of the edges. In other words, the algorithm aims to connect all the nodes in the graph such that the sum of the edge weights is as low as possible and there are no cycles in the resulting tree.
The Kruskal's MST Algorithm operates in a greedy manner, meaning it makes the best local choice at each step with the hope of finding the global optimum. The algorithm starts with sorting all the edges of the graph in non-decreasing order of their weights. Then, it iteratively adds the edges with the lowest weight to the spanning tree, ensuring that the addition of the edge does not create a cycle within the tree. To detect cycles, a disjoint-set data structure, also known as a union-find data structure, is used to keep track of the connected components in the tree. The process is repeated until the minimum spanning tree includes all the vertices or when the edge list is exhausted. The result is a tree with the minimum possible total edge weight that connects all the vertices in the graph.
/*
* Copyright (c) 2017 Kotlin Algorithm Club
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
package com.algorithmexamples.graphs.undirected.weighted
import com.algorithmexamples.datastructures.DisjointSet
import com.algorithmexamples.datastructures.PriorityQueue
import com.algorithmexamples.datastructures.Queue
/**
* Kruskal's algorithm will grow a solution from the cheapest edge by adding the next cheapest edge,
* provided that it doesn't create a cycle.
*/
class KruskalMST(G: UWGraph): MST {
var weight: Double = 0.0
var edges: Queue<UWGraph.Edge> = Queue()
/**
* Compute a minimum spanning tree (or forest) of an edge-weighted graph.
* @param G the edge-weighted graph
*/
init {
val pq = PriorityQueue<UWGraph.Edge>(G.V, compareBy({ it.weight }))
for (v in G.vertices()) {
for (e in G.adjacentEdges(v)) {
pq.add(e)
}
}
val set = DisjointSet(G.V)
while (!pq.isEmpty()) {
val edge = pq.poll()
if (!set.connected(edge.v, edge.w)) {
edges.add(edge)
set.union(edge.v, edge.w)
weight += edge.weight
}
}
}
override fun edges(): Iterable<UWGraph.Edge> {
return edges
}
override fun weight(): Double {
return weight
}
}
