Prim算法生成最小生成树

叶茂林

发布于 2023-07-30 14:41:18

1580

发布于 2023-07-30 14:41:18

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

最小生成树

对于一个图，我们可以把它转换成一颗树（联通图）或者是多棵树（非联通树）。

对于一个带权值的联通图，最小生成树就是它的所有生成树中边权值和最小的生成树。

Prim算法?

Prim算法就是一种用来生成最小生成树的算法。

由一个带权值的联通图到一个最小生成树的过程，其实就是从图的所有边中挑出一部分边用来组成树的过程，所以关键在于如何挑选边。

对于Prim算法，它的具体操作是这样的：

对于给定的一个起点节点（Prim算法必须给它一个起点），先找出这个节点连接的所有节点所组成的边中权值最小的边，作为最小生成树的第一条被挑选出来的边，现在我们有两个节点了对吧？然后以这两个节点为基础，继续找出这两个点连接的所有节点所组成的边中权值最小的边，同时这个查找过程，需要注意不能找已经连起来的节点，具体体现在代码实现上就是每找到节点就标记一下。

看过程图：