CODEWITHSUNDEEP
c++algorithmbreadth-first-search
user553947
user553947

Reputation:

Problem in Breadth First Search

cin>>t;

while (t--)
{

    cin>>n;
    cin>>m;

    if (n==m)
        cout<<"0\n";
    else
    {
        //Breadth First Search Tree:
        queue <gnode*> gqueue;

        bft_data bft=bft_data();


        list<gnode>* gp;
        list<gnode>::iterator it;

        gp=_gfind(graph,n);// finds list containing gnode with n value
        gnode* st=gfind(gp,n),*tmp,*_st;//finds gnode with n value
        _st=st;

        bft.w[st->v]=0;
        bft.pn[st->v]=NULL;
        bft.c[st->v]=1;

        gqueue.push(st);

        while (!gqueue.empty())
        {
            st=gqueue.front();
            gqueue.pop();

            gp=_gfind(graph,st->v);

            it=(*gp).begin();
            for (++it;it!=(*gp).end();it++)//initialized with ++it to skip fist element of list
            {
                tmp=&(*it);
                // cout<<tmp->v<<"\n";
                //  getchar();
                if (bft.c[tmp->v]==0)
                {
                    bft.pn[tmp->v]=st;
                    bft.c[tmp->v]=1;
                    bft.w[tmp->v]=bft.w[st->v]+1;

                    gqueue.push(tmp);
                }
            }

        }


       if(bft.w[m]!=SIZE)
        cout<<bft.w[m]<<"\n";
        else
        cout<<"Impossible\n";
bft.~bft_data();
    }
}

This code snippet to calculate the distance b/w the node with value n and m by constructing bfs tree.But somehow bft tree constructed in first iteration of outer while loop retains its vlaue ,further iteration of while loop have no effect on the bft

here graph is of type vector<list<gnode>>

bfs is object of class bft_data:

class bft_data
{
public:
int w[SIZE],c[SIZE];
gnode* pn[SIZE];

bft_data()
{
    memset(w,SIZE,SIZE);
    memset(c,0,SIZE);
    memset(pn,NULL,SIZE);
}

 };

Upvotes: 0

Views: 897

Answers (1)

TonyK
TonyK

Reputation: 17124

I haven't looked through your first code extract, but the second extract might explain the problem: the third argument to memset is a byte count, so you must multiply it by the size of the array element:

memset(w,SIZE,SIZE * sizeof(int));
memset(c,0,SIZE * sizeof(int));
memset(pn,NULL,SIZE * sizeof (gnode*));

Upvotes: 1

Related Questions