最小生成树——Prim算法和Kruskal算法

2021-06-08 21:03

阅读：554

标签：kruskal算法最小生成树最小 style 概念 mst prim 联通图获取

要了解最小生成树的概念，我们首先要知道生成树是什么

生成树的定义

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

最小生成树的性质

1.容易想象，要保证n个节点联通，至少要有n-1条边，所以一个有n个节点的生成树必有n-1条边。

2. 在所有生成树中，最小生成树的权值之和是最小的。

3. 再添加任意一条边，都将造成回路。

MST性质

描述：假设N=（V，{E}）是一个连通网，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边（u，v）的最小生成树。

MST算法告诉我们，可以通过不断确定最小权值的边来获取最小生成树。下面介绍两种根据MST性质，构造最小生成树的算法。

Prim算法

Prim算法的构造最小生成树的方法是，从图中选取任意一个点作为当前集合，每次选取和当前集合中的点中距离最近的点，这里的距离指和集合中任意一个点的距离。

Krusakal算法

算法特点: 每次更新节点权值

最小生成树——Prim算法和Kruskal算法

标签：kruskal算法最小生成树最小 style 概念 mst prim 联通图获取

原文地址：https://www.cnblogs.com/xyhj/p/14509171.html

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：最小生成树——Prim算法和Kruskal算法
文章链接：http://soscw.com/index.php/essay/92375.html

亲，登录后才可以留言！