Лучший алгоритм для обнаружения циклов в ориентированном графе
5 ответов
решительно связанный алгоритм компонентов Тарьяна имеет O(|E| + |V|) временная сложность.
Для других алгоритмов, см. Решительно связанные компоненты на Википедию.
Путем я делаю это должно сделать Топологический Вид, считая количество вершин посещаемым. Если то число является меньше, чем общее количество вершин в DAG, у Вас есть цикл.
Если Вы не можете добавить "посещаемое" свойство к узлам, используйте набор (или карта) и просто добавьте все посещаемые узлы к набору, если они уже не находятся в наборе. Используйте уникальный ключ или адрес объектов как "ключ".
Это также дает Вам информацию о "корневом" узле циклической зависимости, которая пригодится, когда пользователь должен будет решить проблему.
Другое решение состоит в том, чтобы попытаться найти, что следующая зависимость выполняется. Для этого у Вас должен быть некоторый стек, где можно помнить, где Вы теперь и что необходимо сделать затем. Проверьте, находится ли зависимость уже на этом стеке перед выполнением его. Если это, Вы нашли цикл.
, В то время как это, могло бы казаться, имело бы сложность O (N*M) Вы, должен помнить, что стек имеет очень ограниченную глубину (таким образом, N является маленьким), и что M становится меньшим с каждой зависимостью, которую можно пометить, как "выполняется" плюс Вы, может остановить поиск, когда Вы нашли лист (таким образом, Вы никогда не должны проверять, что каждый узел-> M будет маленьким, также).
В MetaMake, я создал график как список списков и затем удалил каждый узел, когда я выполнил их, которые естественно сокращают поисковый объем. Я никогда на самом деле должен был осуществить независимую проверку, все это произошло автоматически во время нормального выполнения.
при необходимости в "тесте только" режим, просто добавьте флаг "пробного прогона", который отключает выполнение фактических заданий.
Учитывая, что это - расписание заданий, я подозреваю, что в какой-то момент Вы идете в вид их в предложенный порядок выполнения.
, Если это так, затем топологический вид реализация может в любом случае обнаружить циклы. UNIX tsort, конечно, делает. Я думаю, что вероятно, что поэтому более эффективно обнаружить циклы в то же время, что и tsorting, а не на отдельном шаге.
, Таким образом, вопрос мог бы стать, "как делают меня наиболее эффективно tsort", а не, "как я наиболее эффективно обнаруживаю циклы". К которому ответ, вероятно, "пользуются библиотекой", но сбоем что следующая статья Wikipedia:
имеет псевдокод для одного алгоритма и краткого описания другого из Тарьяна. Оба имеют O(|V| + |E|) временная сложность.
Самый простой способ сделать это - выполнить первый проход по глубине (DFT) графа ].
Если граф имеет n вершин, это алгоритм O (n) временной сложности. Поскольку вам, возможно, придется выполнять ДПФ, начиная с каждой вершины, общая сложность становится равной O (n ^ 2) .
Вы должны поддерживать стек , содержащий все вершины текущего прохода глубины , причем его первый элемент является корневым узлом. Если вы встретите элемент, который уже находится в стеке во время DFT, то у вас есть цикл.