Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm for finding a Minimum Spanning Tree (MST) of a connected, undirected, weighted graph.

The basic idea is:

Repeatedly choose the lightest edge that connects two different trees in the current forest.

If adding an edge would create a cycle, that edge is rejected.

🌳 1. Basic Idea

Initially, every vertex is considered as a separate tree.

For example:


A     B     C     D     E

We then examine all edges in increasing order of weight.

For each edge (u, v):

If u and v belong to different trees, add the edge.
If u and v already belong to the same tree, reject the edge because it would create a cycle.

Eventually, there will be:

|V| − 1 edges

and these edges form the MST.

🔑 2. Why is Kruskal's Algorithm Greedy?

At every step, Kruskal chooses:

The lowest-weight edge that can safely be added to the current forest.

Thus, it makes the best available choice at that moment.

The important point is that it proves that this choice is a safe edge, so the greedy strategy produces an MST.

🔗 3. Role of Disjoint Sets

Kruskal's algorithm uses the disjoint-set data structure that we discussed earlier.

Each set represents one tree in the current forest.

For example:


Set 1: {A, B, C}

Set 2: {D, E}

Set 3: {F}

To determine whether an edge (u, v) creates a cycle, we check:

FIND-SET(u)

and

FIND-SET(v)

If:

FIND-SET(u) = FIND-SET(v)

then u and v are already in the same tree.

Therefore, adding (u, v) creates a cycle.

❌ Reject the edge.

If:

FIND-SET(u) ≠ FIND-SET(v)

then u and v are in different trees.

Therefore, the edge can safely connect the two trees.

✅ Add the edge and perform UNION(u, v).

📝 4. Kruskal's Algorithm


MST-KRUSKAL(G, w)

1. A = ∅

2. For each vertex v ∈ G.V
       MAKE-SET(v)

3. Sort all edges in increasing order of weight

4. For each edge (u, v) in sorted order

       if FIND-SET(u) ≠ FIND-SET(v)

           A = A ∪ {(u, v)}

           UNION(u, v)

5. Return A

Here:

A = set of edges selected for the MST
MAKE-SET = creates a separate set for each vertex
FIND-SET = determines which tree contains a vertex
UNION = combines two trees

🔢 5. Simple Example

Consider the following weighted graph:


        4
   A -------- B
   |          |
  2|          |5
   |          |
   C -------- D
        3

Edges:

Edge	Weight
A-C	2
C-D	3
A-B	4
B-D	5

Step 1: Sort edges


A-C   2
C-D   3
A-B   4
B-D   5

Initially:


{A}   {B}   {C}   {D}

Step 2: Consider A-C

A and C are in different sets.


{A,C}   {B}   {D}

Add A-C.

Step 3: Consider C-D

C and D are in different sets.


{A,C,D}   {B}

Add C-D.

Step 4: Consider A-B

A and B are in different sets.


{A,B,C,D}

Add A-B.

We now have:

|V| − 1 = 4 − 1 = 3 edges

Therefore, we can stop.

The MST is:


        A -------- B
        |
       2|
        |
        C -------- D
             3

Total weight:

2 + 3 + 4 = 9

⚠️ 6. What Happens to an Edge That Creates a Cycle?

Consider the same graph, but suppose we have already selected:


A-C
C-D
A-B

Now consider:

B-D

Both B and D already belong to the same set:


{A, B, C, D}

Therefore:

FIND-SET(B) = FIND-SET(D)

So adding B-D would create:


A ---- B
|      |
C ---- D

which contains a cycle.

Therefore:

❌ Reject B-D.

This is exactly how the disjoint-set structure helps Kruskal's algorithm detect cycles efficiently.

⏱️ 7. Complexity Analysis

Let:

V = number of vertices
E = number of edges

CLRS analyzes the algorithm in three main parts.

Step 1: Initialize the disjoint sets

We perform:

V MAKE-SET operations

With the disjoint-set forest implementation, this takes:

O(V)

Step 2: Sort the edges

Kruskal first sorts all E edges according to their weights.

Sorting takes:

O(E log E)

This is the dominant operation in the standard implementation.

Step 3: FIND-SET and UNION

For every edge, Kruskal may perform:

one FIND-SET on u
one FIND-SET on v
possibly one UNION

Therefore, there are:

O(E)

disjoint-set operations.

Using union by rank + path compression, CLRS gives the total cost as:

O((V + E) α(V))

where α(V) is the extremely slowly growing inverse-Ackermann function.

For a connected graph:

E ≥ V − 1

Therefore this can be expressed as:

O(E α(V))

CLRS notes that this is smaller than the sorting cost.

⭐ 8. Overall Complexity

The major costs are:


Disjoint-set initialization       O(V)

Sorting edges                     O(E log E)

Disjoint-set operations           O(E α(V))

Therefore:

Total = O(V + E log E + E α(V))

The sorting term dominates, giving:

O(E log E)

Since:

E < V²

we have:

log E = O(log V)

Therefore CLRS expresses the final complexity as:

O(ElogV)

🎯 9. Kruskal's Algorithm in One Picture


             WEIGHTED GRAPH
                    │
                    ▼
          Sort all edges by weight
                    │
                    ▼
          Start with V separate sets
                    │
                    ▼
             Select smallest edge
                    │
             ┌──────┴──────┐
             │             │
       Different sets   Same set
             │             │
             ▼             ▼
          ADD EDGE       REJECT
             │          (cycle)
             ▼
           UNION
             │
             ▼
        Repeat until
          V − 1 edges
             │
             ▼
       MINIMUM SPANNING
             TREE

📌 Key Points

Kruskal is a greedy algorithm.
It starts with V individual trees.
It sorts edges in increasing order of weight.
It chooses the lightest safe edge.
Disjoint sets are used to detect whether an edge creates a cycle.
FIND-SET(u) == FIND-SET(v) → reject the edge.
FIND-SET(u) != FIND-SET(v) → add the edge and perform UNION.
The algorithm stops after selecting V − 1 edges.
Standard implementation complexity:

O(E log V)

The most important sentence to remember:

Kruskal's algorithm repeatedly adds the smallest-weight edge whose endpoints belong to different trees, thereby growing a forest into a minimum spanning tree without creating cycles.

Search This Blog

Design and Analysis of Algorithms PCCST502 Semester 5 KTU CS 2024 Scheme - Dr Binu V P