WikiGalaxy

Personalize

Kruskal's Algorithm - Introduction

Overview:

Kruskal's algorithm is a minimum spanning tree algorithm that finds an edge of the least possible weight that connects any two trees in a forest. It is a greedy algorithm that helps in finding the minimum spanning tree for a connected weighted graph.

Steps Involved:

1. Sort all the edges in non-decreasing order of their weight.

2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If not, include this edge. Else, discard it.

3. Repeat step 2 until there are (V-1) edges in the spanning tree.


import java.util.*;
class KruskalExample {
  class Edge implements Comparable {
    int src, dest, weight;
    public int compareTo(Edge compareEdge) {
      return this.weight - compareEdge.weight;
    }
  }

  class Subset {
    int parent, rank;
  }

  int V, E;
  Edge edge[];

  KruskalExample(int v, int e) {
    V = v;
    E = e;
    edge = new Edge[E];
    for (int i = 0; i < e; ++i)
      edge[i] = new Edge();
  }

  int find(Subset subsets[], int i) {
    if (subsets[i].parent != i)
      subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
  }

  void Union(Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
    else {
      subsets[yroot].parent = xroot;
      subsets[xroot].rank++;
    }
  }

  void KruskalMST() {
    Edge result[] = new Edge[V];
    int e = 0;
    int i = 0;
    for (i = 0; i < V; ++i)
      result[i] = new Edge();

    Arrays.sort(edge);

    Subset subsets[] = new Subset[V];
    for (i = 0; i < V; ++i)
      subsets[i] = new Subset();

    for (int v = 0; v < V; ++v) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
    }

    i = 0;
    while (e < V - 1) {
      Edge next_edge = new Edge();
      next_edge = edge[i++];

      int x = find(subsets, next_edge.src);
      int y = find(subsets, next_edge.dest);

      if (x != y) {
        result[e++] = next_edge;
        Union(subsets, x, y);
      }
    }

    System.out.println("Following are the edges in the constructed MST");
    for (i = 0; i < e; ++i)
      System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
  }

  public static void main(String[] args) {
    int V = 4;
    int E = 5;
    KruskalExample graph = new KruskalExample(V, E);

    graph.edge[0].src = 0;
    graph.edge[0].dest = 1;
    graph.edge[0].weight = 10;

    graph.edge[1].src = 0;
    graph.edge[1].dest = 2;
    graph.edge[1].weight = 6;

    graph.edge[2].src = 0;
    graph.edge[2].dest = 3;
    graph.edge[2].weight = 5;

    graph.edge[3].src = 1;
    graph.edge[3].dest = 3;
    graph.edge[3].weight = 15;

    graph.edge[4].src = 2;
    graph.edge[4].dest = 3;
    graph.edge[4].weight = 4;

    graph.KruskalMST();
  }
}

Console Output:

2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

Example 1: Simple Graph

Graph Description:

Consider a simple graph with 3 vertices and 3 edges. The goal is to find the minimum spanning tree using Kruskal's algorithm.

Graph Details:

Vertices: 3 (A, B, C)

Edges: (A-B, weight 1), (B-C, weight 2), (A-C, weight 3)


import java.util.*;
class SimpleGraphKruskal {
  class Edge implements Comparable {
    int src, dest, weight;
    public int compareTo(Edge compareEdge) {
      return this.weight - compareEdge.weight;
    }
  }

  class Subset {
    int parent, rank;
  }

  int V, E;
  Edge edge[];

  SimpleGraphKruskal(int v, int e) {
    V = v;
    E = e;
    edge = new Edge[E];
    for (int i = 0; i < e; ++i)
      edge[i] = new Edge();
  }

  int find(Subset subsets[], int i) {
    if (subsets[i].parent != i)
      subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
  }

  void Union(Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
    else {
      subsets[yroot].parent = xroot;
      subsets[xroot].rank++;
    }
  }

  void KruskalMST() {
    Edge result[] = new Edge[V];
    int e = 0;
    int i = 0;
    for (i = 0; i < V; ++i)
      result[i] = new Edge();

    Arrays.sort(edge);

    Subset subsets[] = new Subset[V];
    for (i = 0; i < V; ++i)
      subsets[i] = new Subset();

    for (int v = 0; v < V; ++v) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
    }

