CS61B Guide
  • This site is now deprecated
  • Object Oriented Programming
    • Inheritance
    • Access Control
    • Dynamic Method Selection
    • Java Objects
    • Generic Types
  • Asymptotics
    • Asymptotic Analysis Basics
    • Amortization
    • Asymptotics Practice
  • Abstract Data Types
    • Collections
      • Arrays
      • Linked Lists
      • Sets
      • Stacks and Queues
    • Binary Trees
      • Heaps
      • Balanced BSTs
      • Tries
    • Graphs
    • Hashing and Hash Tables
    • Union Find (Disjoint Sets)
    • Comparables and Comparators
  • Sorting
    • Sorting
  • Algorithms
    • Minimax Algorithm
    • Searching
      • Binary Search
      • Depth First Search (DFS)
      • Breadth First Search (BFS)
    • Shortest Paths
      • Dijkstra's Algorithm
      • A* Search
    • Minimum Spanning Trees
      • Prim's Algorithm
      • Kruskal's Algorithm
  • Misc Topics
    • Modular Arithmetic and Bit Manipulation
    • Exceptions
    • More Resources
Powered by GitBook
On this page
  • Conceptual Overview
  • Detailed Breakdown
  • PseudoCode
  • Runtime Analysis

Was this helpful?

  1. Algorithms
  2. Minimum Spanning Trees

Kruskal's Algorithm

Special thanks to Arin for writing this page!

PreviousPrim's AlgorithmNextModular Arithmetic and Bit Manipulation

Last updated 5 years ago

Was this helpful?

Before reading, review and as they both make Kruskal's algorithm possible!

Conceptual Overview

Kruskal's algorithm is another optimal way to construct a minimum spanning tree. It's benefits are that it is conceptually very simple, and easy to implement. The idea is that first we sort all the edges of the graph in order of increasing weight. Then, add the smallest edge to the MST we are constructing unless this creates a cycle in the MST. Repeat until V - 1 edges total.

Detailed Breakdown

In order to optimally check if adding an edge to our MST creates a cycle, we will use a WeightedQuickUnion object. (See for a recap on what this is.) This is used because checking if a cycle exists using a WeightedUnionFind object boils down to one isConnected() call, which we know takes Θ(log⁡(N))\Theta(\log(N))Θ(log(N)).

To run the algorithm, we start by adding all the edges into a . This gives us our edges in sorted order. Now, we iterate through the PriorityQueue by removing the edge with highest priority, checking if adding it forms a cycle, and adding it to our MST if it doesn't form a cycle.

Let's see an example of Kruskal's Algorithm in action!

Here, we start with a simple graph and have sorted all of its edges into a priority queue.

Since the edge DE is the shortest, we'll add that to our UnionFind first. In the process, we'll remove DE from the priority queue.

We'll do the same thing with the next shortest path, DC.

Now, let's move on to AB. Notice that this time, connecting A and B creates another disjoint set! Unlike Prim's Algorithm, Kruskal's Algorithm does not guarantee that a solution will form a tree structure until the very end.

Now, let's connect BC.

Since CE and BD would both form cycles if connected, we are done 😄 Here's the final tree:

PseudoCode

public class Kruskals() {

    public Kruskals() {
        PQ edges = new PriorityQueue<>();
        ArrayList<Edge> mst = new ArrayList<>();
    }

    public void doKruskals(Graph G) {
        for (e : G.edges()) {
            PQ.add(e);
        }
        WeightedQU uf = new WeightedQU(G.V());
        Edge e = PQ.removeSmallest();
        int v = e.from();
        int w = e.to();
        if (!uf.isConnected(v, w)) {
            uf.union(v, w);
            mst.add(e);
        }

    }
}

Runtime Analysis

Left as an exercise to the reader 😉

Someone's been reading too much ... (The answer is Θ(Elog⁡(E))\Theta(E\log(E))Θ(Elog(E))by the way. Try to convince yourself why!)

LADR
Minimum Spanning Trees
Union Find (Disjoint Sets)
Union Find (Disjoint Sets)
PriorityQueue