为什么 prim 的算法需要距离数组？

Question

我对 Prim 的算法有一些疑问。

Prim算法可以找到MST。在一般实现中，它需要将所有节点初始化为 INF。但我不知道为什么需要这个初始化。

这是我的实现

#include<iostream>
#include<tuple>
#include<algorithm>
#include<vector>
using namespace std;
typedef tuple<int,int,int> ti;
int main(void)
{

ios::sync_with_stdio(0);
cin.tie(0);

bool vis[1005];
vector<pair<int,int>> vertex[1005];

int V,E;
int u,v,w;
int sum = 0;
int cnt = 0;
priority_queue<ti,vector<ti>,greater<ti>> pq;
cin >> V >> E;
for(int i = 0; i < E; i++)
{
    cin >> u >> v >> w;
    vertex[u].push_back({v,w});
    vertex[v].push_back({u,w});
}


for(auto i : vertex[1]){
    pq.push({i.second,1,i.first});
}
vis[1] = true; 

while(!pq.empty())
{
    tie(w,u,v) = pq.top(); pq.pop();
    if(vis[v]) continue;

    vis[v] = true;
    sum += w;
    cnt++;
    for(auto i : vertex[v]){
        if(!vis[i.first])
            pq.push({i.second,v,i.first});
    }

    if(cnt == V-1) break;
}
//   VlogV
cout << sum;
return 0;

请忽略缩进（代码粘贴错误）

在此代码中，您可以找到 MST 的总和。 O(VlogV)，我们还可以找到一些 Vertex Parent 节点 (vis[v] = true, pre[v] = u) 所以我们可以知道 MST 的顺序。

当我们不需要距离数组时，我们可以实现原始算法 O(VlogV)，在几乎情况下（不是在 MST 情况下）它总是比 Kruskal 快。我知道我错了，所以我想知道我错在哪里。

那么我们使用距离数组有什么原因吗？

Answer 1

您关于此算法在 O(Vlog(V)) 中有效的结论似乎是错误的。原因如下：

while(!pq.empty())              // executed |V| times
{
    tie(w,u,v) = pq.top(); 
    pq.pop();                   // log(|V|) for each pop operation
    if(vis[v]) continue;

    vis[v] = true;
    sum += w;
    cnt++;
    for(auto i : vertex[v]){   // check the vertices of edge v - |E| times in total
        if(!vis[i.first])
            pq.push({i.second,v,i.first});  // log(|V|) for each push operation
    }

    if(cnt == V-1) break;
}

首先请注意，您必须执行 while 循环 |V| 次，因为 pq 中存储了 |V| 个顶点。
但是，还要注意，您必须遍历以下行中的所有顶点：
for(auto i : vertex[v]) 因此总共需要 |E| 次操作。
请注意，push 和 pop 操作大约需要 |V| 次操作。
那我们有什么？
我们有 |V| 次迭代，每次迭代中有 log(|V|) 次 push/pop 次操作，这使得操作次数为 V * log(V) 次。
另一方面，我们总共有 |E| 次顶点迭代，并且在每个顶点迭代中有 log(|V|) 次推送操作，这使得操作数为 E * log(V)。

总之，我们有 V*log(V) + E*log(V) 个操作总数。在大多数情况下，V < E 假设一个连通图，因此时间复杂度可以表示为 O(E*log(V)).

因此，Prim's Algorithm 的时间复杂度不依赖于保持距离数组。不过，您必须进行上述迭代。

为什么 prim 的算法需要距离数组？

why prim`s algorithm needs distance array?

algorithm

graph-algorithm