我正在尝试查找图形循环中的节点数。我正在使用递归和 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
应该计算有向图循环中的节点数。但是在某些情况下答案是错误的。请帮忙。我最近开始学习图论。
最佳答案
你不应该这样做:
else if(rec[*it])
kount++;
此外,您需要确保起始节点(您调用函数的节点)确实是循环的一部分。
第三件事 - 你返回 kcount
作为你的函数的结果,当你实际上应该返回 true
或 false
根据你是否是否在该分支遇到循环。
关于c++ - 图的循环中的节点数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38811827/