图：包含节点的计数周期

我想计算非有向图中节点所属的周期数。图：包含节点的计数周期

这些周期可以共享它们之间的节点。这两个将计数：

A -> B -> A 
A -> B -> C -> A

我一直在尝试我的手一段时间了。我目前的实施计数周期两次：单向行走，然后是另一行程。它可能有其他的错误。

这是递归函数来找到路径（从countCycles包装）：

function countPaths(current, destination, visited: set) -> 
    if visited.contains(current): 
     if current is destination and visited.size > 2: 
      return 1 
     else 
      return 0 

    visited.add(current) 
    count = 0 

    for each neighbor of current: 
     count += countPaths(neighbor, destination) 

    visited.remove(current) 
    return count

如果唯一的问题是，周期计数两次，我可以减半的结果，但我想走路每个只循环一次。相同的算法可能对其他方面有好处。

来源

2014-06-17 slezica

最后一段是一个真正的WTF。 –

如果是给我的话，我会花上一个小时。我的老板不会那么高兴。 – slezica

我们不知道哪里出了问题，向我们展示您当前的（非工作）解决方案。 –

这是一个含糊不清的问题。如果一个图有循环，它可以有无数的路径。

一般来说，所有可能的路径问题都是NP困难的，即使对于小图也可能有非常多的路径。

一般策略是将广度优先搜索与队列或某种其他机制相结合，该机制仅存储当前分支的访问节点。

欲了解更多信息，请参阅all possible paths problem

来源

2014-06-17 18:14:52

伪代码暗示他只考虑没有重复节点的循环---一个简单的循环。 – Billiska

对，这就是为什么我建议使用像队列这样的数据结构来记住当前分支上已访问过哪些节点。 –

-1

这是我O(VE^2)算法，其中V是顶点的数目和E是边数。这不是一个递归算法。

我将从1到V的顶点编号。其中1将始终是问题中必须出现在计数周期中的顶点。

草图如下：我将计算所有顶点的较小子集内的循环，并逐渐考虑更多顶点。也就是说，从集{1,2,3}

启动你需要的东西来维持：

m[x][y]大小V x V记住你是否已通过顶点1发现了一个简单的路径的布尔表有x 和y以及路径的终点。通过简单的路径我的意思是路径不重复顶点。
周期的计数这就是答案

让我们开始算法。

(1) Initialize table `m` for the base case of set `{1,2,3}`. I'll assume you can do this. 
(2) For each time you add a vertex `A` into consideration, do the following: 

    (2.1) Update the cycle count 

      For every (B,C) pair of vertices that are both adjacent to vertex A 
      [Meaning we have a path (B,A,C)] 
      that the table m has an entry of path (B,...,1,...,C) 

      We can deduce that there is a simple cycle (A,B,...,1,...C,A). 
      count it. 

    (2.2) Update the table m 

      For every vertex X that is adjacent to A and there is a path (X,...,1,...,Y) 
      Remember that there is a path (A,...,1,...,Y) into table m.

算法描述完成。

复杂性分析：外环经过每个顶点，因此乘以因子V。步骤(2.1)经过与A相邻的每一对边，因此乘以因子E^2。整体O(VE^2)。

来源

2014-06-17 18:51:47 Billiska

那么，为什么-1？我的回答错误或格式不正确？ – Billiska

我无法改进OP中的算法，因此它不会遍历相同的周期两次。所以，我给出了一个不同的算法，它不会遍历同一个循环两次。我不认为这是脱离主题。 – Billiska

图：包含节点的计数周期

回答

相关问题