Minimum Spanning Trees

Kruskal

void kruskal(int size, int[][] connections) {
    Arrays.sort(connections, (a, b) -> a[2] - b[2]); // Sort by weight, non-decreasing
    UnionFind uf = new UnionFind(size);
    for (int[] connection : connections) { // Greedily select the smallest edges
      int u = connection[0], v = connection[1];
      if (!uf.isConnected(u, v)) { // Connect the nodes if they aren't already connected
        uf.union(u, v);
        if (uf.size == 1) break; // All nodes are connected
      }
    }
  }

• Greedily add edges ordered by their weights until all nodes belong to the same component (all are connected).

  • Hint: We can use Union-Find to check if all nodes are connected.

• Time: O(E log V)

Prim

• Prims works with an aribtrary node, and then always chooses the smallest edge that adds a new node. (Similar to Dijkstra, except Dijkstra selects to minimize weight from the start, not the current node).

• Uses a Priority Queue.

• Time: O(E + V log V)