Kruskal’s Algorithm is a greedy algorithm used to find the minimum spanning tree of a weighted undirected graph. It works by sorting the edges of the graph in increasing order of weight and adding them to the tree one by one, provided that the edge does not create a cycle in the tree. The algorithm maintains a disjoint set data structure to keep track of the connected components of the tree and to check for cycles. Kruskal’s Algorithm is often used in network design, transportation planning, and other optimization problems. It has a time complexity of O(E log E) where E is the number of edges in the graph.
class Edge(val src: Int, val dest: Int, val weight: Int)The given Kotlin code implements Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph. The algorithm works by sorting the edges of the graph in non-decreasing order of their weights and then iteratively adding edges to the minimum spanning tree as long as they do not create a cycle.
fun kruskal(graph: List<Edge>, numVertices: Int): List<Edge> {
val sortedEdges = graph.sortedBy { it.weight }
val disjointSet = IntArray(numVertices) { -1 }
val mst = mutableListOf<Edge>()
fun find(parents: IntArray, i: Int): Int {
if (parents[i] < 0) return i
return find(parents, parents[i]).also { parents[i] = it }
}
fun union(parents: IntArray, i: Int, j: Int) {
val root1 = find(parents, i)
val root2 = find(parents, j)
if (root1 != root2) {
if (parents[root1] < parents[root2]) {
parents[root1] += parents[root2]
parents[root2] = root1
} else {
parents[root2] += parents[root1]
parents[root1] = root2
}
}
}
for (edge in sortedEdges) {
if (mst.size >= numVertices - 1) break
if (find(disjointSet, edge.src) != find(disjointSet, edge.dest)) {
union(disjointSet, edge.src, edge.dest)
mst.add(edge)
}
}
return mst
}The kruskal function takes a list of edges graph and the number of vertices numVertices as input and returns a list of edges that form the minimum spanning tree. It first sorts the edges of the graph in non-decreasing order of their weights using the sortedBy function. Then, it initializes a disjoint set data structure represented by an integer array disjointSet and a list mst to store the minimum spanning tree.
The function find implements the find operation of the disjoint set data structure, which recursively finds the representative element of the set to which an element belongs. The union function implements the union operation of the disjoint set data structure, which merges two sets if they are not already in the same set.
The function then iterates through the sorted edges and adds an edge to the minimum spanning tree if it does not create a cycle, using the find and union functions to check and merge sets respectively. Finally, the function returns the list of edges in the minimum spanning tree.
class Edge(val src: Int, val dest: Int, val weight: Int)
fun kruskal(graph: List<Edge>, numVertices: Int): List<Edge> {
val sortedEdges = graph.sortedBy { it.weight }
val disjointSet = IntArray(numVertices) { -1 }
val mst = mutableListOf<Edge>()
fun find(parents: IntArray, i: Int): Int {
if (parents[i] < 0) return i
return find(parents, parents[i]).also { parents[i] = it }
}
fun union(parents: IntArray, i: Int, j: Int) {
val root1 = find(parents, i)
val root2 = find(parents, j)
if (root1 != root2) {
if (parents[root1] < parents[root2]) {
parents[root1] += parents[root2]
parents[root2] = root1
} else {
parents[root2] += parents[root1]
parents[root1] = root2
}
}
}
for (edge in sortedEdges) {
if (mst.size >= numVertices - 1) break
if (find(disjointSet, edge.src) != find(disjointSet, edge.dest)) {
union(disjointSet, edge.src, edge.dest)
mst.add(edge)
}
}
return mst
}
fun main() {
val graph = listOf(
Edge(0, 1, 4),
Edge(0, 7, 8),
Edge(1, 2, 8),
Edge(1, 7, 11),
Edge(2, 3, 7),
Edge(2, 8, 2),
Edge(2, 5, 4),
Edge(3, 4, 9),
Edge(3, 5, 14),
Edge(4, 5, 10),
Edge(5, 6, 2),
Edge(6, 7, 1),
Edge(6, 8, 6),
Edge(7, 8, 7)
)
val mst = kruskal(graph, 9)
println("Minimum Spanning Tree:")
for (edge in mst) {
println("${edge.src} --(${edge.weight})-- ${edge.dest}")
}
}The main function creates a graph represented by a list of edges and calls the kruskal function to find the minimum spanning tree. It then prints the edges of the minimum spanning tree along with their weights.