在 C++ 中实现图形 DFS，指针问题

Question

抱歉，有些变量名之类的名字很奇怪，因为我的母语不是英语，我对编程也很陌生。

所以，我正在做一个具有图形拓扑排序和类似功能的项目，但我无法让 DFS 工作，我知道我可能会丢失数据，因为其中使用了指针（？），但我无论如何都不会在我的程序中进一步使用这个邻接列表。问题只是为了得到正确的结果，在这种情况下是当顶点被输入 (d[]) 和离开 (f[]) 但是在递归中我的指针变得疯狂，有时当我返回递归时（显然什么都没有否则会发生），我认为至少因为这是我第一次使用调试功能。我已经坐了大约 8 个小时（这不是我的第一个问题，但我设法解决了一些问题，这就是代码看起来如此丑陋的原因），我坐在这个调试器上，一个多小时内没有取得任何进展，所以我决定问一下，我第一次使用这个网站，希望你能帮助我，等我好一点我一定会return帮个忙，这里是代码：

#include <iostream>
#include <cstdlib>
#include <time.h>
struct m_sasiedztwa
{
    int s;
    int** m;
    m_sasiedztwa(int a,float b) : s(a)
    {
        m = new int*[s];
        for(int i = 0; i < s; ++i)  m[i] = new int[s];
        for(int j=0; j<s; ++j)
            for(int k=0; k<s; ++k) if(j!=k) m[j][k]=((rand()%100)>(100*b))? 0 : 1; else m[j][k]=0;

    }
    ~m_sasiedztwa()
    {
        delete[] m;
    }
};
struct lista
{
    int key;
    lista *next;
};
struct l_nast
{
    int s;
    lista** arr;
    l_nast(int** m, int a) : s(a)
    {
        lista *curr,*prev;
        arr = new lista*[s];
        for(int i=0;i<s;++i)
        {
            arr[i] = new lista;
            curr = arr[i];
            prev=curr;
            prev->key=-1;
            for(int j=0;j<s;++j)
            {
                if(m[i][j]==1) {curr->next= new lista;curr->key=j;prev=curr;curr=curr->next;}

            }
            prev->next=nullptr;
        }

    }

~l_nast() {delete[] arr;}
};


//Here is the issue

bool *Nowy;
int c;
int* d,*f;
void DFS(int j,l_nast l_a)
{

            Nowy[j]=false;
            d[j]=c++;
            std::cout<<"Am I here yet..."<<j<<" "<<c<<std::endl;
                while((l_a.arr[j]!=nullptr)&&(l_a.arr[j]->key!=-1))
                {
                    std::cout<<"checking "<<(l_a.arr[j]->key)<<"...\n";
                    if(Nowy[l_a.arr[j]->key])
                    {

                    DFS(l_a.arr[j]->key,l_a);

                    }

                    if(l_a.arr[j]->next!=nullptr)                               //And I think this may be the problem, but I honestly don't know
                        l_a.arr[j]=l_a.arr[j]->next;
                            else break;
                }

            f[j]=c++;std::cout<<"Yohoo!"<<j<<" "<<c<<std::endl;

}




//Untill there

using namespace std;



int main()
{
    srand (time(NULL));
    for(int q=5; q<6; q+=5)
    {

        m_sasiedztwa a = m_sasiedztwa(q, 0.2);
        m_sasiedztwa b = m_sasiedztwa(q, 0.4);

        l_nast l_a = l_nast(a.m,q);
        l_nast l_b = l_nast(b.m,q);
      /*
           for(int i=0; i<q; ++i)
            {
                for(int j=0; j<q; ++j)
                {
                    cout << a.m[i][j] << " ";
                }
                cout<<endl;
            }
            cout<<endl;
*/

        Nowy = new bool [q];
        d = new int [q];
        f = new int [q];
        c=0;
    for (int i = 0; i < q; i++)
        Nowy[i] = true;
/*for(int qq=0;qq<q;qq++)
  while((l_a.arr[qq]!=nullptr))
  {
      cout<<l_a.arr[qq]->key<<endl;
      l_a.arr[qq]=l_a.arr[qq]->next;

  }
*/

        for(int j=0;j<q;j++)
        {

            if(Nowy[j]) DFS(j,l_a);

        }



        a.~m_sasiedztwa();
        b.~m_sasiedztwa();

        l_a.~l_nast();
        l_b.~l_nast();
    }

    return 0;
}

正如我所说，它并不漂亮，很抱歉打扰你，我再次需要帮助的是让函数 DFS 正确地得到 d[] 的结果，这是一个 table if 整数，表示顶点何时被访问，并且 f[] - table 当从堆栈中取出顶点时，只需排序 1,2,3...，问题是 - 它在中间中断，有时它确实像 7/10有时只有 2/10 就会中断，当然，它也必须适用于更大的图形。指针丢失，它试图检查 Nowy[那里有一些大数字] 和程序崩溃。

Answer 1

所以，我错误地使用了 struct 并犯了很多错误，多亏了一些评论，我决定使用 vector of vectors 作为 adj 矩阵，使用 forward_list 的 vector 作为 adj list 这是改变的地方 m_sasiedztwa结构

struct m_sasiedztwa
{
    int s;
    std::vector<std::vector<int>> m;
    m_sasiedztwa(int a,float b) : s(a), m(s, std::vector<int>(s,0))
    {
        for(int j=0; j<s; ++j)
            for(int k=0; k<s; ++k)
                if(j!=k)
                    m[j][k]=((rand()%100)>(100*b))? 0 : 1;
     }
};

l_nast 结构：

struct l_nast
{
    int s;
    std::vector<std::forward_list<int>> arr;
    l_nast(std::vector<std::vector<int>> m, int a) : s(a), arr(s)
    {
        for(int i=0;i<s;++i)
        {
            auto it = arr[i].before_begin();
            for(int j=0;j<s;++j)
            {
                if(m[i][j]==1) {it = arr[i].emplace_after(it,j);}

            }
        }

    }

};

和 DFS：

void DFS(int j,l_nast l_a)
{

            Nowy[j]=false;
            d[j]=c++;
            std::cout<<"Visiting "<<j<<"as "<<c<<std::endl;
        auto x=l_a.arr[j].begin();

        for(auto& x: l_a.arr[j])
        {
                    if(Nowy[x])
                    {

                    DFS(x,l_a);

                    }

        }
            f[j]=c++;std::cout<<"Leaving "<<j<<"as "<<c<<std::endl;

}

在 C++ 中实现图形 DFS，指针问题

Implementing a Graph DFS in C++, pointers issue

c++

pointers

graph

depth-first-search