Spanning-Tree

定义 Definition

spanning-tree（生成树）：在图论中，指一个连通图的子图，它包含图中所有顶点，并且边的数量最少、不含回路（环），因此形成一棵“树”。（常见相关概念还有 minimum spanning tree 最小生成树。）

发音 Pronunciation

/ˈspænɪŋ triː/

例句 Examples

A spanning tree connects all the nodes without forming any cycles.
生成树连接所有节点，但不会形成任何环。

To minimize cabling cost, the engineer computed a spanning tree of the network graph and then refined it into a minimum spanning tree.
为降低布线成本，工程师先计算了该网络图的生成树，再进一步优化为最小生成树。

词源 Etymology

该词由 spanning（“跨越、覆盖全部”）+ tree（“树状结构”）组成。它形象地表达了：用树结构覆盖（包含）图中的所有顶点，同时保持无环与连通，这是图论与网络设计中的核心概念之一。

相关词 Related Words

• Graph
• Tree
• Vertex
• Edge
• Cycle
• Connected
• Subgraph
• Minimum-Spanning-Tree
• Kruskal
• Prim

文学与经典著作 Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在图算法章节系统讲解生成树与最小生成树。
• Graph Theory（Bondy & Murty）：在图论基础内容中讨论树、连通性与生成树相关定理。
• Network Flows: Theory, Algorithms, and Applications（Ahuja, Magnanti, Orlin）：在网络优化与算法背景下涉及生成树及其应用。