1

问题正如标题所暗示的那样，图表以邻接表形式给出。我的方法是在任何一个顶点中调用 DFS，每当我在 DFS 递归步骤中遇到访问的顶点时，我都会从 0 开始递增全局变量的计数器，并且不为该访问的顶点调用 DFS（就像我们通常所做的那样）。这行得通吗，我想对了吗？我也没有在互联网上找到任何相关文章来了解#Number of Cycles in undirected graph。

阐述：我的意思是使用简单的 DFS 方法。虽然我们在遇到访问顶点的递归步骤中什么都不做，但我增加了counter这种情况下的全局变量值。我这样做是因为每当我遇到访问过的顶点时，都意味着我正在完成一个循环。我声称：在任何 DFS 运行中，图中的每个循环都只会遇到一次（至少和最多一次）。我的说法正确吗？

编辑：没有后边缘

4

1 回答 1

2

我很抱歉发布我的答案本身的答案，只是为了那些将来有类似疑问的人：我发现我会重复计算许多周期，例如：- 

    A 
  /   \
B ----- C
  \   /
    D

从 A->B->C->DI 开始 DFS 使循环 CBD 计数两次。我还了解到在无向图中查找所有循环的问题是 np-hard。厄运 ：'（

于 2017-04-22T10:35:33.120 回答