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

StackOverflow https://stackoverflow.com/questions/261573

Вопрос

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

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

Это было полезно?

Решение

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

Другие алгоритмы см. в Компонентах с сильным подключением в Википедии.

Другие советы

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

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

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

  

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

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

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

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

Если у графа есть 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

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

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

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

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

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

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

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

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

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

  

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

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

введите описание изображения здесь

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

введите описание изображения здесь

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

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

Следующий код 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 discovered and 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.

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

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

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

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

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

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

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

|e| > |v| - 1

тогда график содержит, по крайней мере, цикл.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top