Проблема в поиске по ширине - PullRequest
Новая
       1

Проблема в поиске по ширине

0 голосов
/ 28 декабря 2010 
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();
    }
}

Этот фрагмент кода для вычисления расстояния ч / б узла со значениями n и m путем построения дерева bfs. Но каким-то образом дерево bft, построенное в первой итерации внешнего цикла while, сохраняет свое значение, дальнейшая итерация цикла while не влияет на BFT

здесь график имеет тип vector<list<gnode>>

bfs является объектом класса 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);
}

 };

1 Ответ

1 голос
/ 28 декабря 2010

Я не просматривал ваш первый фрагмент кода, но второй фрагмент может объяснить проблему: третий аргумент memset - это число байтов, поэтому вы должны умножить его на размер элемента массива: 

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