Minimum spanning tree

As explained in 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 Classic Computer Science Problems in Swift: Essential techniques for practicing programmers covers it

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 it assumes

Assumes graph familiarity enough to use vertices and edges, while defining trees, cycles, connected graphs, and spanning trees.

What you can do after

Apply it via Swift by constructing a weighted graph and calling mst(start:) to obtain selected edges.

How it connects

Connects weighted graphs, spanning trees, cycles, priority queues, adjacency lists, and Prim's algorithm.

liveBookmanning.com

Read Classic Computer Science Problems in Swift: Essential techniques for practicing programmers on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Optimization Algorithms: AI techniques for design, planning, and control problemsAn algorithm that finds a minimum-weight tree connecting every node of a connected weighted graph.

Compare how 2 books explain minimum spanning tree →

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, commonly organized hierarchically through parent-child relationships and optionally around a designated 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.
• informed searchaddressed by · Informed search is a search strategy that uses problem-specific knowledge or heuristic estimates to prioritize promising states or paths.

This explainer was generated by Manning's knowledge graph from the text of Classic Computer Science Problems in Swift: Essential techniques for practicing programmers. The section links point to the parts of the book it draws on.