在给定源顶点的情况下，查找有向图中所有包含环的路径

Question

我遇到了解决这个问题的困难。我必须找到所有从源顶点s开始包含简单循环的路径。即，不允许重复，除了当循环重新加入路径时的单个重复顶点。

我知道如何使用DFS遍历来查找图中是否存在循环，但我找不到一种方法来使用它来查找所有从s开始的这样的路径。

例如，在这个图中：

        +->B-+
        |    v
s-->T-->A<---C
        |    ^
        +->D-+

从点s开始，可以正确地找到路径S-T-A-B-C-A。但是路径S-T-A-D-C-A将无法找到，因为DFS标记了顶点C为已访问。请问有人能给我提示如何解决这个问题吗？谢谢。

- Jubstuff

---

可能会有无限多个包含循环的路径...你能更具体地说明你正在寻找什么吗？ - templatetypedef

你可能是指不再访问相同顶点的路径。是这样吗？即使是这样，仍然可能有惊人数量的路径。所以你可能只想要最小的循环？将最小循环定义为其中任何成员子集中没有更短的循环。也许你想要所有的最小循环？ - Aaron McDaid

你的意思是所有包含一个简单环的简单路径，其中路径以s为起点？还有一个问题：您是否要求s在环中或不在环中？您的问题在最后一点上有点模糊，在某个地方您说“从s开始找到所有循环”。 - Aaron McDaid

可能仍将有许多循环。在我所涉及的所有网络中，如果您从一个节点开始并进行长时间的随机游走，几乎总会有一条回到起始节点的路线，在该路线上没有重复经过任何节点。这样的路径将比您的硬盘可以存储的还要多！ - Aaron McDaid

可能存在指数数量的循环。对于具有20条边左右的图，可以在合理的时间内枚举出所有循环。 - n. m.

Answer 1

这实际上是一种非常简单的算法，比深度优先搜索简单得多。您只需要在朴素递归搜索中枚举所有路径，记住不要在路径自我回路时进一步递归：

（这只是受Python启发的伪代码。希望足够清晰。）

 def find_paths_with_cycles(path_so_far):
       node_just_added = path_so_far.back()
       for neigh in out_neighbours(node_just_added):
           if neigh in path_so_far:
               # this is a cycle, just print it
               print path_so_far + [neigh]
           else:
               find_paths_with_cycles(path_so_far + [neigh])


 initial_path = list()
 initial_path.append(s)
 find_paths_with_cycles(initial_path)

- Aaron McDaid

---

漂亮简洁的代码。就性能而言，这个代码会只找到所有简单路径一次，还是可能会找到多次？ - Clement

@Clement，所有这样的路径只会被找到一次。但是可能仍然有很多这样的路径。例如，它会将S->A->B->X->Y->Z-X和S->B->A->X->Y->Z-X作为不同的路径找到，即使它们都包含相同的循环(X->Y->Z->X)并使用相同的节点(A和B)到达那里。唯一的区别是它们访问A和B的顺序。 - Aaron McDaid

此代码将无法检测出不以 path_so_far 变量开头的图中的循环。 - Naveen Dennis

@NaveenDennis，它将找到问题中要求的这样的循环。这不需要S在循环中。 - Aaron McDaid

Answer 2

这是垃圾回收算法中的一个常见问题。

在一次 .net 培训中，我学到了 .net 垃圾回收器通过在图形中启动两个指针来检测循环引用，其中一个指针的速度是另一个指针的两倍。如果快速前进的指针从后面追上了慢速的指针，那么就找到了一个循环引用。对于复杂的图形，这将更加复杂，但不需要为节点打标签。

- user180326

Answer 3

当你发现一个循环时，回到已标记的顶点并将它们取消标记。

假设你已经找到了SABCA并想要找到下一个循环。A是你的最终节点，你不应该取消标记它。回到C。C有另一条出边吗？没有，所以取消标记C并返回B。B有另一条出边吗？没有，取消标记B并返回A。A有另一条出边吗？有！有一条通向D的边。所以去那里，标记D，去到C 现在已经取消标记，然后到达A。在这里，你又找到了另一个循环。你再次回到A，但现在没有更多的路径可以导出A，所以你取消标记A并返回S。

- n. m.

Answer 4

我已经在C#中实现了Aaron的算法。

由于它使用IEnumerable，它是惰性枚举的，如果您只想找到第一个循环，则可以使用DirectedGraphHelper.FindSimpleCycles(s).First()：

public static class DirectedGraphHelper
{
    public static IEnumerable<Node[]> FindSimpleCycles(Node startNode)
    {
        return FindSimpleCyclesCore(new Stack<Node>(new[] { startNode }));
    }

    private static IEnumerable<Node[]> FindSimpleCyclesCore(Stack<Node> pathSoFar)
    {
        var nodeJustAdded = pathSoFar.Peek();
        foreach (var target in nodeJustAdded.Targets)
        {
            if (pathSoFar.Contains(target))
            {
                yield return pathSoFar.Reverse().Concat(new[] { target }).ToArray();
            }
            else
            {
                pathSoFar.Push(target);
                foreach (var simpleCycle in FindSimpleCyclesCore(pathSoFar))
                {
                    yield return simpleCycle;
                }
                pathSoFar.Pop();
            }
        }
    }
}

public class Node
{
    public string Id { get; private set; }
    public readonly List<Node> Targets = new List<Node>();

    public Node(string id)
    {
        this.Id = id;
    }
}

你可以像这样使用它：

class Program
{
    static void Main(string[] args)
    {
        var s = new Node("s");
        var t = new Node("t");
        var a = new Node("a");
        var b = new Node("b");
        var c = new Node("c");
        var d = new Node("d");

        s.Targets.Add(t);
        t.Targets.Add(a);
        a.Targets.AddRange(new[] { b, d });
        b.Targets.Add(c);
        c.Targets.Add(a);
        d.Targets.Add(c);

        foreach (var cycle in DirectedGraphHelper.FindSimpleCycles(s))
        {
            Console.WriteLine(string.Join(",", cycle.Select(n => n.Id)));
        }
        Console.Read();
    }
}

- Clement