Minimum spanning trees

Use a minimum spanning tree when the output must connect every vertex of an undirected weighted graph with minimum total edge cost. It is not a source-to-target shortest-path problem.

Recognition checklist

• Every vertex must be connected.
• Any connected tree with V vertices uses exactly V - 1 edges.
• The objective is the sum of selected edges, not a path distance.
• Edge weights may be zero or negative.
• If the graph is disconnected, decide whether the contract wants an error or a minimum spanning forest.

Kruskal or Prim?

Situation	Prefer	Owned operation
edges already form a sortable list	Kruskal	next globally cheapest edge
sparse graph and DSU is convenient	Kruskal	reject component-forming cycles
graph is naturally an adjacency list	Prim	next cheapest edge crossing the tree frontier
dense graph with cheap vertex scans	eager Prim	cheapest connection for each outside vertex

Both rely on the cut property: a minimum-weight edge crossing a cut is safe for some minimum spanning tree.

Kruskal thinking flow

1. Sort edges by increasing weight.
2. Let DSU represent the connected components formed by accepted edges.
3. Accept an edge only if its endpoints currently belong to different components.
4. Stop after accepting V - 1 edges.
5. If fewer edges were accepted, the graph was disconnected.

Invariant: accepted edges are a forest that can still be extended to an MST.

flowchart LR
  accTitle: Kruskal builds a minimum spanning tree by joining components
  accDescr: Sort the example edges by weight, accept the three edges that join different components, and reject later edges because all four vertices are already connected.
  S["Sorted edges<br/>AC 1 · BD 1 · BC 2 · AB 4 · CD 5"] --> A["Accept AC<br/>{A,C} {B} {D}"]
  A --> B["Accept BD, then BC<br/>{A,B,C,D}"]
  B --> C["Chosen edges<br/>AC 1 · BD 1 · BC 2"]
  C --> D["V-1 edges accepted<br/>MST cost = 4"]
  D -.-> E["AB and CD are skipped<br/>they would create cycles"]

At every accepted edge, read the braces as the DSU state. Kruskal never asks whether an edge is locally short on a path; it asks whether the cheapest remaining edge safely joins two whole components.

PythonC++17C++11

class DisjointSet:
    """Union-by-size disjoint set with path compression."""

    def __init__(self, size: int) -> None:
        if size < 0:
            raise ValueError("size must be nonnegative")
        self.parent = list(range(size))
        self.component_size = [1] * size

    def find(self, item: int) -> int:
        if not 0 <= item < len(self.parent):
            raise ValueError("item must be a valid set element")
        while self.parent[item] != item:
            # Point to the grandparent to shorten future find paths.
            self.parent[item] = self.parent[self.parent[item]]
            item = self.parent[item]
        return item

    def union(self, left: int, right: int) -> bool:
        left_root, right_root = self.find(left), self.find(right)
        if left_root == right_root:
            return False
        # Attach the smaller tree below the larger tree.
        if self.component_size[left_root] < self.component_size[right_root]:
            left_root, right_root = right_root, left_root
        self.parent[right_root] = left_root
        self.component_size[left_root] += self.component_size[right_root]
        return True
def minimum_spanning_tree_weight(
    vertex_count: int, edges: Sequence[tuple[int, int, int]]
) -> int:
    """Return an MST weight or raise when the undirected graph is disconnected."""
    if vertex_count < 0:
        raise ValueError("vertex_count must be nonnegative")
    for left, right, _weight in edges:
        if not 0 <= left < vertex_count or not 0 <= right < vertex_count:
            raise ValueError("edge endpoint must be a valid vertex")

    groups = DisjointSet(vertex_count)
    total = 0
    accepted = 0
    # The cheapest safe edge is justified by the MST cut property.
    for left, right, weight in sorted(edges, key=lambda edge: edge[2]):
        if groups.union(left, right):
            total += weight
            accepted += 1

    required = max(0, vertex_count - 1)
    if accepted != required:
        raise ValueError("undirected graph is disconnected")
    return total

class DisjointSet {
 public:
  explicit DisjointSet(int size)
      : parent_(checked_size(size)), component_size_(checked_size(size), 1) {
    for (int index = 0; index < size; ++index) {
      parent_[index] = index;
    }
  }

  int find(int item) {
    if (item < 0 || static_cast<std::size_t>(item) >= parent_.size()) {
      throw std::invalid_argument("item must be a valid set element");
    }
    while (parent_[item] != item) {
      // Point to the grandparent to shorten future find paths.
      parent_[item] = parent_[parent_[item]];
      item = parent_[item];
    }
    return item;
  }

  bool unite(int left, int right) {
    left = find(left);
    right = find(right);
    if (left == right) {
      return false;
    }
    // Attach the smaller tree below the larger tree.
    if (component_size_[left] < component_size_[right]) {
      std::swap(left, right);
    }
    parent_[right] = left;
    component_size_[left] += component_size_[right];
    return true;
  }

 private:
  static std::size_t checked_size(int size) {
    if (size < 0) {
      throw std::invalid_argument("size must be nonnegative");
    }
    return static_cast<std::size_t>(size);
  }

