Количество узлов в цикле графа

Я пытаюсь найти количество узлов в цикле графа. Я использую рекурсию и DFS для вычисления количества узлов во всех циклах графа. Вот функция вычисления в C ++.

int iscyclic(int node,bool visited[],bool rec[],vector<int>g[])
{
if(!visited[node])
{
visited[node] = true;
rec[node] = true;
vector<int>::iterator it;
for(it=g[node].begin();it!=g[node].end();it++)
{
if(!visited[*it] && iscyclic(*it,visited,rec,g))
{
kount++;
}
else if(rec[*it])
kount++;
}
}
rec[node] = false;
return kount;
}

Visited а также rec по умолчанию для массива установлено значение false и kount был глобально установлен как 0, kount Предполагается рассчитать количество узлов в цикле ориентированного графа. Однако бывают случаи, когда ответ неверен. Пожалуйста, помогите. Я недавно начал изучать теорию графов.

1

Решение

Вы не должны делать это:

else if(rec[*it])
kount++;

Кроме того, вам нужно убедиться, что начальный узел (тот, с которым вы вызываете функцию) действительно является частью цикла.

Третье — вы возвращаетесь kcount как результат вашей функции, когда вы должны вернуть true или же false исходя из того, столкнулись ли вы с циклом в этой ветке или нет.

0

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

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