1回答

liuyubobobo

2017-07-16

已采纳

在 while 循环中每次选择了一条边e，并且通过if判断保证了后续处理的这条边e的两个端点一定不是同色的。之后选择了一个未被访问过的端点，在 visit 函数中查看这个端点的所有邻边。这些邻边中除了e之外，可能还有其他的边和这个端点同色，所以在 visit 中，使用这个if判断，可以提前将不符合要求的边剔除，优化算法。

如果没有这个if，算法确实是正确的。但是注意：我们的 Prim 算法在初始化的时候创造了一个最小堆，这个最小堆我们定义其容量最大为图中边的个数：

LazyPrimMST(Graph &graph):G(graph), pq(MinHeap<Edge<Weight>>(graph.E())){
    
    ...

}

如果在 visit 中删除这个 if 判断，不仅仅算法时间性能不优，从空间的角度，我们的最小堆中放入的边，有可能远远大于图中的边的个数。预估在这种情况下最小堆中最多会存入多少条边也是一个麻烦的事情（但不是不可以，可以想想看：））。但是我们现在的代码，可以保证，在最小堆中的边数不会超过图中的总边数：）

1

3

liuyubobobo

回复

tobeabee

是的：）

2021-11-22

共3条回复