Prim 的邻接矩阵实现可以使用最小堆吗？

Question

我发现有两种方法可以实现 Prim 算法，邻接矩阵的时间复杂度是 O(V^2) 而堆和邻接列表的时间复杂度是 O(E lg(V))。

我想知道当图用邻接矩阵表示时我可以使用堆。是否有意义？如果是这样，邻接矩阵+堆和邻接表+堆之间有什么区别吗？

Answer 1

通常，矩阵图表示对于 Prim 算法来说不是那么好。

这是因为算法的主要迭代，它从堆中弹出一个节点，然后扫描它的邻居。你如何找到它的邻居？使用矩阵图表示，您基本上需要遍历整个矩阵行（在列表图表示中，您只需要遍历节点的列表，它可以明显更短）。

这意味着，不管堆是什么，找到弹出节点的邻居的部分的总和已经是Ω(|V| ² )，因为每个节点的行最终都会被扫描。

所以，不 - 这没有多大意义。堆不会降低整体复杂性。