写在前面
这是我学这个算法的时候看的博客:推荐博客(除了这个还看了老师发的资料)
为了复习以及加深理解,来简单写一篇学习笔记(预计半小时写完)
关于Boruvka
起因是在模拟赛遇到的T3。大意是:对于给出的完全图,\(w_{(u,v)}=a_{\max{(u,v)}}-a_{\min{(u,v)}}\),求最小生成树。
烧烤了半场比赛依然只拿了25分……
题解:用Boruvka算法简单解决。
当然这是一个最小生成树算法,那道题也是很显然的最小生成树题。
说到生成树,最先想到的就是Kruskal;然后是Prim(然而我Prim没怎么写过);至于Boruvka,大概是印象中只记得名字的存在。
简单来说,Boruvka像是前两者的结合体。它使用了Kruskal的贪心思想,同时也加入了Prim的向外扩展。
实现思路
最初令每个点为一个连通块,每一轮,对于所有连通块,求它连向其他连通块的最短边;如果一个连通块的最短边连向另一连通块,则把最小边加入图中。
伪代码
while 所有点未连通{
for 连通块 i
minw[i] = 从i连向其他连通块的最短边
for 连通块 i
if minw[i] 连接不同连通块{
ans += minw[i].w;
merge(minw[i].u, minw[i].v);
连通块数量 -= 1;
}
}
时间复杂度
假设求minw[i]
的时间复杂度为\(T\),那么总的时间复杂度就是\(O(T\log_{2}N)\)。
解题
一般来说,运用Boruvka解题的关键就在于优化\(T\)
例如题中给出边权特殊的完全图
朴素的\(T\)即\(N^2\);针对边权进行优化使得\(T\)在\(N\log_{2}N\)左右
例题
写在后面
于是一个小时才写完。今天心态有点炸裂TT
标签:连通,复杂度,最小,生成,Boruvka,minw From: https://www.cnblogs.com/meteor2008/p/18248497