Kruskal's Algorithm

@kruskals_algorithm

Kruskal's Algorithm finds a Minimum Spanning Tree (MST) by always picking the smallest edge that does not form a cycle, until all nodes are connected.

Pseudo-code
function kruskal(graph):

  # Step 1: Sort all edges by weight (smallest first)
  sort edges E by weight

  # Step 2: Initialize empty MST
  MST = empty set

  # Step 3: Create disjoint sets (each node is its own group)
  make_set for each vertex in V

  # Step 4: Process edges
  for each edge e(u, v) in sorted edges:

    # Check if adding edge forms a cycle
    if find(u) != find(v):

      # Safe to add edge
      MST.add(e)
      union(u, v)

  return MST
  • V The set of vertices (nodes) in the graph.
  • E The set of edges, each with a weight (cost).
  • e The current edge being checked from the sorted list.
  • MST The resulting tree that connects all nodes with minimum total cost.
  • infinity Represents a very large value, though not always directly needed in Kruskal.
Recipe Steps
1

List all connections — Imagine you have cities connected by roads with costs.

2

Sort by cheapest first — Arrange all roads from cheapest to most expensive.

3

Start building — Pick the cheapest road and add it.

4

Keep adding the next cheapest road, but skip it if it creates a loop.

5

Stop when all cities are connected. You now have the cheapest possible network.

Questions & Answers

To build a Minimum Spanning Tree with the smallest total edge weight.

So we always pick the smallest available edge first.

By checking if two nodes are already connected using a disjoint-set (union-find).

We skip it and move to the next edge.
- Time complexity is O(E log E) due to sorting edges.
- Uses Union-Find (Disjoint Set) for efficiency.
- Tip: Think of it as slowly building a network without creating loops.
- Common mistake: Forgetting cycle detection.
- Works best for sparse graphs (few edges).

Related Algorithms
Bellman-Ford Algorithm

The Bellman-Ford algorithm finds the shortest path from a source node to all other nodes, even when there are negative edge weights. It works by repeatedly improving distance estimates.

View
Dijkstra's Algorithm

Dijkstra's Algorithm finds the shortest path from one starting node to all other nodes in a graph by always expanding the currently closest node first.

View
Dinic's Algorithm

Dinic's Algorithm finds the maximum flow in a network by building layers using BFS and then sending flow using DFS in these layers, making it faster than simpler methods.

View