2

假设图中的所有边权重都是 1 到 |V| 范围内的整数。你能让 Prim 的算法运行多快？如果对于某个常数 W，边权重是 1 到 W 范围内的整数怎么办？

MST-PRIM(G,w,r)
1.  for each u∈  G.V
2.       u.key=inf
3.       u.π=NIL
4.  r.key=0
5.  Q=G.V
6.  while Q != Ø 
7.     u=EXTRACT-MIN(Q)
8.     for each v ∈  G.Adj[u]
9.         if v∈  Q and w(u,v)<v.key
10.          v. π=u
11.          v.key=w(u,v)

根据我的教科书：

Prim 算法的运行时间取决于我们如何实现最小优先级队列 Q。如果我们将 Q 实现为二进制最小堆，我们可以使用 BUILD-MIN-HEAP 过程在 O(V) 中执行第 1-5 行时间。while 循环的主体执行 |V| 次，并且由于每个 EXTRACT-MIN 操作需要 O(lg V) 时间，所以对 EXTRACT-MIN 的所有调用的总时间为 O(VlgV)。第 8-11 行中的 for 循环总共执行 O(E) 次，因为所有邻接列表的长度之和为 2|E|。在 for 循环中，我们可以在第 9 行中通过为每个顶点保留一个位来判断它是否在 Q 中，并在顶点从 Q 中删除时更新该位，从而在恒定时间内实现对 Q 中的成员资格的测试。第 11 行的赋值涉及对最小堆的隐式 DECREASE-KEY 操作，二进制最小堆在 O(lg V) 时间内支持该操作。因此，

第 1-4 行需要 O(V) 时间。我已经阅读了一些解释为什么 BUILD-MIN-HEAP 过程需要线性时间，但我还没有理解它们。你能解释一下为什么 MIN-HEAP 过程的时间复杂度是 O(V) 吗？

此外，我认为在最小堆中，最小元素位于根部。那么，为什么每个 EXTRACT-MIN 操作都需要 O(lg V) 时间？

然后，for 循环执行 O(Σ_{v in VG} deg(v)) 次，对吧？你能解释一下为什么 Σ_{v in VG} deg(v)=2E 吗？

此外，如果我们知道对于某个常数 W，边权重是从 1 到 W 范围内的整数，会有什么不同？

编辑：

假设图中的所有边权重都是 1 到 |V| 范围内的整数。你能让 Prim 的算法运行多快？

我们可以对上述算法进行哪些更改，以使 Prim 算法尽可能快地运行？

4

1 回答 1

3

答案-1

第一个问题可以在 stackoverflow from- this question中找到。

答案-2

提取最小操作在 O(1) 时间内从根中获取最小元素，但与此同时，我们需要执行使下一个提取最小操作在 O(1) 时间内提供最小元素的操作。我们做什么？我们只是将根元素与最右边的叶节点交换，然后删除该叶节点并堆积根，这可能会向下渗透到叶节点，这意味着 O(logn) 复杂度。（如 2^h=n 然后 h=log2(n)）。

答案-3

对于无向图

现在为什么是2E。好的！每个节点都有一些连接到它的边缘。（如果没有连接，那么它的度数为零）。现在节点的度数为 n 意味着它有 n 条边连接到它。现在让我们举个例子

1---2
|  /
| /
3
1 has degree=2
2 has degree=2
3 has degree=2
-+-+-+-+-+-+-+-
so sum(deg(v))=2+2+2=6= 2*(no of edges);

为什么这样？您可以考虑将这种情况建模为握手 b/2 朋友。每个节点表示朋友，每条边表示握手。如果你和 B 握手，那么 B 也会和你握手。所以每个握手（边缘）被节点（朋友）考虑两次。

注意：对于有向图，结果将等于E

答案-4

这些链接已经解释了它。检查这个希望一切都会清楚

1.链接1

2.链接2

让我们在这里说清楚。算法是什么——在 cormen 中是这样给出的——

MST-PRIM(G, w, r)
 1  for each u ∈ V [G]  ~~~~~~~~~> O(V)
 2       do key[u] ← ∞
 3          π[u] ← NIL
 4  key[r] ← 0
 5   Q ← V [G]          ~~~~~~~~~> If binary min-heap used then heapification's comlexity is O(V)
 6   while Q ≠ Ø        ~~~~~~~~~> Executed |V| times
 7       do u ← EXTRACT-MIN(Q)~~~> O(logV) in binary heap
 8          for each v ∈ Adj[u] ~~~> For each vertex the degree of that vertex times it will loop. So total O(E) times
 9              do if v ∈ Q and w(u, v) < key[v]
