问题如题所示,图形以邻接表形式给出。我的方法是在任何一个顶点调用 DFS,每当我在 DFS 递归步骤中遇到访问的顶点时,我都会从 0 开始递增全局变量的计数器并且不为该访问的顶点调用 DFS(正如我们通常所做的那样)。这行得通吗,我想对吗?我还没有在互联网上找到任何相关文章来了解无向图中的#Number of cycles。
详细说明:我的意思是使用简单的 DFS 方法。虽然我们在遇到访问顶点的递归步骤中什么都不做,但我会针对这种情况增加 counter
全局变量值。我这样做是因为每当我遇到一个已访问的顶点时,都意味着我正在完成一个循环。我声称:图中的每个循环在任何 DFS 运行中只遇到一次(至少一次)。我的说法是否正确?
编辑:没有后缘
最佳答案
我很抱歉发布我的答案本身的答案,只是为了那些将来有类似疑问的人:我发现我会多余地计算很多周期,例如:-
A
/ \
B ----- C
\ /
D
从 A->B->C->D 开始 DFS 我得到循环 C-B-D 计数两次。我还了解到在无向图中查找所有循环的问题是 np-hard。运气不好:'(
关于algorithm - 无向图中的循环数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43557934/