Kruskal's algorithm

Kruskal's algorithm is a popular method used to find the minimum spanning tree (MST) for a connected, weighted, undirected graph. The goal of the algorithm is to find a subset of the graph's edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. This algorithm is categorized under greedy algorithms because it finds a local optimum with the hope that this leads to a global optimum.

Algorithm Workflow

1. Initialization:

   • Create a Union-Find data structure to manage connected components.
   • Sort all edges based on their weights in ascending order.

2. Iterate over Edges:

   • Start with an empty MST.
   • Traverse through the sorted edge list.
   • For each edge (u, v):
     • If u and v belong to different sets (i.e., adding the edge won't form a cycle), include this edge in the MST.
     • Union the sets containing u and v to indicate that they're now connected.
   • Stop once MST contains (V-1) edges, where V is the number of vertices.

3. Completion:

   • Return the MST and its total weight.

The algorithm uses the Union-Find data structure to detect cycles efficiently and to keep track of the vertices that are already included in the MST. The Union-Find algorithm helps in determining whether two vertices belong to the same subset or not, which in turn helps in checking if adding an edge creates a cycle in the MST.

Greedy Algorithm

Kruskal's Algorithm is classified as a greedy algorithm because at each step, it makes the locally optimal choice—it picks the edge with the lowest weight that doesn't create a cycle.

Pseudo Code

KRUSKAL(G):
  A = ∅
  foreach v ∈ G.V:
    MAKE-SET(v)
  foreach (u, v) ∈ G.E ordered by weight(u, v), increasing:
    if FIND-SET(u) ≠ FIND-SET(v):
      A = A ∪ {(u, v)}
      UNION(u, v)
  return A

Complexity

Time Complexity

• Sorting the edges takes $O(E \log E)$.
• Union-Find operations take nearly constant time due to path compression.

The time complexity of Kruskal's algorithm is $O(E \log E)$ or $O(E \log V)$, where $E$ is the number of edges and $V$ is the number of vertices in the graph. The dominant factor in this time complexity is the sorting of the edges based on their weights. Once the edges are sorted, the algorithm processes each edge in order, which takes $O(E)$ time, but the Union-Find operations (find and union) can be performed in nearly constant time, $O(\log V)$, for each edge due to path compression and union by rank optimizations.

Space Complexity

• $O(V + E)$ where $V$ and $E$ represent the number of vertices and edges, respectively.

Key Points

• Complexity: Time complexity is dominated by sorting edges, generally O (E log E) where E is the number of edges.
• Data Structures: Disjoint Sets (Union-Find) are helpful for cycle detection.

Implementation

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

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

    def apply_union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskal_algo(self):
        result = []
        i, e = 0, 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        rank = []
        for node in range(self.V):
            parent.append(node)
            rank.append(0)
        while e < self.V - 1:
            u, v, w = self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                e = e + 1
                result.append([u, v, w])
                self.apply_union(parent, rank, x, y)
        for u, v, weight in result:
            print("%d - %d: %d" % (u, v, weight))