why prim`s algorithm needs distance array?

Question

I have some questions about Prim`s algorithm.

Prim algorithms can find MST. In general implementation, It needs initialize all Nodes as INF. but i don`t know why this initialize needs.

Here is my implementation

#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;    

plz ignore indentation (code paste error)

In this code, you can find sum of the MST. O(VlogV), Also we can find some Vertex Parent node (vis[v] = true, pre[v] = u) so we can know order of MST.

When we don`t need distance array, we can implement prim algorithm O(VlogV), In almost case(not in MST case) it always faster than Kruskal. I know I'm something wrong, so i want to know what point I am wrong.

So is there any reason why we use distance array??

Answer 1

Your conclusion that this algorithm works in O(Vlog(V)) seems to be wrong. Here is why:

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

First of all notice that, you have to implement the while loop |V| times, since there are |V| number of vertices stored in the pq.
However, also notice that you have to traverse all the vertices in the line:
for(auto i : vertex[v]) Therefore it takes |E| number of operations in total.
Notice that push and pop operations takes |V| number of operations for each approximately.
So what do we have?
We have |V| many iterations and log(|V|) number of push/pop operations in each iteration, which makes V * log(V) number of operations.
On the other hand, we have |E| number of vertex iteration in total, and log(|V|) number of push operation in each vertex iteration, which makes E * log(V) number of operations.

In conclusion, we have V*log(V) + E*log(V) total number of operations. In most cases, V < E assuming a connected graph, therefore time complexity can be shown as O(E*log(V)).

So, time complexity of Prim's Algorithm doesn't depend on keeping a distance array. Still, you have to make the iterations mentioned above.