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

发布于 2024-09-13 00:00:13 字数 777 浏览 10 评论 0原文

如果使用邻接矩阵表示，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}

编辑：

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

我想要低效的实施

原文

Time complexity of Prim's MST algorithm is O(|V|^2) if you use adjacency matrix representation.

I am trying to implement Prim's algorithm using adjacency matrix. I am using this
as a reference.

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}

EDIT:

I understand Prim's algorithm very well.
I know how to implement it efficiently using heaps and priority queues.
I also know about better algorithms.
I want to use adjacency matrix representation of graph and get O(|V|^2) implementation.

I WANT THE INEFFICIENT IMPLEMENTATION

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

还不是爱你 2024-09-20 00:00:13

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

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

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

Finding the lowest cost edge (u,v), such that u is in U and v is in V-U, is done with a priority queue. More precisely, the priority queue contains each node v from V-U together with the lowest cost edge from v into the current tree U. In other words, the queue contains exactly |V-U| elements.

After adding a new node u to U, you have to update the priority queue by checking whether the neighboring nodes of u can now be reached by an edge of lower cost than previously.

The choice of priority queue determines the time complexity. You will get O(|V|^2) by implementing the priority queue as a simply array cheapest_edges[1..|V|]. That's because finding minimum in this queue takes O(|V|) time, and you repeat that |V| times.

In pseudo-code:

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)

回复收藏 0 原文