График цикла обнаружения аваля

Я изучал граф, и я закончил свою рекурсивную реализацию в C ++ для определения, когда граф имеет цикл или нет, вот мой код:

bool Graph::dfsCyclic(unsigned vt, bool *visited, bool *beingVisited) {

beingVisited[vt] = true;
bool dfs = false;

for (list<unsigned>::const_iterator it = this->adjList[vt].begin(); it!= this->adjList[vt].end(); ++it) {
if (beingVisited[*it]) {
return true;
}

if (!visited[*it]) {
dfs = this->dfsCyclic(*it, visited, beingVisited);
}
}

visited[vt] = true;
beingVisited[vt] = false;
return dfs;
}

bool Graph::isCyclic() {
bool visited[this->v];
bool beingVisited[this->v];

for (unsigned i = 0; i < this->v; ++i) {
visited[i] = false;
beingVisited[i] = false;
}

for (unsigned i = 0; i < this->v; ++i) {
if (dfsCyclic(i, visited, beingVisited)) {
return true;
}
}

return false;
}

Я хотел бы знать, думаете ли вы, ребята, если это хорошая реализация. Я сделал несколько тестов, и он работал нормально. Я также хотел бы знать, как я мог сделать и ИТЕРАЦИОННУЮ версию этого кода, я пробовал, но у меня есть некоторые проблемы с этим. Заранее спасибо за помощь! Также есть ли в любом случае, я могу доказать правильность этого кода?

1

Решение

Задача ещё не решена.

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

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

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