数据结构与算法——第7章-图-普里姆算法(7.10.1)

发表于 2023-04-17 分类于开发， N-数据与算法，数据结构与算法阅读时长 ≈ 1 分钟

一概述

1
2
3

1.连通图的生成树
2.权值
3.最小生成树

1	通过前面的学习，对于含有 n 个顶点的连通图来说可能包含有多种生成树，例如图 1 所示：

1
2
3

图 1 中的连通图和它相对应的生成树，可以用于解决实际生活中的问题：
假设 A、B、C 和 D 为 4 座城市，为了方便生产生活，要为这 4 座城市建立通信。
对于 4 个城市来讲，本着节约经费的原则，只需要建立 3 个通信线路即可，就如图 1（b）中的任意一种方式。

在具体选择采用（b）中哪一种方式时，需要综合考虑城市之间间隔的距离，
建设通信线路的难度等各种因素，将这些因素综合起来用一个数值表示，当作这条线路的权值

假设通过综合分析，城市之间的权值如图 2（a）所示，对于（b）的方案中，选择权值总和为 7 的两种方案最节约经费。

这就是本节要讨论的最小生成树的问题，简单得理解就是给定一个带有权值的连通图（连通网），
如何从众多的生成树中筛选出权值总和最小的生成树，即为该图的最小生成树。

给定一个连通网，求最小生成树的方法有：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。