Найти все пути с циклами в ориентированном графе, учитывая исходную вершину

Question

У меня проблемы с решением этой проблемы. Я должен найти все простые пути, начиная с исходной вершины s , содержащей простой цикл в ориентированном графе. Т.е. повторы не допускаются, за исключением, конечно, для одной повторяющейся вершины, где цикл возвращается на путь.

Я знаю, как использовать посещение DFS, чтобы определить, есть ли на графике циклы, но я не могу найти способ использовать его, чтобы найти все такие пути, начиная с s .

Например, на этом графике

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

Начиная с s, путь S-T-A-B-C-A будет найден правильно. Но путь S-T-A-D-C-A не будет найден, поскольку вершина C помечена как Посещенная DFS.

Может кто-нибудь подсказать мне, как решить эту проблему? Спасибо

Answer 1

Это на самом деле довольно простой алгоритм, более простой, чем DFS.Вы просто перечисляете все пути в наивном рекурсивном поиске, помня о том, чтобы больше не повторять его в любое время, когда путь возвращается к самому себе:

(Это просто вдохновленный 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)

Answer 2

Я реализовал алгоритм Аарона в C #.

Поскольку он использует 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();
    }
}

Answer 3

Когда вы найдете цикл, вернитесь назад и снимите отметки с отмеченных вершин, когда вы проходите мимо них.

Предположим, вы нашли SABCA и хотите найти следующий цикл. A - ваш последний узел, вы не должны его отмечать. Вернитесь к C. Есть ли еще один край, выходящий из C? Нет, поэтому снимите отметку C и вернитесь к B. Есть ли еще один край, выходящий из B? Нет, снимите отметку B и вернитесь к A. Есть ли еще один край, выходящий из A? Да! есть один, который идет к D. Итак, идите туда, пометьте D, перейдите к C , который теперь не отмечен , затем к A. Здесь вы нашли другой цикл. Вы снова возвращаетесь к A, но теперь больше нет путей, ведущих из A, поэтому вы снимаете отметку с A и возвращаетесь к S.

Answer 4

Это общая проблема для алгоритмов сборки мусора.

Во время обучения .net я узнал, что сборщик мусора .net обнаруживает циклы, начиная с двух указателей на графике, один из которых движется вдвое быстрее, чем другой.Если быстро продвигающийся сзади сталкивается с медленным, вы нашли цикл.Он будет более сложным для сложных графов, но будет работать без маркировки узлов.