生成树

生成树是连通网络的骨架。它保留任意两顶点之间的可达性，却删除所有形成环的冗余边。树中任意两点之间只有一条简单路径，因此每条边都承担不可替代的连接职责。

这种骨架同时具有两种极值性质。删去任意树边，图会断开；向树加入任意一条非树边，图中会出现唯一一个圈。前者说明它是极小连通结构，后者说明它是极大无圈结构。

一个连通图往往有许多生成树。它们选择不同的路径承担连接任务，反映原图中的冗余可以怎样被裁剪。生成树本身不保留故障容错；删去骨架上的一条边便会断网，所以工程系统通常在树之外保留额外边。

三角形图有三棵生成树，每棵都删除三条边中的一条。原图的一个圈对应三种可删边选择；得到的每棵树都保留三个顶点，并含两条边。

取外圈边 $ab,bc,cd,da$ 和对角线 $ac$。先删去三角形 $abc$ 上的边 $ac$，得到四圈；再删去四圈上的 $da$，便留下路径 $a-b-c-d$。每一步都能用原圈的另一侧绕行，故连通性保持，最终得到三边生成树。

反过来，直接选择 $ab,bc,ac$ 虽然也有三条边，却只在前三点围成三角形。生成子图必须仍保留顶点 $d$，此时 $d$ 成为孤立点，结果不连通。失败之处不是可以把 $d$ 从顶点集漏掉，而是所有顶点保留后仍未接通。

非连通图没有覆盖全部顶点的生成树。对每个连通分量分别取生成树，可以得到生成森林。若图有 $c$ 个连通分量，这样得到的生成森林含 $n-c$ 条边。这里“生成森林”要求每个原分量内部都被接通；任意保留全部顶点的无圈子图未必达到这个边数。零顶点图没有本条所定义的生成树，但有空生成森林，符合 $0-0=0$。

带权图中的最小生成树理路最小生成树Minimum spanning tree · MST连通加权图中总边权最小的生成树及其算法问题。在所有生成树中最小化总权重。它仍然先满足“覆盖、连通、无圈”，再比较成本；最短路径树则从固定源点优化到各点的距离，两种目标通常产生不同树。

对连通图，深度优先搜索理路深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。和广度优先搜索理路广度优先搜索Breadth-first search · BFS按无权距离分层访问可达顶点的图遍历算法。记录首次发现新顶点的边，便能在邻接表表示下用 $O(|V|+|E|)$ 时间构造生成树。每条记录边都把一个新顶点接到已发现部分，因而不会成圈；搜索又能到达全部顶点，故最终确实是一棵生成树。搜索树还保留遍历层次、父子关系或 DFS 时间戳，成为连通性、割点和回边分析的基础。

图拟阵理路图拟阵Graphic matroid以图边为底集、以无环边集为独立集的拟阵。把无圈边集视为独立集；当原图连通时，生成树的边集恰好是其基，原图不连通时则由各分量的生成树共同组成基。不同生成树都含 $n-1$ 条边，基交换性质解释了许多贪心算法为何能够逐边替换而不破坏可行性。

反向搜索枚举理路反向搜索枚举Reverse search enumeration · Avis-Fukuda reverse search · 逆向搜索枚举为每个完整解指定唯一且有限到根的父映射，反向遍历隐式解树；以生成树换边实现无已见集合、可恢复邻居游标的低存储枚举。把一次合法交换组织成全部生成树的唯一父关系：加入最小缺失根树边，再删圈中最大的非根边，缺失根边数恰减一。沿父关系反向遍历即可逐一输出所有树；四点五边例交付八份不同边集，并证明邻居槽恢复和无全局已见集合的空间界。

Cayley 公式理路Cayley 树计数公式Cayley's formula顶点集固定为 $[n]$ 的标号树恰有 $n^{n-2}$ 棵。计数完全图的生成树；矩阵树定理把生成树总数写成图 Laplacian 的任一主余子式。生成树因此不仅是算法输出，也连接组合计数、线性代数与电网络。

生成树桥接理路生成树桥接与端口角色Spanning Tree Protocol · STP · 生成树协议由根ID、根路径成本和端口平局规则计算活动转发树，证明稳定拓扑无环，并用三角形区分最短根路径、最小总成本和切换期安全。将“连通且无环”用作网络数据转发条件：桥通过根与路径消息选端口，稳定父方向上的正成本严格下降。图论结论描述最终骨架，协议还要处理旧消息过期和端口切换；最短根路径形成的桥树也不必最小化整棵树的总成本。