Greedy Algorithms VTU BCSL40A

Kruskal's Algorithm

Kruskal's algorithm finds the Minimum Spanning Tree of a weighted graph by sorting edges and using union-find to avoid cycles.

Time Complexity

O(E log E)

Space Complexity

O(V)

Paradigm

Greedy Algorithms

Introduction

Kruskal's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected, weighted graph. Developed by Joseph Kruskal in 1956, it works by selecting the minimum weight edge at each step, ensuring no cycle is formed. It is widely used in network design, circuit design, and cluster analysis.

Problem Statement

Given a connected, undirected, weighted graph G = (V, E), find a spanning tree T such that the total weight of edges in T is minimized. A spanning tree connects all vertices with exactly V-1 edges and no cycles.

Real World Applications

→ Network cable layout — minimizing the amount of cable to connect all computers in a network
→ Road construction — finding the cheapest way to connect all cities
→ Electrical circuit design — minimizing wire length in printed circuit boards
→ Cluster analysis in machine learning
→ Water pipeline networks

Algorithm Explanation

Kruskal's algorithm sorts all edges in non-decreasing order of their weights. It then picks edges one by one, adding each to the spanning tree only if it does not form a cycle with already-selected edges. This cycle detection uses the Union-Find (Disjoint Set Union) data structure. The process continues until V-1 edges are selected.

Step-by-Step Procedure

1 Sort all edges in the graph in non-decreasing order of weight.
2 Initialize each vertex as its own component (root array).
3 Pick the smallest edge. Check if it forms a cycle using the root array.
4 If no cycle is formed, include the edge in the MST and union the two components.
5 If a cycle is formed, discard the edge.
6 Repeat steps 3-5 until V-1 edges are included in the MST.
7 Print all selected edges and the minimum cost.

Complete C Program

Kruskal_Algorithm.c

View on GitHub ↗

#include<stdio.h>
#include<stdlib.h>
#define MAX 10
#define INFI 99

int a[MAX][MAX], n, cost = 0;

void findmin(int *v1, int *v2) {
    int edge = INFI, i, j;
    for(i = 1; i <= n; i++) {
        for(j = i + 1; j <= n; j++) {
            if(a[i][j] > 0 && a[i][j] < edge) {
                edge = a[i][j];
                *v1 = i;
                *v2 = j;
            }
        }
    }
}

void update(int root[], int v1, int v2) {
    int temp, i;
    temp = root[v2];
    for(i = 1; i <= n; i++) {
        if(root[i] == temp)
            root[i] = root[v1];
    }
}

void kruskal() {
    int root[MAX], edge, i, v1, v2;
    for(i = 1; i <= n; i++)
        root[i] = i;
    i = 0;
    while(i != n - 1) {
        findmin(&v1, &v2);
        edge = a[v1][v2];
        a[v1][v2] = a[v2][v1] = 0;
        if(root[v1] != root[v2]) {
            printf("(%d, %d)\n", v1, v2);
            update(root, v1, v2);
            cost += edge;
            i++;
        }
    }
}

int main() {
    int i, j;
    printf("Enter the Number of Vertices: ");
    scanf("%d", &n);
    printf("Enter the Weighted Graph (adjacency matrix):\n");
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    printf("Edges of Spanning Tree:\n");
    kruskal();
    printf("\nMinimum Cost: %d\n", cost);
    return 0;
}

Sample Input & Output

Sample Input

Expected Output

Edges of Spanning Tree:
(3, 4)
(1, 4)
(1, 2)

Minimum Cost: 19

Dry Run / Trace

For a 4-vertex graph with edges: (1,2)=10, (1,3)=6, (1,4)=5, (2,4)=15, (3,4)=4

Step 1: Sort edges → (3,4)=4, (1,4)=5, (1,3)=6, (1,2)=10, (2,4)=15
Step 2: Pick (3,4)=4 → no cycle, add it. MST = {(3,4)}
Step 3: Pick (1,4)=5 → no cycle, add it. MST = {(3,4),(1,4)}
Step 4: Pick (1,3)=6 → cycle detected (1-4-3), skip.
Step 5: Pick (1,2)=10 → no cycle, add it. MST = {(3,4),(1,4),(1,2)}
Done! 3 = n-1 edges selected. Minimum Cost = 4+5+10 = 19

Advantages & Disadvantages

✓ Advantages

+ Simple and easy to implement
+ Works well for sparse graphs
+ Produces optimal (minimum) spanning tree
+ Can handle disconnected graphs (finds MST for each component)

✗ Disadvantages

− Requires sorting of all edges — O(E log E)
− Slower than Prim's algorithm for dense graphs
− Needs Union-Find structure for cycle detection

Viva Questions & Answers

Q1. What is the time complexity of Kruskal's algorithm?

O(E log E) due to sorting edges. The Union-Find operations are nearly O(1) with path compression.

Q2. How does Kruskal's algorithm detect cycles?

Using a root/parent array (Union-Find structure). If two vertices have the same root, adding the edge between them would create a cycle.

Q3. When is Kruskal's preferred over Prim's?

Kruskal's is preferred for sparse graphs (fewer edges), while Prim's is better for dense graphs.

Q4. What is a Minimum Spanning Tree?

A spanning tree of a weighted graph where the total weight of all edges is minimized. It contains exactly V-1 edges and connects all V vertices.

Q5. Can Kruskal's algorithm handle negative edge weights?

Yes, Kruskal's algorithm works correctly with negative edge weights as it only requires sorting.