Лучший алгоритм обнаружения циклов в ориентированном графе

Question

Какой самый эффективный алгоритм для обнаружения всех циклов в ориентированном графе?

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

Answer 1

То, как я это делаю, - это топологическая сортировка, подсчитывающая количество посещенных вершин. Если это число меньше общего числа вершин в группе обеспечения доступности баз данных, у вас есть цикл.

Answer 2

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length Мне больше всего нравится это решение специально для 4 длин:)

Также физик говорит, что ты должен сделать O (V ^ 2). Я считаю, что нам нужно только O (V) / O (V + E). Если граф подключен, DFS посетит все узлы. Если у графа есть связанные подграфы, то каждый раз, когда мы запускаем DFS на вершине этого подграфа, мы найдем связанные вершины и не будем рассматривать их для следующего запуска DFS. Поэтому возможность запуска для каждой вершины неверна.

Answer 3

Как вы сказали, у вас есть набор заданий, его нужно выполнять в определенном порядке. Topological sort с учетом необходимого вам порядка для планирования заданий (или для проблем с зависимостями, если это direct acyclic graph). Запустите dfs, сохраните список и начните добавлять узел в начале списка, и если вы встретили узел, который уже посещен Затем вы нашли цикл в данном графике.

Answer 4

Если график удовлетворяет этому свойству

|e| > |v| - 1

тогда график содержит хотя бы по циклу.