  std::vector<int> parent_;
  std::vector<int> component_size_;
};
inline long long minimum_spanning_tree_weight(
    int vertex_count,
    const std::vector<std::tuple<int, int, long long>>& edges) {
  if (vertex_count < 0) {
    throw std::invalid_argument("vertex_count must be nonnegative");
  }
  for (const auto& edge : edges) {
    const int left = std::get<0>(edge);
    const int right = std::get<1>(edge);
    const long long weight = std::get<2>(edge);
    static_cast<void>(weight);
    if (left < 0 || right < 0 || left >= vertex_count ||
        right >= vertex_count) {
      throw std::invalid_argument("edge endpoint must be a valid vertex");
    }
  }

  auto ordered = edges;
  std::sort(ordered.begin(), ordered.end(),
            [](const std::tuple<int, int, long long>& left,
               const std::tuple<int, int, long long>& right) {
              return std::get<2>(left) < std::get<2>(right);
            });

  DisjointSet groups(vertex_count);
  long long total = 0;
  int accepted = 0;
  // The cheapest safe edge is justified by the MST cut property.
  for (const auto& edge : ordered) {
    const int left = std::get<0>(edge);
    const int right = std::get<1>(edge);
    const long long weight = std::get<2>(edge);
    if (groups.unite(left, right)) {
      if ((weight > 0 &&
           total > std::numeric_limits<long long>::max() - weight) ||
          (weight < 0 &&
           total < std::numeric_limits<long long>::min() - weight)) {
        throw std::overflow_error("minimum spanning-tree weight overflow");
      }
      total += weight;
      ++accepted;
    }
  }

  const int required = std::max(0, vertex_count - 1);
  if (accepted != required) {
    throw std::invalid_argument("undirected graph is disconnected");
  }
  return total;
}

class DisjointSet {
 public:
  explicit DisjointSet(int size)
      : parent_(checked_size(size)), component_size_(checked_size(size), 1) {
    for (int index = 0; index < size; ++index) {
      parent_[index] = index;
    }
  }

  int find(int item) {
    if (item < 0 || static_cast<std::size_t>(item) >= parent_.size()) {
      throw std::invalid_argument("item must be a valid set element");
    }
    while (parent_[item] != item) {
      // Point to the grandparent to shorten future find paths.
      parent_[item] = parent_[parent_[item]];
      item = parent_[item];
    }
    return item;
  }

  bool unite(int left, int right) {
    left = find(left);
    right = find(right);
    if (left == right) {
      return false;
    }
    // Attach the smaller tree below the larger tree.
    if (component_size_[left] < component_size_[right]) {
      std::swap(left, right);
    }
    parent_[right] = left;
    component_size_[left] += component_size_[right];
    return true;
  }

 private:
  static std::size_t checked_size(int size) {
    if (size < 0) {
      throw std::invalid_argument("size must be nonnegative");
    }
    return static_cast<std::size_t>(size);
  }

  std::vector<int> parent_;
  std::vector<int> component_size_;
};
inline long long minimum_spanning_tree_weight(
    int vertex_count,
    const std::vector<std::tuple<int, int, long long>>& edges) {
  if (vertex_count < 0) {
    throw std::invalid_argument("vertex_count must be nonnegative");
  }
  for (const auto& edge : edges) {
    const int left = std::get<0>(edge);
    const int right = std::get<1>(edge);
    const long long weight = std::get<2>(edge);
    static_cast<void>(weight);
    if (left < 0 || right < 0 || left >= vertex_count ||
        right >= vertex_count) {
      throw std::invalid_argument("edge endpoint must be a valid vertex");
    }
  }

  auto ordered = edges;
  std::sort(ordered.begin(), ordered.end(),
            [](const std::tuple<int, int, long long>& left,
               const std::tuple<int, int, long long>& right) {
              return std::get<2>(left) < std::get<2>(right);
            });

  DisjointSet groups(vertex_count);
  long long total = 0;
  int accepted = 0;
  // The cheapest safe edge is justified by the MST cut property.
  for (const auto& edge : ordered) {
    const int left = std::get<0>(edge);
    const int right = std::get<1>(edge);
    const long long weight = std::get<2>(edge);
    if (groups.unite(left, right)) {
      if ((weight > 0 &&
           total > std::numeric_limits<long long>::max() - weight) ||
          (weight < 0 &&
           total < std::numeric_limits<long long>::min() - weight)) {
        throw std::overflow_error("minimum spanning-tree weight overflow");
      }
      total += weight;
      ++accepted;
    }
  }

  const int required = std::max(0, vertex_count - 1);
  if (accepted != required) {
    throw std::invalid_argument("undirected graph is disconnected");
  }
  return total;
}

Worked example

For edges (A,C,1), (B,D,1), (B,C,2), (A,B,4), (C,D,5):

1. accept A-C;
2. accept B-D;
3. accept B-C, which joins the two components;
4. stop at three edges for four vertices.

The total is 4. The later edges are unnecessary even though they are valid connections.

Complexity and traps

• Kruskal: O(E log E) sorting plus near-constant amortized DSU operations.
• Heap-based Prim: O(E log V).
• Do not require distinct weights; multiple MSTs may exist with the same total.
• Do not reject negative weights.
• Do not return a partial total as though it were a spanning tree.
• In C++, guard the accumulated weight from overflow.

Practice and reference

• Princeton: Minimum Spanning Trees
• LeetCode: Min Cost to Connect All Points