10                    then π[v] ← u
11                         key[v] ← w(u, v)~~~> decrease key operation in min-heap(binary) O(logV) times.

所以总复杂度= O(V)+O(VlogV)+O(ElogV) = O((V+E)logV) //VlogV支配V

现在，如果所有边缘权重都在 1 到 |V| 的范围内 那么我们可以只取一个列表数组 A[1..|V|]。现在假设边权重为 1(E1)、3(E2)、2(E3)、5(E4)、7(E5)、3(E6)，并且有 7 个顶点和 6 个边。

最初的列表数组

A  [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
    0   1   2   3   4   5   6   7

现在您应用计数排序的方法 - 对于每个边缘权重，您将该边缘放在相应的数组位置，例如

现在遇到边缘 E1 后，数组将是

A  [ ] [E1] [ ] [ ] [ ] [ ]  [ ] [ ]
    0    1    2  3   4    5   6   7

然后是边缘 E2

A  [ ] [E1] [ ] [E2] [ ] [ ] [ ] [ ]
    0   1    2   3    4   5   6   7

所以在遍历所有边之后你得到

                  E6
                  | 
A  [ ] [E1] [E3] [E2] [ ] [E4] [ ] [E5]
    0    1    2    3   4    5   6   7

可能现在您可以理解为什么提到|V|的某些答案了 列出或 |W| 此图中的列表。

现在你可以在 O(V) 时间内从数组中得到所有最小值。通常对于大范围的权重，堆数据结构用于存储边。

但是，在这种情况下，权重是 1 .. |V| 所以你可以简单地将边缘存储在|V|中 单独的列表，一个用于权重为 1 到 |V| 的边。

要找到权重最低的边，只需从第一个列表中取一个，除非它是空的，在这种情况下，您从第二个列表中取一个边。

从列表中访问和删除元素是 O(1)，您只需从列表中删除最上面的元素。所以 Prim 的算法将以 O(V*W+E) 运行。

所以如果 W=O(V) 那么它运行在 O(V^2+E)

如果权重在 1..W 范围内（W=O(1) 常数），那么复杂度同样将是 O(V*W+E)。〜O（V + E）。

伪代码

在 C 中

结构边缘 { int u,v,w; } 结构列表节点 { 边 e; 结构列表节点*下一个；}

struct listnode ** A;
A=malloc(sizeof(struct list *)*N);
Intilally all of A[i]=NULL;

A[i]=malloc(sizeof(struct listnode),1);
(*A[i]).e.u=..
(*A[i]).e.v=..
(*A[i]).e.w=..

 create the array of lists don't insert anythiing.
 Then just select a vertex say s
 keep an array visisted[1..|V|]
 visited[s]=true;
 no_of_visited=1;
 recently_visted=s;
 while(all nodes are not visited)   //no_of_visited!=|V|
 {
    insert all edges from s-x (adjacent) in the array of lists.(s is recently visited) provided x is not visited
    get the minimum weight one
    if it is u-w and w is not visited
    {
        visited[w]=true;
        no_of_visited++;
        recently_visited=w;
        insert(u,w) in spanning tree
    }

}

复杂性分析

算法：

让我们的权重在 1..|W| 范围内

Then just select a vertex say s ~~~~~~~~~~> O(1)
 //keep an array visisted[1..|W|]
 for i=1 to |W| 
     visited[i]=false;   ~~~~~~~~~~> O(|W|) 
 visited[s]=true; ~~~~~~~~~~> O(1)
 no_of_visited=1; ~~~~~~~~~~> O(1)
 recently_visted=s; ~~~~~~~~~~~ O(1)
 while(all nodes are not visited) ~~~~~O(V)  //no_of_visited!=|W|
 {
    insert all edges from s-x (adjacent) in the array of lists.(s is recently visited) provided x is not visited ~~~~~O(|E|) altogether
    get the minimum weight one          ~~~~~O(|W|) 
    if it is u-w and w is not visited   --O(1)
    {
        visited[w]=true;               
        no_of_visited++;
        recently_visited=w;
        insert(u,w) in spanning tree    --O(1)
    }

}

所以复杂度=O(|W|)+O(|W|.|V|)+O(|E|)~O(E+V W) 当W=O(V)时T(V,E)= O(E+VV )=O(E+V^2)

于 2015-04-13T13:36:36.633 回答