Kruskal’s algorithm

Kruskal’s algorithm is a greedy algorithm for finding the minimum spanning tree (MST) of a weighted undirected graph. The MST is a subset of the edges of the graph that form a tree connecting all vertices, with the minimum total edge weight.

The algorithm works as follows:

Sort all the edges in non-decreasing order of their weight. Create a new empty set of edges, initially containing no edges, which will eventually form the MST.

Iterate through the sorted edges in ascending order of weight:

a. If adding the current edge to the set of edges would not create a cycle, add it to the set.

b. If adding the current edge would create a cycle, skip it and move on to the next edge. Continue until all edges have been considered.

More specific

Sure, here are some additional details about Kruskal’s algorithm:

Kruskal’s algorithm is a greedy algorithm, meaning that it makes locally optimal choices at each step, hoping that these choices will lead to a globally optimal solution. In the case of finding the MST, the locally optimal choice is to add the minimum-weight edge that doesn’t create a cycle in the MST-so-far.

The algorithm can handle disconnected graphs, i.e., graphs that consist of multiple connected components. The resulting MST will be a forest, i.e., a set of trees, one for each connected component.

To sort the edges by weight, the algorithm can use any comparison-based sorting algorithm, such as quicksort or merge sort. The time complexity of sorting the edges is O(E log E).

The disjoint-set data structure used by Kruskal’s algorithm can be implemented using arrays or linked lists, with union-find operations taking O(log n) time in the worst case, where n is the number of vertices.

Kruskal’s algorithm is not the only algorithm for finding the MST of a graph. Other well-known algorithms include Prim’s algorithm and Boruvka’s algorithm. Prim’s algorithm is also a greedy algorithm, while Boruvka’s algorithm is a more complex algorithm that uses a divide-and-conquer approach.

Kruskal’s algorithm has many practical applications, such as designing efficient transportation networks, designing electrical power grids, and in image processing for finding a minimum-spanning forest.

To check for cycles, Kruskal’s algorithm uses the disjoint-set data structure, which can efficiently determine whether two vertices are in the same connected component (i.e., whether adding an edge between them would create a cycle). Once the algorithm has been completed, the resulting set of edges forms the MST of the graph.

Kruskal’s algorithm has a time complexity of O(E log E), where E is the number of edges in the graph. This makes it an efficient algorithm for finding the MST of large graphs.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        pi, pj = self.find(i), self.find(j)
        if pi == pj:
            return
        if self.rank[pi] < self.rank[pj]:
            self.parent[pi] = pj
        elif self.rank[pi] > self.rank[pj]:
            self.parent[pj] = pi
        else:
            self.parent[pj] = pi
            self.rank[pi] += 1


def kruskal(graph):
    n = len(graph)
    edges = [(graph[i][j], i, j) for i in range(n) for j in range(i+1, n)]
    edges.sort()
    uf = UnionFind(n)
    mst = []
    for weight, u, v in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v))
    return mst