Spanning tree
A spanning tree is a tree subgraph of a connected graph that contains every vertex.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
A spanning tree is a tree that includes every vertex of a graph.
- How it is used
- Frames spanning trees as the structure behind minimum-cost network design.
- How deep it goes
- Defines trees, cycles, connectivity, and minimum spanning trees, then demonstrates an implementation with Prim’s algorithm.
- Examples
- Uses a cycle-pruning diagram and a weighted graph connecting 15 United States metropolitan areas.
- What you can do after
- Builds a minimum spanning tree in Swift using a weighted graph, visited vertices, and an ascending priority queue.
Optimization Algorithms: AI techniques for design, planning, and control problems
A spanning tree is a cycle-free subgraph of an undirected graph that contains every vertex and connects them with the minimum number of edges.
- How it is used
- Models connected infrastructure while minimizing the number of selected edges or, for MSTs, their total cost.
- How deep it goes
- Defines structural conditions, distinguishes MSTs, and demonstrates Kruskal’s step-by-step edge selection with pseudocode and code.
- Examples
- Uses damaged-road repair, graph vertices A–F, and a weighted town network visualized with Python.
- What you can do after
- Apply it via Python, NetworkX, and Kruskal’s algorithm to construct and visualize a minimum spanning tree.
Related concepts
- minimum spanning treeincludes · A minimum spanning tree is a spanning tree of a connected, weighted, undirected graph having the smallest possible total edge weight.
- maximum weight spanning treeincludes · A maximum weight spanning tree is a spanning tree whose total edge weight is maximal among all spanning trees of a weighted graph.
- treekind of · A tree is a connected, acyclic structure of nodes, commonly organized hierarchically through parent-child relationships and optionally around a designated root.
- spanning tree protocolproduced by · Spanning Tree Protocol is a Layer 2 protocol that prevents bridged-network loops by selecting a loop-free topology and blocking redundant paths.
- spanning subgraphkind of · A spanning subgraph is a subgraph that contains every vertex of its original graph and a subset of its edges.
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.