图:计算包含节点的周期数

Question

我想计算一个无向图中的节点所属的圈数。

这些循环可以在它们之间共享节点。这两个都算数：

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

我已经试了好一阵子了。我目前的实现计算了两次周期:一种方式遍历它们，然后另一种方式。它可能还有其他的bug。

这是用于查找路径的递归函数(从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

如果唯一的问题是周期被计算两次，我可以将结果减半，但我希望每个周期只走一次。同样的算法可能对其他东西也有好处。

Answer 1

这是一个模棱两可的问题。如果一个图有圈，那么它可以有无限多条路径。

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

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

有关更多信息，请参阅all possible paths problem

Answer 2

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

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

草图是:我将计算所有顶点的较小子集内的周期，并逐渐添加更多的顶点。也就是说，从集合{1,2,3}开始

你需要维护的东西：

1. m[x][y]一个大小为V x V的布尔表，记住您是否发现了一条通过顶点1的简单路径，该路径具有x和y以及该路径的端点。我所说的简单路径指的是不重复循环的vertices.
2. the计数的路径，这就是答案

让我们开始这个算法。

(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)。