spanning tree
A subset of a connected graph's edges that links all V vertices together with no cycles, using exactly V minus one edges.
In more detail
Removing any edge from a spanning tree disconnects it, and adding any edge creates a cycle. A graph usually has many spanning trees; the minimum spanning tree is the one with the smallest total weight.
Related terms
- minimum spanning tree — The spanning tree of a weighted, connected graph whose edges have the smallest possible total weight.
- tree — A hierarchy of nodes joined by edges, with one root at the top, no cycles, and exactly one path between any two nodes.
- subgraph — A graph made from some of another graph's vertices and edges.
Taught in
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers