老师，在视频的末尾你说优化后的prim算法中遍历边的次数也变少了，我不是很理解这个意思（时间复杂度那个就能理解）
来源：8-4 Prim算法的优化
tobeabee
2021-11-21
写回答
1回答
-
能否给我一个视频的具体时间位置，我看一下上下文？
==========
简单来说，就是在使用索引堆的 Prim 算法中，不需要 56-57 行的判断：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/08-Minimum-Span-Trees/Course%20Code%20(C%2B%2B)/03-Lazy-Prim/LazyPrimMST.h
在 lazyPrim 中，52 行的 while 循环每次取出的不一定是“横切边”，但是当使用索引堆以后，保证每次 while 循环内一定处理一条横切边，我说的是这重 while 循环，使用索引堆以后，更少。
继续加油！：）
032021-11-23
相似问题