最小生成树算法描述

最小生成树算法的求解过程通常从一个空树开始，逐步添加边以形成一棵包含n-1条边的最小生成树。这个通用算法可以用伪代码简洁表示：

最小生成树的求解步骤如下：

• 定义一个初始为空的树T，表示顶点集和边集。


• 重复以下操作，直到T成为图G的生成树：在T中寻找一条安全边（u，v），即加入这条边后T仍保持为MST的子集。


• 将找到的安全边(u，v)添加到T中，扩大T的范围。

这可以用Pascal、Prim算法或Kruskal算法等具体实现，它们的区别在于寻找安全边的方式不同：

• Prim算法：从一个起点v0开始，逐步加入与生成树距离最近的未加入顶点，更新边集。


• Kruskal算法：按权值递增顺序挑选边，每次选择不形成回路的边加入到最小生成树中。

扩展资料

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图联通的最少的边。