algorithm - Prim 的 MST 算法 O(|V|^2)

Question

Prim 的 MST 算法的时间复杂度是O(|V|^2)如果您使用邻接矩阵表示。

我正在尝试使用邻接矩阵来实现 Prim 的算法。我用这个 作为参考。

V = {1,2...,n}
U = {1}
T = NULL
while V != U:

     /* 
         Now this implementation means that 
         I find lowest cost edge in O(n).
         How do I do that using adjacency list? 
     */

     let (u, v) be the lowest cost edge 
                such that u is in U and v is in V - U;

     T = T + {(u,v)}
     U = U + {v}

编辑：

1. 我非常了解 Prim 的算法。
2. 我知道如何使用堆和优先级队列有效地实现它。
3. 我也知道更好的算法。
4. 我想使用图形的邻接矩阵表示并获得 O(|V|^2) 实现。

我想要低效的实施

Answer 1

找到最低成本边（u，v），使得u在 U 中，v在 VU 中，是通过优先级队列完成的。更准确地说，优先级队列包含来自 VU 的每个节点v以及从v到当前树 U 的最低成本边。换句话说，队列正好包含 |VU| 元素。

将新节点u添加到 U 后，您必须通过检查u的相邻节点现在是否可以通过比以前成本更低的边到达来更新优先级队列。

优先级队列的选择决定了时间复杂度。通过将优先级队列实现为简单的数组，您将获得 O(|V|^2) cheapest_edges[1..|V|]。那是因为在这个队列中找到最小值需要 O(|V|) 时间，然后你重复 |V| 次。

在伪代码中：

V = {2...,n}
U = {1}
T = NULL
P = array, for each v set P[v] = (1,v)

while V != U

    (u,v) = P[v] with v such that  length P[v]  is minimal

    T = T + {(u,v)}
    U = U + {v}

    for each w adjacent to v
        if length (v,w) < length P[w] then
            P[w] = (v,w)

Answer 2

您可以像在Dijkstra 的算法中一样，通过选择连接到具有最小成本边（不生成循环）的当前部分树的节点来执行此操作。我认为维基百科对 Prim 的解释比你拥有的伪代码更好。看一看，如果您有更多问题，请告诉我。

Answer 3

您可以按成本对边进行排序，然后按成本的顺序迭代边，如果该边连接两个不同的子图，则使用该边。

我在这里有一个实现。它依次读取顶点数（N）、边数（M）和边（A，B，Cost），然后输出边。这就是克鲁斯卡尔算法。

可以在此处找到使用相同输入的 Prim 算法与堆的实现。