Prim算法的运行时间

Question

假设图中的所有边权都是从1到x的整数。你能让Prim的算法运行多快？如果边权值是从1到W的整数，对于一些常数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实现为二进制最小堆，我们可以使用构建最小堆过程在O(V)时间内执行第1-5行。while循环的主体执行x-V\x次数，由于每个提取-MIN操作都需要O(lg - V)时间，所以所有提取-MIN调用的总时间为O(VlgV)。第8-11行中的for-循环总共执行O(E)次，因为所有邻接列表的长度之和都是2\E。在for -循环中，我们可以在固定时间内实现第9行中Q中的成员资格测试，方法是为每个顶点保留一个比特，以说明它是否在Q中，并在从Q中删除顶点时更新该位。第11行中的赋值涉及到对最小堆的隐式减少键操作，二进制的min-堆在O(lg V)时间内支持该操作。因此，Prim算法的总时间为O(V lg V+E lg V)=O(E lg V)。

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

此外，我认为在最小堆中，最小元素在根处.那么，为什么每次提取-MIN操作都需要O(lg V)时间？

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

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

编辑

假设图中的所有边权都是从1到x的整数。你能让Prim的算法运行多快？

我们可以在上面的算法中改变什么，这样Prim的算法就能运行得越快越好？

Answer 1

答案-1

第一个问题可以在- this question的堆栈溢出中找到。

回答-2

提取min操作在O(1)时间内从根获取最小元素，但同时我们需要执行操作，使下一次提取min操作在O(1)时间内给出min元素。我们该怎么办？我们只需将根元素与最右边的叶节点交换，然后删除该叶节点，并将可能从新根向下渗透到叶节点的根重新化，这就意味着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.link1

2.link2

我们在这里说清楚。算法是什么?在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.

因此，总comlexity= O(V)+O(VlogV)+O(ElogV) = O((V+E)logV) //VlogV占主导地位。

现在，如果所有的边权值都在1假设边权为1(E1),3(E2),2(E3),5(E4),7(E5)，3(E6)，有7个顶点和6个边。

列表数组

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

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

现在，在encounterng边缘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

也许现在你可以理解为什么会有人从这个图表中提到了一些关于维维列表或维维列表的答案。 现在你可以在O(V)时间内从数组中得到所有的最小值。通常，对于大范围的权重，堆数据结构是用来存储边缘。

然而，在这种情况下，权重不是1 ..您可以简单地将这些边存储在单独的列表中，其中一个用于权重为1的边。

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

从列表中访问和删除元素是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.

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)
    }

}

因此，当complexity=O(V)和T(V，E)= O(E+V_V)=O(E+V^2)时，当W=O(V) =O(E+V_V)=O(E+V^2)时，W=O(W=O(V)，E)=O(E+V_V)=O(E+V^2)。