最小生成树的应用,算法和总结
树图思维导图提供 最小生成树思维脑图 在线思维导图免费制作,点击“编辑”按钮,可对 最小生成树思维脑图 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是: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 ,采用邻接表进行存储边之间的关系(更多采用结构体的方式)。
树图思维导图提供 唯物辩证法思维脑图 在线思维导图免费制作,点击“编辑”按钮,可对 唯物辩证法思维脑图 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:10fcb85e51ca26a78545113c04bc35a5
树图思维导图提供 0505早会思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 0505早会思维导图 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:578d19b977f9356c161f897857e63de0