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

Question

我发现 there are two ways to implement Prim algorithm ，并且邻接矩阵的时间复杂度为 O(V^2)，而堆和邻接列表的时间复杂度为 O(E lg(V))。

我想知道当图形用邻接矩阵表示时我可以使用堆吗？是否有意义？如果是的话，邻接矩阵+堆和邻接表+堆有区别吗？

Answer 1

一般来说，矩阵图形表示对于 Prim 算法不是很好。

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

这意味着，无论堆如何，只是找到弹出节点的邻居的部分的总和已经是Ω(|V|²)，因为最终会扫描每个节点的行。

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