    i = 0;
    while (e < V - 1) {
      Edge next_edge = new Edge();
      next_edge = edge[i++];

      int x = find(subsets, next_edge.src);
      int y = find(subsets, next_edge.dest);

      if (x != y) {
        result[e++] = next_edge;
        Union(subsets, x, y);
      }
    }

    System.out.println("Following are the edges in the constructed MST");
    for (i = 0; i < e; ++i)
      System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
  }

  public static void main(String[] args) {
    int V = 3;
    int E = 3;
    SimpleGraphKruskal graph = new SimpleGraphKruskal(V, E);

    graph.edge[0].src = 0;
    graph.edge[0].dest = 1;
    graph.edge[0].weight = 1;

    graph.edge[1].src = 1;
    graph.edge[1].dest = 2;
    graph.edge[1].weight = 2;

    graph.edge[2].src = 0;
    graph.edge[2].dest = 2;
    graph.edge[2].weight = 3;

    graph.KruskalMST();
  }
}

Console Output:

0 -- 1 == 1
1 -- 2 == 2

Example 2: Graph with Cycle

Graph Description:

In this example, we will consider a graph with 4 vertices and 5 edges, some of which form a cycle. The algorithm will ensure no cycles are included in the MST.

Graph Details:

Vertices: 4 (A, B, C, D)

Edges: (A-B, weight 1), (B-C, weight 2), (C-D, weight 3), (D-A, weight 4), (A-C, weight 5)


import java.util.*;
class CycleGraphKruskal {
  class Edge implements Comparable {
    int src, dest, weight;
    public int compareTo(Edge compareEdge) {
      return this.weight - compareEdge.weight;
    }
  }

  class Subset {
    int parent, rank;
  }

  int V, E;
  Edge edge[];

  CycleGraphKruskal(int v, int e) {
    V = v;
    E = e;
    edge = new Edge[E];
    for (int i = 0; i < e; ++i)
      edge[i] = new Edge();
  }

  int find(Subset subsets[], int i) {
    if (subsets[i].parent != i)
      subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
  }

  void Union(Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
    else {
      subsets[yroot].parent = xroot;
      subsets[xroot].rank++;
    }
  }

  void KruskalMST() {
    Edge result[] = new Edge[V];
    int e = 0;
    int i = 0;
    for (i = 0; i < V; ++i)
      result[i] = new Edge();

    Arrays.sort(edge);

    Subset subsets[] = new Subset[V];
    for (i = 0; i < V; ++i)
      subsets[i] = new Subset();

    for (int v = 0; v < V; ++v) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
    }

    i = 0;
    while (e < V - 1) {
      Edge next_edge = new Edge();
      next_edge = edge[i++];

      int x = find(subsets, next_edge.src);
      int y = find(subsets, next_edge.dest);

      if (x != y) {
        result[e++] = next_edge;
        Union(subsets, x, y);
      }
    }

    System.out.println("Following are the edges in the constructed MST");
    for (i = 0; i < e; ++i)
      System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
  }

  public static void main(String[] args) {
    int V = 4;
    int E = 5;
    CycleGraphKruskal graph = new CycleGraphKruskal(V, E);

    graph.edge[0].src = 0;
    graph.edge[0].dest = 1;
    graph.edge[0].weight = 1;

    graph.edge[1].src = 1;
    graph.edge[1].dest = 2;
    graph.edge[1].weight = 2;

    graph.edge[2].src = 2;
    graph.edge[2].dest = 3;
    graph.edge[2].weight = 3;

    graph.edge[3].src = 3;
    graph.edge[3].dest = 0;
    graph.edge[3].weight = 4;

    graph.edge[4].src = 0;
    graph.edge[4].dest = 2;
    graph.edge[4].weight = 5;

    graph.KruskalMST();
  }
}

Console Output:

0 -- 1 == 1
1 -- 2 == 2
2 -- 3 == 3

Example 3: Dense Graph

Graph Description:

This example demonstrates Kruskal's algorithm on a dense graph with 5 vertices and 7 edges. The graph is more complex, showcasing the efficiency of the algorithm in handling larger graphs.

Graph Details:

