Prim的MST算法在O（| V |^2）

时间复杂度为如果使用邻接矩阵表示，则Prim的MST算法为O(|V|^2)。Prim的MST算法在O（| V |^2）

我想实现使用邻接矩阵的Prim算法。我正在使用this 作为参考。

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）的实现。

我想不能有效地实施

来源

2010-08-06 Pratik Deoghare

这是V^2实现朝向页面末尾http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/primAlgor.htm – Ankush 2012-08-22 21:38:55

你不喜欢它在Dijkstra's algorithm，通过选择连接到您当前的部分树以最小的成本边缘节点（即不产生循环）。我认为wikipedia解释Prim比你有的伪码更好。如果你有更多的问题，请给我看看，让我知道。

来源

2010-08-06 10:21:26 IVlad

问题是不理解算法。我很了解它。问题不是有效的实现。有很多使用优先级队列。问题是我如何以O（| V |^2）的复杂度来实现它。 – 2010-08-06 10:44:13

寻找最低成本的边缘（ü，v），使得Ü是在U和v是在V-U，与优先级队列完成。更确切地说，优先级队列包含来自V-U的每个节点以及从v到当前树U的最低成本边缘。换句话说，队列正好包含| V-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)

来源

2010-08-06 11:59:31

你能写一点伪代码吗？ – 2010-08-06 12:29:45

当然。编辑我的答案。 – 2010-08-06 15:43:02

您可以通过成本的边缘进行排序，然后在成本的顺序重复的边缘，如果该边连接两个不同的子图使用边缘。

我有一个执行here。它按顺序（A，B，Cost）读取垂直数（N），边数（M）和边，然后输出边。这是Kruskal算法。

使用相同的输入可以找到带有堆的Prim算法的实现here。

来源

2010-08-06 13:50:25

Prim的MST算法在O（| V |^2）

回答

相关问题