最小生成树思维脑图思维导图

U425500912

2024-01-13

浏览量: 3

算法介绍

程序算法

最小生成树

最小生成树的应用，算法和总结

树图思维导图提供《最小生成树思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《最小生成树思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：04fefad762cd608b06e4d1a8541e49e6

思维导图大纲

什么是树

如果一个无向连通图不包含回路(连通图中不存在环),那么就是一个树。

最小生成树

一个图中可能存在多条相连的边,我们一定可以从一个图中挑出一些边生成一棵树。这仅仅是生成一棵树,还未满足最小,当图中每条边都存在权重时,这时候我们从图中生成一棵树(n - 1 条边)时,生成这棵树的总代价就是每条边的权重相加之和。

一个有N个点的图，边一定是大于等于N-1条的。图的最小生成树，就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。

最小生成树的应用

要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

实现最小生成树的两种算法

Prim

算法分析:

Prim算法每次循环都将一个蓝点u变为白点，并且此蓝点u与白点相连的最小边权min[u]还是当前所有蓝点中最小的。这样相当于向生成树中添加了n-1次最小的边，最后得到的一定是最小生成树。

Kruskal

Kruskal算法是一种巧妙利用并查集来求最小生成树的算法。

算法描述:

在描述 kruskal 算法时先了解一下连通块的概念, 我们将无向图中相互连通的一些点称为处于同一个连通块中。

Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。

Kruskal算法开始时，认为每一个点都是孤立的，分属于n个独立的集合。

生成树中没有边 Kruskal每次都选择一条最小的边，而且这条边的两个顶点分属于两个不同的集合。将选取的这条边加入最小生成树，并且合并集合。

Kruskal算法每次都选择一条最小的，且能合并两个不同集合的边，一张n个点的图总共选取n-1次边。因为每次我们选的都是最小的边，所以最后的生成树一定是最小生成树。每次我们选的边都能够合并两个集合，最后n个点一定会合并成一个集合。通过这样的贪心策略，Kruskal算法就能得到一棵有n-1条边，连接着n个点的最小生成树。

总结

从上面的两道模板可得知,解决最小生成树的问题一般有两种方式:prim 和 Kruskal ,那么,什么时候选择哪种策略就成为了我们应该思考的一个问题: 稀疏图一般选择 prim,采用邻接矩阵进行存储边之间的关系。稠密图一般选择 Kruskal ,采用邻接表进行存储边之间的关系(更多采用结构体的方式)。

3A Unit 1 A Proper Job思维导图