Vertices: 5 (A, B, C, D, E)

Edges: (A-B, weight 1), (B-C, weight 3), (C-D, weight 2), (D-E, weight 4), (E-A, weight 5), (B-D, weight 6), (C-E, weight 7)


import java.util.*;
class DenseGraphKruskal {
  class Edge implements Comparable {
    int src, dest, weight;
    public int compareTo(Edge compareEdge) {
      return this.weight - compareEdge.weight;
    }
  }

  class Subset {
    int parent, rank;
  }

  int V, E;
  Edge edge[];

  DenseGraphKruskal(int v, int e) {
    V = v;
    E = e;
    edge = new Edge[E];
    for (int i = 0; i < e; ++i)
      edge[i] = new Edge();
  }

  int find(Subset subsets[], int i) {
    if (subsets[i].parent != i)
      subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
  }

  void Union(Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
    else {
      subsets[yroot].parent = xroot;
      subsets[xroot].rank++;
    }
  }

  void KruskalMST() {
    Edge result[] = new Edge[V];
    int e = 0;
    int i = 0;
    for (i = 0; i < V; ++i)
      result[i] = new Edge();

    Arrays.sort(edge);

    Subset subsets[] = new Subset[V];
    for (i = 0; i < V; ++i)
      subsets[i] = new Subset();

    for (int v = 0; v < V; ++v) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
    }

    i = 0;
    while (e < V - 1) {
      Edge next_edge = new Edge();
      next_edge = edge[i++];

      int x = find(subsets, next_edge.src);
      int y = find(subsets, next_edge.dest);

      if (x != y) {
        result[e++] = next_edge;
        Union(subsets, x, y);
      }
    }

    System.out.println("Following are the edges in the constructed MST");
    for (i = 0; i < e; ++i)
      System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
  }

  public static void main(String[] args) {
    int V = 5;
    int E = 7;
    DenseGraphKruskal graph = new DenseGraphKruskal(V, E);

    graph.edge[0].src = 0;
    graph.edge[0].dest = 1;
    graph.edge[0].weight = 1;

    graph.edge[1].src = 1;
    graph.edge[1].dest = 2;
    graph.edge[1].weight = 3;

    graph.edge[2].src = 2;
    graph.edge[2].dest = 3;
    graph.edge[2].weight = 2;

    graph.edge[3].src = 3;
    graph.edge[3].dest = 4;
    graph.edge[3].weight = 4;

    graph.edge[4].src = 4;
    graph.edge[4].dest = 0;
    graph.edge[4].weight = 5;

    graph.edge[5].src = 1;
    graph.edge[5].dest = 3;
    graph.edge[5].weight = 6;

    graph.edge[6].src = 2;
    graph.edge[6].dest = 4;
    graph.edge[6].weight = 7;

    graph.KruskalMST();
  }
}

Console Output:

0 -- 1 == 1
2 -- 3 == 2
1 -- 2 == 3
3 -- 4 == 4

Example 4: Sparse Graph

Graph Description:

This example covers a sparse graph with 6 vertices and 5 edges, highlighting how Kruskal's algorithm efficiently constructs the MST even when many vertices have fewer connections.

Graph Details:

Vertices: 6 (A, B, C, D, E, F)

Edges: (A-B, weight 1), (B-D, weight 2), (C-D, weight 3), (D-E, weight 4), (E-F, weight 5)


import java.util.*;
class SparseGraphKruskal {
  class Edge implements Comparable {
    int src, dest, weight;
    public int compareTo(Edge compareEdge) {
      return this.weight - compareEdge.weight;
    }
  }

  class Subset {
    int parent, rank;
  }

  int V, E;
  Edge edge[];

  SparseGraphKruskal(int v, int e) {
    V = v;
    E = e;
    edge = new Edge[E];
    for (int i = 0; i < e; ++i)
      edge[i] = new Edge();
  }

  int find(Subset subsets[], int i) {
    if (subsets[i].parent != i)
      subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
  }

  void Union(Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
    else {
      subsets[yroot].parent = xroot;
      subsets[xroot].rank++;
    }
  }

