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

Алгоритм сильно связанных компонентов Тарьяна имеет O(|E| + |V|) временную сложность.

Для других алгоритмов см. Сильно связанные компоненты в Википедии.

Учитывая, что это расписание заданий, я подозреваю, что в какой-то момент вы собираетесь отсортировать их в соответствии с предлагаемым порядком выполнения.

В этом случае реализация топологической сортировки в любом случае может обнаруживать циклы. UNIX tsort определенно делает. Я думаю, что, вероятно, поэтому более эффективно обнаруживать циклы одновременно с сортировкой, а не на отдельном этапе.

Таким образом, вопрос может заключаться в том, «как мне наиболее эффективно выполнять сортировку», а не «как мне наиболее эффективно обнаруживать петли». На что ответ, вероятно, будет «использовать библиотеку», но в противном случае следующая статья в Википедии:

http://en.wikipedia.org/wiki/Topological_sorting

содержит псевдокод для одного алгоритма и краткое описание другого от Тарьяна. Оба имеют O(|V| + |E|) временную сложность.

Согласно лемме 22.11 из Кормен и др., Введение в алгоритмы (CLRS):

Ориентированный граф G является ацикличным тогда и только тогда, когда поиск G в глубину не дает обратных ребер.

Об этом упоминалось в нескольких ответах; здесь я также приведу пример кода, основанный на главе 22 CLRS. Пример графика проиллюстрирован ниже.

Псевдокод CLRS для поиска в глубину гласит:

В примере, показанном на рис. 22.4 CLRS, граф состоит из двух деревьев DFS: одно состоит из узлов u, v, x и y, а другой из узлов w и z. Каждое дерево содержит один задний край: один от x до v, а другой от z до z (само- петля).

Ключевая реализация состоит в том, что задний край встречается, когда в функции DFS-VISIT при итерации по соседям v из u встречается узел с цветом GRAY.

Следующий код Python представляет собой адаптацию псевдокода CLRS с добавленным предложением if, которое обнаруживает циклы:

import collections


class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.adj = Graph._build_adjacency_list(edges)

    @staticmethod
    def _build_adjacency_list(edges):
        adj = collections.defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
        return adj


def dfs(G):
    discovered = set()
    finished = set()

    for u in G.adj:
        if u not in discovered and u not in finished:
            discovered, finished = dfs_visit(G, u, discovered, finished)


def dfs_visit(G, u, discovered, finished):
    discovered.add(u)

    for v in G.adj[u]:
        # Detect cycles
        if v in discovered:
            print(f"Cycle detected: found a back edge from {u} to {v}.")

        # Recurse into DFS tree
        if v not in finished:
            dfs_visit(G, v, discovered, finished)

    discovered.remove(u)
    finished.add(u)

    return discovered, finished


if __name__ == "__main__":
    G = Graph([
        ('u', 'v'),
        ('u', 'x'),
        ('v', 'y'),
        ('w', 'y'),
        ('w', 'z'),
        ('x', 'v'),
        ('y', 'x'),
        ('z', 'z')])

    dfs(G)

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

Когда этот сценарий выполняется, он выводит следующий результат:

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

Это в точности задние края в примере на рис. 22.4 CLRS.

Самый простой способ сделать это - выполнить обход графика в глубину (ДПФ).

Если граф имеет n вершину, это алгоритм O(n) временной сложности. Поскольку вам, возможно, придется выполнять ДПФ, начиная с каждой вершины, общая сложность становится O(n^2).

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

На мой взгляд, наиболее понятным алгоритмом обнаружения цикла в ориентированном графе является алгоритм раскраски графа.

По сути, алгоритм раскраски графа обходит граф способом DFS (поиск в глубину, что означает, что он полностью исследует путь, прежде чем исследовать другой путь). Когда он находит задний край, он помечает граф как содержащий петлю.

Подробное объяснение алгоритма раскраски графа можно найти в этой статье: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Кроме того, я предоставляю реализацию раскраски графов в JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

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

Если вы не можете добавить свойство «посещенные» к узлам, используйте набор (или карту) и просто добавьте все посещенные узлы в набор, если они еще не включены в набор. Используйте уникальный ключ или адрес объектов в качестве «ключа».

Это также дает вам информацию о «корневом» узле циклической зависимости, которая пригодится, когда пользователю необходимо решить проблему.

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

Хотя это может показаться сложностью O (N * M), вы должны помнить, что стек имеет очень ограниченную глубину (поэтому N мало) и что M становится меньше с каждой зависимостью, которую вы можете отметить как «выполнено» плюс вы можете остановить поиск, когда найдете лист (так что вам никогда не придется проверять каждый узел -> M тоже будет маленьким).

В MetaMake я создал график в виде списка списков, а затем удалил все узлы по мере их выполнения, что естественным образом сократило объем поиска. На самом деле мне никогда не приходилось запускать независимую проверку, все это происходило автоматически во время обычного выполнения.

Если вам нужен режим «только тест», просто добавьте флаг «пробного прогона», который отключает выполнение фактических заданий.

Не существует алгоритма, который мог бы найти все циклы в ориентированном графе за полиномиальное время. Предположим, что ориентированный граф имеет n узлов, и каждая пара узлов имеет связи друг с другом, что означает, что у вас есть полный граф. Таким образом, любое непустое подмножество этих n узлов указывает на цикл, и таких подмножеств 2 ^ n-1. Таким образом, не существует алгоритма полиномиального времени. Итак, предположим, что у вас есть эффективный (не глупый) алгоритм, который может сказать вам количество направленных циклов в графе, вы можете сначала найти сильные связанные компоненты, а затем применить свой алгоритм к этим связанным компонентам. Поскольку циклы существуют только внутри компонентов, а не между ними.

Я реализовал эту проблему в sml (императивное программирование). Вот схема. Найдите все узлы с нулевой или исходящей степенью. Такие узлы не могут быть частью цикла (поэтому удалите их). Затем удалите все входящие или исходящие ребра из таких узлов. Рекурсивно примените этот процесс к получившемуся графу. Если в конце у вас не останется ни одного узла или ребра, граф не имеет циклов, иначе они есть.

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

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

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

Если DFS находит ребро, которое указывает на уже посещенную вершину, у вас есть цикл.

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

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

|e| > |v| - 1

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