Реализация Graph DFS в C ++, проблема с указателями

Извините заранее, но некоторые имена переменных и тому подобные имеют странные имена, так как я не являюсь носителем английского языка, я также довольно новичок в программировании.

Итак, я делал проект с сортировкой топологий графиков и тому подобным, но я не могу заставить DFS работать, я знаю, что, возможно, я теряю данные из-за использования там указателей (?), Но я не буду использовать этот список смежности в моей программе в любом случае дальше. Проблема состоит в том, чтобы просто получить правильный результат, который в этом случае состоит в том, что вершина была введена (d []) и оставлена ​​(f []), но во время рекурсии мои указатели сходят с ума, иногда, когда я возвращаюсь в повторении (и, по-видимому, ничего еще бывает), я думаю, по крайней мере, потому что я впервые использую функцию отладки. Я сижу за этим уже около 8 часов (это не моя первая проблема, но мне удалось решить некоторые, поэтому код выглядит так некрасиво), и я сидел с этим отладчиком и не добился никакого прогресса в течение часа, поэтому я решил спросить, впервые пользуясь этим веб-сайтом, я надеюсь, что вы мне поможете, и когда я стану немного лучше, я обязательно верну услугу, вот код:

#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 [], который представляет собой таблицу, если целые числа, которые указывают, когда вершина была посещена, и f [] — таблица. когда вершина была взята из стека, просто упорядочив 1,2,3 …, проблема в том, что она разрывается посередине, иногда ей нравится 7/10, иногда просто 2/10, и, конечно, она разбивается. придется работать и для больших графиков. Указатели утеряны, и он пытается проверить Nowy [какое-то большое число там] и происходит сбой программы.

-2

Решение

Итак, я плохо использовал struct и допустил много ошибок, благодаря некоторым комментариям я решил использовать вектор векторов для прилежащей матрицы и вектор forward_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:

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;

}
0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector