algorithm - 图:计算包含节点的循环

Question

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

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

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

如果唯一的问题是循环被计算两次，我可以将结果减半，但我想每个循环只走一次。相同的算法可能适用于其他事物。

Answer 1

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

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

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

有关详细信息，请参阅 all possible paths problem