liveBook · Manning

Minimum spanning tree

A minimum spanning tree is a spanning tree of a connected, weighted, undirected graph having the smallest possible total edge weight.

How 2 Manning books explain it

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.

Read how Optimization Algorithms: AI techniques for design, planning, and control problems explains minimum spanning tree →

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.

Read how Classic Computer Science Problems in Swift: Essential techniques for practicing programmers explains minimum spanning tree →

Also covered in

What to know first

Related concepts

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.