0

I am implementing a simple version of Prim's algorithm using adjacency list using basic graph implementation idea.Here is my approach for this algorithm-

1.Pick an index.

2.Inside the Prims function,mark the index as visited.

3.If any adjacent vertex is not visited and cost of that vertex is less than mi(which is initialized as INF at the start of the function) then mi stores the cost and parent stores the index.

4.At the last adjacent vertex mi stores the smallest cost and parent stores the smallest cost index.

5.Again call the prims for parent vertex.

6.At last return the total cost.

But the problem in my approach is when I am comparing cost[v] with mi then it gives me an error cause I am comparing int with vector.I have tried using mi as a vector but then it gives me error in result section.My code is given below-

#include<bits/stdc++.h>
using namespace std;
#define mx 10005
#define INF 1000000007
vector<int>graph[mx],cost[mx];
int visited[mx]={0};
int result=0,parent;
int n,e,x,y,w,mi;

int prims(int u)
{
    mi=INF;
    visited[u]=1;
    for(int i=0;i<graph[u].size();++i)
    {
        int v=graph[u][i];
        if(visited[v]==0 and cost[v]<mi)
        {
            mi=cost[v];
            parent=v;
        }
        if(i==graph[u].size()-1)
        {
            result+=mi;
            prims(parent);
        }
    }
    return result;
}

int main()
{
    cin>>n>>e;
    for(int i=1;i<=e;++i)
    {
        cin>>x>>y>>w;
        graph[x].push_back(y);
        graph[y].push_back(x);
        cost[x].push_back(w);
        cost[y].push_back(w);
    }
    int src;cin>>src;
    int p=prims(src);
    cout<<p<<endl;

    return 0;
}
Some programmer dude
  • 400,186
  • 35
  • 402
  • 621
  • No, you implemented it wrong. You have to find an edge with the minimum weight connecting one of already visited nodes (not only the last one you've visited). So there's an example: edge 1-2 with cost 10 and edge 1-3 with cost 1, no other edges, you start from node 1, in that case you'll never pick edge 1-2, but you have to. – fas Mar 30 '20 at 04:48
  • No ,I belive that's why I use the last if condition.when I am in node 1.It checks all its adjacent vertices like 2 and 3.when it's in adj node 2 then it checks if it's cost is less than mi.if it does then mi stores the minimum value.Again if any other vertices has less cost then the mi is updated so as the parent.In your case,first it checks edge 1-2 and mi=10.then edge 1-3 mi updated to 1.From my code result only contains the last mi and parent the last minimum vertex –  Mar 30 '20 at 05:00
  • `vectorgraph[mx]` -- Why are you using non-standard C++ syntax, when you are using `std::vector` already? You use similar syntax here: `cost[mx];`. Arrays in C++ must have their sizes denoted by a constant expression, not a runtime variable's value. That should be `std::vector> graph(mx);` – PaulMcKenzie Mar 30 '20 at 05:08
  • @PaulMcKenzie Sinze `mx` is a macro that expands to an integer literal that's fine (syntactically and semantically, but still rather bad). – Some programmer dude Mar 30 '20 at 05:25
  • @ParthaPratimMazumder Please don't use online judge or competition site as a learning resource, all you learn from them are how to write *bad* code for such sites and such sites only. Take a few classes, get [a few good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282), and learn properly. – Some programmer dude Mar 30 '20 at 05:26
  • @Someprogrammerdude thanks,but I didn't get my answer though. –  Mar 30 '20 at 06:03

0 Answers0