spanning-trees

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.24 Common Bugs

11.24 Common Bugs Problem Minimum spanning tree code often fails for reasons that are easy to miss in clean textbook examples. The graph is disconnected. The edge list has parallel edges. The total cost overflows. The implementation forgets to store reverse edges. The priority queue contains stale entries. The union-find structure compares vertices instead of roots. These bugs are common because MST algorithms combine several moving pieces: graph representation edge...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.2 Cut Property

11.2 Cut Property Problem Minimum spanning tree algorithms repeatedly make local decisions. At each step, they select one edge from many available choices. The challenge is determining whether a locally attractive edge can safely become part of a globally optimal solution. Suppose a graph contains thousands or millions of edges. Testing every possible spanning tree is computationally infeasible. We need a rule that identifies edges that must belong to some...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.5 Prim's Algorithm

11.5 Prim's Algorithm Problem Kruskal's algorithm builds a minimum spanning tree by selecting edges globally. It sorts every edge in the graph and repeatedly connects separate components. There is another approach. Instead of constructing many small trees and merging them, we can start with a single vertex and grow one tree until it spans the entire graph. This idea leads to Prim's algorithm. Like Kruskal, Prim produces a minimum spanning...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.23 Choosing the Right MST Algorithm

11.23 Choosing the Right MST Algorithm Problem By this point, you have seen three major minimum spanning tree algorithms: Kruskal Prim Borůvka All produce the same result. All are correct. All are efficient. This naturally raises a practical question: Which one should you use? Many developers learn all three algorithms but never develop a framework for selecting between them. As a result, they either use the same algorithm everywhere or...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.13 Second-Best Spanning Tree

11.13 Second-Best Spanning Tree Problem A minimum spanning tree gives the cheapest way to connect all vertices. In practice, the cheapest tree may not be the only tree worth knowing. A cable route may become unavailable. A road segment may be blocked by regulation. A network design may need a backup plan. A contest problem may ask for the next larger spanning tree cost. In each case, you need the...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.16 Sparse Graph Handling

11.16 Sparse Graph Handling Problem Minimum spanning tree algorithms are usually described in terms of V vertices and E edges. That notation hides an important engineering detail: the graph’s density strongly affects which representation and algorithm are best. A sparse graph has relatively few edges compared with the number of vertices. In many real systems, each vertex connects only to a small number of neighbors. Examples include: road intersections computer...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.20 Complexity Analysis

11.20 Complexity Analysis Problem Minimum spanning tree algorithms are easy to state, but their performance depends heavily on representation and data structure choices. The same graph problem can produce different costs depending on whether you use: edge list adjacency list adjacency matrix binary heap union-find sorting A useful complexity analysis must therefore answer more than: What is the Big O? It should answer: Which operation dominates? Which representation is assumed?...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.15 Network Design

11.15 Network Design Problem Many real-world optimization problems can be modeled as graphs. Cities become vertices. Roads become edges. Data centers become vertices. Network links become edges. Water treatment facilities, electrical substations, pipelines, rail systems, and communication towers can all be represented in the same way. The challenge is rarely to connect everything. The challenge is to connect everything at an acceptable cost. Consider a telecommunications company deploying fiber across...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.22 Testing MST Code

11.22 Testing MST Code Problem Minimum spanning tree implementations can look correct while failing on small edge cases. The usual failures are not in the theorem. They are in details such as input handling, duplicate edges, disconnected graphs, integer overflow, and incorrect component updates. A good test suite should verify more than the happy path. It should answer: Does the algorithm return a tree? Does it have minimum cost? Does...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.21 Implementation Patterns

11.21 Implementation Patterns Problem After studying cut properties, union-find, Kruskal, Prim, Borůvka, clustering, network design, and complexity analysis, a practical question remains: How should MST algorithms actually be implemented? Many algorithm failures are not caused by incorrect theory. They are caused by small implementation mistakes: incorrect edge sorting bad union-find duplicate edge handling disconnected graph assumptions overflow bugs This section collects implementation patterns that appear repeatedly in production-quality MST code....

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.1 Spanning Trees

