[C++]最小生成树
2020-12-13 16:53
标签：生成 ESS 注意 amp chm image $$ href 流程 就以上图为例： 时间复杂度： $$O(nm+m)$$ 这个算法的时间的主要瓶颈就是在我们寻找那一条边的边权最小的时候，那么注意到这里其实是可以通过堆优化的。代码如下： 时间复杂度： $O(n\log m + m)$ 还是以上图为例： 时间复杂度：$O(n^2)$ 算法的主要时间瓶颈就是在如何判断原来两个点已经连通，如果用DFS或者BFS的话，效率较低，所以我们这里使用并查集优化。 时间复杂度：$O(m \log m+m \alpha (n))$ ==by szdytom == [C++]最小生成树 标签：生成 ESS 注意 amp chm image $$ href 流程 原文地址：https://www.cnblogs.com/szdytom/p/11622045.html1. 最小生成树定义
树是指没有环路的图，生成树就是指一个图上面删除一些边，使它没有环路。
最小生成树就是指生成树中边权之和最小的那一种。
上图的最小生成树就是这样：
2. Prim 算法
2.1. 算法流程
2.2. 优化
int ans = 0;
int index = 1;
h.push(point(0, 1));
while (index
3. kruskal 算法
3.1. 算法流程
3.2. 优化
sort(E.begin(), E.end(), cmp);
int index = 1, np = 0;
int ans = 0;
while (index = E.size()) break;
node now = E[np++];
if (getf(now.u) == getf(now.v)) continue;
++index;
ans += now.w;
merage(now.u, now.v);
}
