🪓 Kruskal

This page provides introduction to Kruskal Algorithm.

Overview

Kruskal's algorithm is a minimum spanning tree (MST) algorithm. It finds a subgraph with $\text{n} - 1$ edges, in which all vertices are connected. A minimum spanning tree is a tree in which the sum of the edge weights is minimized.

Run Krushkal

Let's apply the Kruskal's algorithm to the directed graph shown below to find minimum spanning tree.

We begin with sorting edges by weights in ascending order. Here we are using the Union Find algorithm to determine whether two vertices are already connected.

Now, we iterate over the edges and add an edge to the MST if adding it does not connect already connected components. Let's start with the first edge, $\text{AD}$. Adding this edge to the MST does not connect already connected components, so we include it in the MST.

info

Edges that are part of the MST are marked in green.

Similarly, let's iterate over the remaining edges and add them to the MST if they do not connect already connected nodes.

Applying algorithm to edge $\text{BC}$.

Applying algorithm to edge $\text{CD}$.

Applying algorithm to edge $\text{EF}$.

Applying algorithm to edge $\text{AB}$.

Applying algorithm to edge $\text{BD}$.

Applying algorithm to edge $\text{CF}$.

Applying algorithm to edge $\text{CE}$.

Applying algorithm to edge $\text{DE}$.

The final MST looks as follows:

Java

class Edge {
  char src;
  char dest;
  int distance;

  Edge(char src, char dest, int distance) {
    this.src = src;
    this.dest = dest;
    this.distance = distance;
  }

  @Override
  public int compareTo(Edge other) {
    return Integer.compare(this.weight, other.weight);
  }
}

public List<Edge> kruskal(int nodes, List<Edge> graph) {
  // sorting edges by weight
  Collections.sort(graph);

  // union find parent arr
  int[] parentArr = new int[nodes];

  List<Edge> mst = new ArrayList<>();
  for(Edge e: graph) {
    int from = e.src - 'A';
    int to = e.dest - 'A';
    // check connected
    if(!isConnected(from, to, parentArr)) {
      mst.add(new Edge(e.src, e.dest, e.weight));
    }
  }

  private boolean isConnected(int from, int to, int[] parentArr) {
    int fromParent = find(from, parentArr);
    int toParent = find(to, parentArr);
    
    if(fromParent == toParent) return true;
    else {
      parentArr[fromParent] = toParent;
      return false;
    }
  }

  private int find(int node, int[] parentArr) {
    if(parentArr[node] == node) return node;
    int parent = parentArr[node];
    return parentArr[parent] = find(parent, parentArr);
  }
}

Complexity

Let's say there are $\text{N}$ nodes and $\text{E}$ edges in a graph.

Time Complexity

• Sorting the edges by weight takes $\text{O(E log E)}$ time.
• Initializing the Disjoint Set for $\text{V}$ vertices takes $\text{O(V)}$ time.
• Processing each edge involves find() and union() operations, both of which run in $\text{O(log V)}$ time, and since we process at most $\text{E}$ edges, this step contributes $\text{O(E log V)}$ to the complexity.

Thus, the overall time complexity is:

$$\text{O(E log E)} + \text{O(E log V)}$$

info

Since in a connected graph, $\text{E}$ is at most $\text{O}(\text{V}^{2})$ for a complete graph, the worst case time complexity becomes $\text{O}(\text{V}^{2} \text{log V})$.

Space Complexity

The space complexity of Kruskal’s algorithm includes

• $\text{O(E)}$ for storing the edge list.
• $\text{O(V)}$ for union and find parent array.
• $\text{O(V)}$ for storing the minimum spanning Tree (MST).

Thus, the overall space complexity is:

$$\text{O(E + V)}$$

info

This makes Kruskal’s algorithm well suited for sparse graphs where $\text{E} \approx \text{V}$, but for dense graphs $(\text{E} \approx \text{V}{2})$ prim’s algorithm may be more efficient.