11.1 Spanning Trees Problem You are given a connected undirected graph. You need a subset of edges that keeps every vertex reachable from every other vertex while using the smallest possible number of edges. This problem appears in communication networks, road systems, electrical distribution, dependency management, clustering, and many optimization problems. Before searching for the minimum-cost solution, we must understand the structure called a spanning tree. Solution A spanning tree...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.12 Minimum Bottleneck Spanning Trees

11.12 Minimum Bottleneck Spanning Trees Problem Minimum spanning trees minimize the total weight of selected edges. In some applications, however, the largest edge matters more than the total cost. Consider a communication network. A spanning tree with total cost: 100 and largest edge: 50 may be less desirable than a spanning tree with total cost: 110 and largest edge: 20 The second network has a smaller worst-case link. Similar situations...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.19 Correctness Proofs

11.19 Correctness Proofs Problem Minimum spanning tree algorithms are short. Their correctness proofs are not optional. Kruskal, Prim, and Borůvka all make greedy choices. A greedy algorithm is risky unless each local decision can be shown to preserve a globally optimal solution. Without a proof, the algorithm may look plausible while silently failing on edge cases. The goal of this section is to give reusable proof templates for MST algorithms....

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.6 Borůvka's Algorithm

11.6 Borůvka's Algorithm Problem Kruskal's algorithm grows a forest by processing edges globally. Prim's algorithm grows a single tree from a starting vertex. Both approaches are highly effective, but neither was the first minimum spanning tree algorithm. In 1926, before modern computers existed, the Czech mathematician entity["people","Otakar Borůvka","Czech mathematician"] developed an algorithm for designing an efficient electrical network. His solution became one of the earliest graph optimization algorithms and remains...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.18 Parallel and Distributed MST Algorithms

11.18 Parallel and Distributed MST Algorithms Problem The classical MST algorithms were designed for a single machine processing a graph stored in local memory. Modern graph-processing systems often face very different constraints. Consider: 10 billion edges hundreds of machines streaming input distributed storage A graph may be too large to fit into memory on a single server. Even when it fits, processing it sequentially can become a bottleneck. The challenge...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.14 Clustering

11.14 Clustering Problem You have a set of objects and pairwise distances between them. You want to divide the objects into groups so that nearby objects stay together and distant objects fall into different groups. This is a clustering problem. Minimum spanning trees provide a simple and effective clustering method when the data can be represented as a weighted undirected graph: vertex = object edge weight = distance or dissimilarity...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.3 Cycle Property

11.3 Cycle Property Problem The cut property identifies edges that can safely be added to a minimum spanning tree. An equally important question is the reverse: How can we identify edges that can safely be discarded? In large graphs, many edges obviously appear unnecessary. If we can prove that certain edges never belong to any minimum spanning tree, we can eliminate them immediately and reduce the search space. The cycle...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.4 Kruskal's Algorithm

11.4 Kruskal's Algorithm Problem Given a connected weighted undirected graph, find a spanning tree whose total edge weight is minimum. A brute-force approach would generate every possible spanning tree and compute its cost. Unfortunately, the number of spanning trees grows exponentially with graph size, making exhaustive search impractical even for moderately sized graphs. We need an efficient algorithm that constructs a minimum spanning tree directly. Solution Kruskal's algorithm is a...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.7 Union-Find

11.7 Union-Find Problem Many graph algorithms repeatedly ask the same question: Do these two vertices already belong to the same connected component? Consider Kruskal's algorithm. Before adding an edge: (u,v) we must determine whether the edge creates a cycle. A naïve solution performs DFS or BFS every time an edge is considered. For a graph with millions of edges, repeatedly traversing the graph becomes prohibitively expensive. We need a data...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.9 Union by Rank

