[图论总结] 最小生成树问题!

最小生成树

(图片来源于:Acwing算法基础课)

最小生成树问题是什么?

官方解释:

给定一张边带权的无向图G=(V, E)， 其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。 由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树

样例解释:

地图上有n个城市,需要在城市时间铺设公路,问铺设公路的总长度的最小值之和

在这里我们一般只求无向图的最小生成树

由于堆优化的prim不常用 我这里只罗列出Prim和Kruskal的算法思路和代码

稠密图和稀疏图的简单划分:

• 看边和点的平方是否接近,接近那么是稠密图

Prim朴素版(O n^2) 非常像dijkstra 稠密图

算法思路:

• 初始化dist[] = 0x3f
• 迭代n次 每次找到集合外距离最近的点(集合是已被用来更新的点的集合)
• 用该点来更新其他点到集合的距离

代码:

初始化dist
memset(dist, 0x3f, sizeof dist);

int res = 0;
for (int i = 0; i