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 更新 |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| =====Prim算法===== | =====Prim算法===== | ||
| - | Prim算法可以理解为“加点法”。算法的流程是，随意选择一个起始点$s$，把图$G=\langle E,V \rangle$的点集$V$分为两个部分$S,T$，即$S \bigcup T = V$且$S \cap T = \emptyset$。初始情况下，$S={s}$，$T$即是剩下的点的集合。每次操作，我们选择连接两个集合的边中最短的那个边，将其加入我们选择的生成树，并把这条边所连接的那个不在$S$中的点从$T$中移动到$S$中。当我们选择了$n-1$条边后就得到了最小生成树。 | + | Prim算法可以理解为“加点法”。算法的流程是，随意选择一个起始点$s$，把图$G=\langle E,V \rangle$的点集$V$分为两个部分$S,T$，即$S \cup T = V$且$S \cap T = \emptyset$。初始情况下，$S={s}$，$T$即是剩下的点的集合。每次操作，我们选择连接两个集合的边中最短的那个边，将其加入我们选择的生成树，并把这条边所连接的那个不在$S$中的点从$T$中移动到$S$中。当我们选择了$n-1$条边后就得到了最小生成树。 |
| - | 我们会发现，Prim算法的流程于Dijkstra算法的流程十分相似，事实上，朴素Prim算法的时间复杂度也是$O(V^2)$，并且它也可以用二叉堆来优化，优化后的时间复杂度为$O(ElogV)$。此外，Prim算法还可以用斐波那契堆来优化，优化后的时间复杂度为$O(E+VlogV)$。 | + | 我们会发现，Prim算法的流程于Dijkstra算法的流程十分相似，事实上，朴素Prim算法的时间复杂度也是$O(V^2)$，并且它也可以用二叉堆来优化，优化后的时间复杂度为$O(E \log V)$。此外，Prim算法还可以用斐波那契堆来优化，优化后的时间复杂度为$O(E+V \log V)$。 |
| =====Kruskal算法===== | =====Kruskal算法===== | ||
| 行 13: | 行 13: | ||
| Kruskal算法可以理解为“加边法”。先将图中所有的边从小到大排序，然后从小往大尝试添加，如果一条边的两端不在同一个集合就将其加入，这一过程需要使用到并查集，当加入$n-1$条边后就得到了原图的最小生成树。 | Kruskal算法可以理解为“加边法”。先将图中所有的边从小到大排序，然后从小往大尝试添加，如果一条边的两端不在同一个集合就将其加入，这一过程需要使用到并查集，当加入$n-1$条边后就得到了原图的最小生成树。 | ||
| - | 显然，Kruskal算法的时间复杂度为$O(ElogE)$。 | + | 显然，Kruskal算法的时间复杂度为$O(E \log E)$。 |
| =====分析及证明===== | =====分析及证明===== | ||
2020-2021/teams/hotpot/mst.1588999585.txt.gz · 最后更改: 2020/05/09 12:46 由 misakatao
