Minimum spanning tree
A minimum spanning tree is a spanning tree of a connected, weighted, undirected graph having the smallest possible total edge weight.
Optimization Algorithms: AI techniques for design, planning, and control problems
An algorithm that finds a minimum-weight tree connecting every node of a connected weighted graph.
- How it is used
- Frames minimum spanning trees as an informed-search solution for connecting networks while minimizing total edge cost.
- How deep it goes
- Defines spanning trees, compares three algorithms, works through Kruskal, and demonstrates Python implementation without formal proofs.
- Examples
- Uses the muddy city road-repair problem, toy graph figures, a NetworkX graph, and a University of Toronto street network.
- What you can do after
- Apply it via NetworkX and OSMnx to compute, visualize, and inspect minimum spanning trees for toy or street-network graphs.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
A minimum spanning tree is a spanning tree of a weighted graph whose total edge weight is minimal among all spanning trees of that graph.
- How it is used
- Frames minimum-cost network design as connecting every node without cycles.
- How deep it goes
- Defines trees, cycles, connected graphs, and spanning trees, then implements Prim's algorithm with a priority queue.
- Examples
- Uses a 15-city distance graph, printed adjacency lists, selected MST edges, and a total weight of 5,372.
- What you can do after
- Apply it via Swift by constructing a weighted graph and calling mst(start:) to obtain selected edges.
Also covered in
What to know first
- edgeAn edge is a connection between two vertices or nodes in a graph or related structure, representing a relationship and optionally carrying direction, labels, or weights.
- nodeA node is a discrete element of a graph, tree, linked structure, network, or computing system that can represent an entity, state, or component and may connect to other elements.
- priority queueA priority queue is an abstract data type that retrieves or removes elements according to assigned priority rather than insertion order.
Related concepts
- spanning treekind of · A spanning tree is a tree subgraph of a connected graph that contains every vertex.
- treekind of · A tree is a connected, acyclic structure of nodes organized through parent-child relationships, typically around a single root.
- Jarnik's algorithmproduced by · Jarnik’s algorithm, also called Prim’s algorithm, is a greedy algorithm that constructs a minimum spanning tree by repeatedly adding the lowest-weight edge connecting the current tree to an outside vertex.
- Kruskal's algorithmproduced by · Kruskal’s algorithm is a greedy algorithm that constructs a minimum spanning tree by adding edges in nondecreasing weight order when they connect separate components.
- Traveling Salesman problemcontrasts with · The Traveling Salesman problem is a combinatorial optimization problem that seeks a minimum-cost tour visiting each specified location exactly once and returning to the starting location.
- graphpart of · A graph is a mathematical structure consisting of vertices and edges that connect pairs of vertices to represent relationships or connections.
Questions about minimum spanning tree
What is minimum spanning tree?
A minimum spanning tree is a spanning tree of a connected, weighted, undirected graph having the smallest possible total edge weight.
Which Manning books explain minimum spanning tree?
Optimization Algorithms: AI techniques for design, planning, and control problems and Classic Computer Science Problems in Swift: Essential techniques for practicing programmers.
What should I know before learning minimum spanning tree?
Manning books that teach minimum spanning tree usually introduce edge, node and priority queue first.
What is the difference between minimum spanning tree and Traveling Salesman problem?
A minimum spanning tree is a spanning tree of a connected, weighted, undirected graph having the smallest possible total edge weight. The Traveling Salesman problem is a combinatorial optimization problem that seeks a minimum-cost tour visiting each specified location exactly once and returning to the starting location.
What is minimum spanning tree a kind of?
Minimum spanning tree is a kind of spanning tree. A spanning tree is a tree subgraph of a connected graph that contains every vertex.
What is minimum spanning tree part of?
Minimum spanning tree is part of graph. A graph is a mathematical structure consisting of vertices and edges that connect pairs of vertices to represent relationships or connections.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.

