алгоритм — поиск в глубину (C ++)

Я создал класс, который содержит вектор связанных списков. Каждый связанный список представляет собой вершину в моем графике. Узлы, связанные с моими связанными списками, считаются ребрами между этими вершинами. Я пытаюсь создать функцию DFS для своего графика, но у меня проблемы с настройкой цветов моих вершин. Я понимаю, что в моем коде много проблем, но я пытаюсь решить одну из них. Моя функция DFSit () заканчивается бесконечным циклом, потому что атрибуту цвета для моего списка фактически не присваивается значение «серый». Есть идеи, почему это будет?

void Graph::DFS()
{
int i = 0;
while (i != myvector.size())
{

DFSit(myvector[i], myvector[i].val);
myvector[i].color = "black";
i++;
}
}

void Graph::DFSit(AdjList x, int root)
{
if (x.color == "white")
{
cout << "tree edge ( " << root << "," << x.val << ") " << endl;
}
if (x.color == "gray")
{
cout << "Back Edge ( " << root << "," << x.val << ") " << endl;
return;
}

x.color = "gray";

AdjNode *temp = new AdjNode();
temp = x.front;
int i = 0;
int value;
while (temp != NULL)
{
value = temp->getValue();
while (i != myvector.size())
{
if (value == myvector[i].val)
{
DFSit(myvector[i], root);
}
i++;
}
temp = temp->next;
}

}

3

Решение

Как правило, правильная реализация процедуры DFS выполняется с помощью стека, но это также может работать.
Я думаю, что вы красите узел AdjList x и эта раскраска не спасает, потому что вы передаете ее по значению val, а не ref.
попробуйте изменить void Graph::DFSit(AdjList x, int root) в void Graph::DFSit(AdjList& x, int root)

2

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

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

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