最小(代价)生成树—Prim算法与Kruskal算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了最小(代价)生成树—Prim算法与Kruskal算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、最小生成树的特点

二、最小生成树算法

① Prim(普里姆)算法

②Kruskal(克鲁斯卡尔)算法

③Prim算法与Kruskal算法对比

一、最小生成树的特点

最小生成树是带权连通图G=(V,E)的生成树中边的权值之和最小的那棵生成树。它具有以下特点：

图G中各边权值互不相等时有唯一的最小生成树。图G的边数等于顶点数减1时，图G的最小生成树是它本身。其他情况最小生成树不是唯一的。
最小生成树的边的权值之和是唯一的且是最小的。
最小生成树的边数为顶点数减1。

二、最小生成树算法

① Prim(普里姆)算法

基本思想

初始时从图中任意选择一个顶点加入树T。

之后选择一个与当前顶点集合之间的边权值最小的顶点，并将该顶点和相应的边加入树T，每次操作后顶点数和边数都加1。

重复步骤2，直至图中所有顶点都并入了树T，得到的T就是最小生成树。

最小(代价)生成树—Prim算法与Kruskal算法

408标准2017：MST的顶点和边一样时，就是同一个MST，不区分根结点是谁。

②Kruskal(克鲁斯卡尔)算法

基本思想

初始时为只有n个顶点而无边的非连通图T={V，{}}，每个顶点自成一个连通分量。

然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边选择接下来权值最小的边。

重复步骤2，直至图中所有顶点都连通了，得到的T就是最小生成树。

最小(代价)生成树—Prim算法与Kruskal算法