11.9 Union by Rank Problem Path compression makes existing trees flatter, but it does not prevent bad trees from being created. Consider the following sequence: union(A,B) union(B,C) union(C,D) union(D,E) union(E,F) A naïve implementation might repeatedly attach one root beneath another: A | B | C | D | E | F Path compression eventually fixes this structure, but the first few operations may still be expensive. Can we avoid creating...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.25 Case Study: Building a Production-Quality MST Service

11.25 Case Study: Building a Production-Quality MST Service Problem Throughout this chapter, we have studied minimum spanning trees from multiple perspectives: Graph theory Greedy algorithms Union-find Kruskal Prim Borůvka Clustering Network design Performance analysis Testing The final challenge is bringing these ideas together into a real system. Suppose you are building a service that receives infrastructure graphs and computes minimum spanning trees for customers. The service must: accept large inputs...

Programming › Algorithm Cookbook ›

Chapter 11. Minimum Spanning Trees and Connectivity

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.8 Path Compression

11.8 Path Compression Problem The basic union-find structure can become highly unbalanced. Consider the sequence: union(A,B) union(B,C) union(C,D) union(D,E) union(E,F) A naïve implementation may produce: A | B | C | D | E | F Now evaluate: find(F) The search follows: F → E → D → C → B → A Every operation traverses the entire chain. For (n) vertices: $$ O(n) $$ time may be required for...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.26 Practice Exercises

11.26 Practice Exercises Problem Minimum spanning tree algorithms become useful only after you can recognize the pattern in unfamiliar problems. The core ideas are simple: connect all vertices minimize edge cost avoid cycles merge components But problem statements rarely say “use Kruskal” or “use Prim.” They describe networks, roads, cables, clusters, islands, sensors, or regions. Your task is to translate the story into a graph and then choose the right...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.11 Dynamic Connectivity Overview

11.11 Dynamic Connectivity Overview Problem Offline connectivity works well when edges are fixed, or when all updates can be processed in a convenient order. Real systems are messier. Networks gain and lose links. Roads close. Machines fail. Social connections appear and disappear. A graph changes over time, and we still need to answer questions such as: Are u and v connected right now? This is the dynamic connectivity problem. The...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.17 Dense Graph Handling

11.17 Dense Graph Handling Problem Sparse graphs reward algorithms that touch only existing edges. Dense graphs are different. When most vertex pairs have an edge, avoiding non-existent edges no longer helps much because there are few non-existent edges to avoid. A dense graph has edge count close to: V² Examples include: complete distance graphs small fully connected networks correlation graphs similarity graphs dense cost matrices In these settings, representation choices...

Programming › Algorithm Cookbook › Chapter 11. Minimum Spanning Trees and Connectivity ›

11.10 Offline Connectivity

11.10 Offline Connectivity Problem Suppose you are given a graph and thousands or millions of connectivity queries: Are vertices u and v connected? A straightforward approach runs DFS or BFS for every query. Example: Query 1: connected(A,D)? Query 2: connected(B,F)? Query 3: connected(C,E)? ... If the graph contains: $$ V = 100,000 $$ vertices and: $$ Q = 1,000,000 $$ queries, repeatedly traversing the graph becomes extremely expensive. In many...

#spanning-trees

11.24 Common Bugs

11.2 Cut Property

11.5 Prim's Algorithm

11.23 Choosing the Right MST Algorithm

11.13 Second-Best Spanning Tree

11.16 Sparse Graph Handling

11.20 Complexity Analysis

11.15 Network Design

11.22 Testing MST Code

11.21 Implementation Patterns

11.1 Spanning Trees

11.12 Minimum Bottleneck Spanning Trees

11.19 Correctness Proofs

11.6 Borůvka's Algorithm

11.18 Parallel and Distributed MST Algorithms

11.14 Clustering

11.3 Cycle Property

11.4 Kruskal's Algorithm

11.7 Union-Find

11.9 Union by Rank

11.25 Case Study: Building a Production-Quality MST Service

Chapter 11. Minimum Spanning Trees and Connectivity

11.8 Path Compression

11.26 Practice Exercises

11.11 Dynamic Connectivity Overview

11.17 Dense Graph Handling

11.10 Offline Connectivity