2020-2021:teams:hotpot:mst
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:mst [2020/05/09 12:47] misakatao 更新 |
2020-2021:teams:hotpot:mst [2020/05/09 12:47] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| 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算法可以理解为“加点法”。算法的流程是，随意选择一个起始点$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(E \logV)$。此外，Prim算法还可以用斐波那契堆来优化，优化后的时间复杂度为$O(E+V \log V)$。 | + | 我们会发现，Prim算法的流程于Dijkstra算法的流程十分相似，事实上，朴素Prim算法的时间复杂度也是$O(V^2)$，并且它也可以用二叉堆来优化，优化后的时间复杂度为$O(E \log V)$。此外，Prim算法还可以用斐波那契堆来优化，优化后的时间复杂度为$O(E+V \log V)$。 |
| =====Kruskal算法===== | =====Kruskal算法===== | ||
2020-2021/teams/hotpot/mst.1588999644.txt.gz · 最后更改: 2020/05/09 12:47 由 misakatao
