生成树和最小生成树

相关概念

简单路径

简单路径（Simple Path）：一条路径中，除了起点和终点允许相同，其余顶点都没有相同顶点存在。若起点和终点相同，则成为简单回路（Simple Circuit）。

连通图与连通分量

• （强）连通图：任意两个顶点之间都存在路径。
• （强）连通分量：对于非连通图，图中各个极大连通子图为该图的连通分量。

求解连通分量需要基于某个顶点进行遍历，能访问到的顶点都属于一个连通分量。将所有顶点搜索完成后，即可得到所有的连通分量。

生成树

连通图的生成树（Spanning Tree）：一个连通图的所有顶点和能够连接所有顶点的最小数量边（n-1 条边）构成该连通图的生成树。

对于非连通图，所有连通分量的生成树构成非连通图的生成森林（Spanning Forest）。

最小生成树

**最小生成树（Minimum Spanning Tree, MST）**是指权最小的生成树，在求解如何将所有顶点连通代价最小的问题时需要使用。权最小意味着所有边权之和最小。

求解最小生成树的经典算法有：

• Prim 算法：一个个更新点，从顶点的角度构建最小生成树。
• Kruskal 算法：一个个更新边，从边的角度构建最小生成树。

链接到

• 上一个知识点：7.5 图的广度优先搜索
• 下一个知识点：7.7 Prim算法
• 相关知识点：树、逻辑结构与存储结构