Prim在O(| V | ^ 2)中的MST算法

Question

时间的复杂性普里姆的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 的解释比你拥有的伪代码更好。看一下，如果您还有其他问题，请告诉我。