Graph：包含节点的循环计数

Question

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

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难的，即使对于小图也可能有非常多的路径。

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