Chapter 10 · Advanced graphs

Advanced graph selection starts with the result that must be proved.

Objective	Key condition	Candidate
connect all vertices cheaply	undirected weighted graph	Kruskal / Prim MST
move maximum amount	capacities	max flow
shortest paths with negative edges	reachable negative cycles matter	Bellman–Ford
all-pairs paths, small V	dense or repeated queries	Floyd–Warshall
mutual reachability groups	directed graph	SCC
critical undirected links	connectivity after removal	bridge / articulation DFS
repeated ancestor queries	static rooted tree	LCA with binary lifting
one target with a useful lower bound	nonnegative costs	A* heuristic search

flowchart TD
  accTitle: Choosing an advanced graph algorithm by the result to prove
  accDescr: Choose minimum spanning tree algorithms to connect all vertices cheaply, max flow to maximize movement through capacities, Bellman-Ford or Floyd-Warshall for specialized shortest paths, A-star for one target with a lower-bound heuristic, strongly connected components for mutual reachability, bridge search for critical links, and binary lifting for repeated ancestor queries.
  A{"What must the answer prove?"}
  A -->|"cheapest connection<br/>of all vertices"| B{"How are edges consumed?"}
  B -->|"sorted edge list"| C["Kruskal + DSU"]
  B -->|"grow from a frontier"| D["Prim + heap"]
  A -->|"maximum amount through<br/>capacity-limited edges"| E["Max flow<br/>Dinic / Edmonds–Karp"]
  A -->|"shortest paths with<br/>negative edges"| F["Bellman–Ford"]
  A -->|"all-pairs paths<br/>with small V"| G["Floyd–Warshall"]
  A -->|"mutual reachability<br/>groups"| H["Strongly connected<br/>components"]
  A -->|"links whose removal<br/>disconnects the graph"| I["Bridges / articulation points"]
  A -->|"many ancestor or<br/>path queries on a tree"| J["LCA / binary lifting"]
  A -->|"one target with a<br/>useful lower bound"| K["A* heuristic search"]

This selection begins with the output contract. Edge direction, weights, capacities, graph size, and number of queries then remove invalid candidates.

Detailed guides

Each guide separates recognition, proof, template, complexity, and failure cases:

• Minimum spanning trees: cut property, Kruskal versus Prim, and disconnected inputs.
• Network flow: residual edges, augmenting paths, min-cut, and matching reductions.
• Bellman–Ford: negative edges and reachable negative-cycle detection.
• Floyd–Warshall: the intermediate-vertex DP state for all-pairs paths.
• Strongly connected components: Kosaraju and the condensation DAG.
• Bridges and articulation points: discovery times, low links, parallel edges, and root handling.
• LCA and binary lifting: preprocessing a static tree for repeated ancestor queries.
• A* heuristic search: admissible heuristics and a tested four-direction grid contract.

Tested example: minimum spanning tree

Kruskal sorts edges by weight and accepts an edge only when it joins different components.

flowchart TD
  accTitle: Kruskal minimum-spanning-tree decision loop
  accDescr: Sort edges by increasing weight, inspect the next edge, skip it when both endpoints are already connected, otherwise unite the components and accept it, and stop after n minus one accepted edges.
  A["Sort edges by increasing weight"] --> B["Take next edge (u, v, weight)"]
  B --> C{"find(u) = find(v)?"}
  C -->|yes| D["Skip: it would create a cycle"]
  C -->|no| E["Union components<br/>and accept edge"]
  D --> F{"Accepted n - 1 edges?"}
  E --> F
  F -->|no| B
  F -->|yes| G["Minimum spanning tree complete"]

Invariant: accepted edges form a forest that can still be extended to a minimum spanning tree.

The disjoint-set structure makes cycle checks nearly constant amortized time. After processing, exactly n - 1 accepted edges are required for a connected graph.

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;
}

The implementations validate every endpoint, accept negative edge weights, and reject a disconnected graph instead of silently returning a forest. The complete MST guide explains when Prim is the better representation.

Copy-ready policy

Pseudocode is labeled as explanation. Only implementations under codes/ are promised to compile or import in the current release.

Primary references

The selection table and complexity checks are cross-checked against Princeton's Algorithms and Data Structures Cheatsheet, minimum-spanning-tree chapter, shortest-path chapter, and directed-graph chapter.