  void KruskalMST() {
    Edge result[] = new Edge[V];
    int e = 0;
    int i = 0;
    for (i = 0; i < V; ++i)
      result[i] = new Edge();

    Arrays.sort(edge);

    Subset subsets[] = new Subset[V];
    for (i = 0; i < V; ++i)
      subsets[i] = new Subset();

    for (int v = 0; v < V; ++v) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
    }

    i = 0;
    while (e < V - 1) {
      Edge next_edge = new Edge();
      next_edge = edge[i++];

      int x = find(subsets, next_edge.src);
      int y = find(subsets, next_edge.dest);

      if (x != y) {
        result[e++] = next_edge;
        Union(subsets, x, y);
      }
    }

    System.out.println("Following are the edges in the constructed MST");
    for (i = 0; i < e; ++i)
      System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
  }

  public static void main(String[] args) {
    int V = 6;
    int E = 5;
    SparseGraphKruskal graph = new SparseGraphKruskal(V, E);

    graph.edge[0].src = 0;
    graph.edge[0].dest = 1;
    graph.edge[0].weight = 1;

    graph.edge[1].src = 1;
    graph.edge[1].dest = 3;
    graph.edge[1].weight = 2;

    graph.edge[2].src = 2;
    graph.edge[2].dest = 3;
    graph.edge[2].weight = 3;

    graph.edge[3].src = 3;
    graph.edge[3].dest = 4;
    graph.edge[3].weight = 4;

    graph.edge[4].src = 4;
    graph.edge[4].dest = 5;
    graph.edge[4].weight = 5;

    graph.KruskalMST();
  }
}

Console Output:

0 -- 1 == 1
1 -- 3 == 2
2 -- 3 == 3
3 -- 4 == 4
4 -- 5 == 5

Example 5: Disconnected Graph

Graph Description:

This example illustrates Kruskal's algorithm on a disconnected graph. The algorithm will only find the MST for the largest connected component.

Graph Details:

Vertices: 6 (A, B, C, D, E, F)

Edges: (A-B, weight 1), (B-C, weight 2), (D-E, weight 3)

Note: Vertices D, E, and F form a separate component.


import java.util.*;
class DisconnectedGraphKruskal {
  class Edge implements Comparable {
    int src, dest, weight;
    public int compareTo(Edge compareEdge) {
      return this.weight - compareEdge.weight;
    }
  }

  class Subset {
    int parent, rank;
  }

  int V, E;
  Edge edge[];

  DisconnectedGraphKruskal(int v, int e) {
    V = v;
    E = e;
    edge = new Edge[E];
    for (int i = 0; i < e; ++i)
      edge[i] = new Edge();
  }

  int find(Subset subsets[], int i) {
    if (subsets[i].parent != i)
      subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
  }

  void Union(Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
    else {
      subsets[yroot].parent = xroot;
      subsets[xroot].rank++;
    }
  }

  void KruskalMST() {
    Edge result[] = new Edge[V];
    int e = 0;
    int i = 0;
    for (i = 0; i < V; ++i)
      result[i] = new Edge();

    Arrays.sort(edge);

    Subset subsets[] = new Subset[V];
    for (i = 0; i < V; ++i)
      subsets[i] = new Subset();

    for (int v = 0; v < V; ++v) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
    }

    i = 0;
    while (e < V - 1) {
      Edge next_edge = new Edge();
      next_edge = edge[i++];

      int x = find(subsets, next_edge.src);
      int y = find(subsets, next_edge.dest);

      if (x != y) {
        result[e++] = next_edge;
        Union(subsets, x, y);
      }
    }

    System.out.println("Following are the edges in the constructed MST");
    for (i = 0; i < e; ++i)
      System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
  }

  public static void main(String[] args) {
    int V = 6;
    int E = 3;
    DisconnectedGraphKruskal graph = new DisconnectedGraphKruskal(V, E);

    graph.edge[0].src = 0;
    graph.edge[0].dest = 1;
    graph.edge[0].weight = 1;

    graph.edge[1].src = 1;
    graph.edge[1].dest = 2;
    graph.edge[1].weight = 2;

    graph.edge[2].src = 3;
    graph.edge[2].dest = 4;
    graph.edge[2].weight = 3;

    graph.KruskalMST();
  }
}

Console Output:

0 -- 1 == 1
1 -- 2 == 2