2020-2021:teams:hotpot:mst
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:mst [2020/05/09 12:46] misakatao 更新 |
2020-2021:teams:hotpot:mst [2020/05/09 12:47] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| Kruskal算法可以理解为“加边法”。先将图中所有的边从小到大排序，然后从小往大尝试添加，如果一条边的两端不在同一个集合就将其加入，这一过程需要使用到并查集，当加入$n-1$条边后就得到了原图的最小生成树。 | Kruskal算法可以理解为“加边法”。先将图中所有的边从小到大排序，然后从小往大尝试添加，如果一条边的两端不在同一个集合就将其加入，这一过程需要使用到并查集，当加入$n-1$条边后就得到了原图的最小生成树。 | ||
| - | 显然，Kruskal算法的时间复杂度为$O(ElogE)$。 | + | 显然，Kruskal算法的时间复杂度为$O(E \log E)$。 |
| =====分析及证明===== | =====分析及证明===== | ||
2020-2021/teams/hotpot/mst.1588999613.txt.gz · 最后更改: 2020/05/09 12:46 由 misakatao
