MST Algorithm
The MST Kruskal Algorithm is an algorithm in graph theory that computes the minimum spanning tree (MST) of a connected, undirected graph. The algorithm was developed by Joseph Kruskal in 1956 and is widely used in network design, clustering, and other optimization problems. The main idea behind the algorithm is to iteratively add edges to the MST in increasing order of their weights, while ensuring that no cycles are formed. The end result is a tree that connects all vertices in the graph with the minimum possible total edge weight.
To execute the Kruskal Algorithm, the edges of the input graph are first sorted in non-decreasing order according to their weights. Then, the algorithm goes through the sorted edges and, for each edge, checks if the two vertices it connects have already been connected by the MST. If not, the edge is added to the MST, and the two vertices are considered connected. This process is repeated until all vertices are connected, or equivalently, when the MST has (n-1) edges, where n is the number of vertices in the graph. To efficiently check if two vertices are connected, a disjoint-set data structure, also known as a union-find data structure, is typically used. The algorithm's time complexity is O(E log E), where E is the number of edges in the graph, making it efficient for solving large-scale problems.
/*
* 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
interface MST {
/**
* Returns the edges in a minimum spanning tree (or forest).
* @return the edges in a minimum spanning tree (or forest) as
* * an iterable of edges
*/
fun edges(): Iterable<UWGraph.Edge>
/**
* Returns the sum of the edge weights in a minimum spanning tree (or forest).
* @return the sum of the edge weights in a minimum spanning tree (or forest)
*/
fun weight(): Double
}
