我试图用min Heap实现Prim的算法.这里是我提到的链接。https:/www.geeksforgeeks.orgprims-mst-for-adjacency-list-representation-greedy-algo-6
我想知道为什么我们可以使用一个矢量，然后使用 std::sort 函数来代替min heap。
你可以这样做，但是要记住，每次有新的节点加入到MST中，你都必须更新穿越分区的边集（通往还没有进入MST的节点的边），所以你必须在算法的每次迭代中对你的向量进行排序，这将会浪费时间，因为你只需要知道穿越分区的边中哪一条在该迭代中具有最小值，对于该操作来说，min堆是最优的，因为其提取最小值的时间复杂度是 O(log n) 而排序是 O(n log n) 这可能会使算法在大图或密集图上运行得更慢。