Как проверить, является ли ориентированный граф ациклическим? И как называется алгоритм? Я был бы признателен за ссылку.
Как проверить, является ли ориентированный граф ациклическим?
Ответ 1
Я попытался бы сортировать график топологически, а если вы не можете, то он имеет циклы.
Ответ 2
Выполнение простого поиска по глубине сначала недостаточно для поиска цикла. Можно посещать node несколько раз в DFS без существующего цикла. В зависимости от того, где вы начинаете, вы также можете не посетить весь график.
Вы можете проверить циклы в подключенном компоненте графика следующим образом. Найдите node, который имеет только исходящие ребра. Если такой node нет, тогда существует цикл. Запустите DFS с помощью node. При пересечении каждого края проверьте, указывает ли край на node на ваш стек. Это указывает на существование цикла. Если вы не найдете такого края, в этом подключенном компоненте нет циклов.
Как указывает Rutger Prins, если ваш график не подключен, вам нужно повторить поиск по каждому подключенному компоненту.
В качестве ссылки Тархан сильно связанный компонентный алгоритм тесно связан. Это также поможет вам найти циклы, а не просто сообщить, существуют ли они.
Ответ 3
Лемма 22.11 в книге Introduction to Algorithms (Второе издание) гласит, что:
Направленный граф G ацикличен тогда и только тогда, когда поиск по глубине в G не дает обратных ребер
Ответ 4
Решение1: алгоритм Кана для проверки цикла. Основная идея: поддерживать очередь, в которой node с нулевой степенью будет добавляться в очередь. Затем отделите node один за другим, пока очередь не будет пустой. Проверьте, существуют ли какие-либо внешние ребра node.
Решение2: Тарханский алгоритм для проверки Сильного подключенного компонента.
Решение3: DFS. Используйте целочисленный массив для маркировки текущего состояния node: то есть 0 - означает, что этот node ранее не был посещен. -1 - означает, что этот node был посещен, и его дочерние узлы посещаются. 1 - означает, что этот node был посещен, и это было сделано. Поэтому, если статус node равен -1 при выполнении DFS, это означает, что должен существовать цикл.
Ответ 5
Решение, предоставленное ShuggyCoUk, является неполным, поскольку оно может не проверять все узлы.
def isDAG(nodes V):
while there is an unvisited node v in V:
bool cycleFound = dfs(v)
if cyclefound:
return false
return true
Это имеет временную сложность O (n + m) или O (n ^ 2)
Ответ 6
Я знаю, что это старая тема, но для будущих поисковиков здесь есть реализация С#, которую я создал (не утверждают, что она наиболее эффективна!). Это предназначено для использования простого целого для идентификации каждого node. Вы можете украсить это, как вам нравится, при условии, что ваши хэш-объекты node равны.
Для очень глубоких графиков это может иметь высокие накладные расходы, поскольку он создает хешсет на каждом node по глубине (они уничтожаются по ширине).
Вы вводите node, из которого вы хотите выполнить поиск, и путь к этому node.
- Для графа с одним корнем node вы отправляете этот node и пустой hashset
- Для графика с несколькими корневыми узлами вы переносите это в foreach по этим узлам и передаете новый пустой хэш-набор для каждой итерации
-
При проверке циклов ниже любого данного node просто передайте, что node вместе с пустым hashset
private bool FindCycle(int node, HashSet<int> path) { if (path.Contains(node)) return true; var extendedPath = new HashSet<int>(path) {node}; foreach (var child in GetChildren(node)) { if (FindCycle(child, extendedPath)) return true; } return false; }
Ответ 7
При выполнении DFS не должно быть никакого заднего края. Следите за уже посещенными узлами при выполнении DFS, если вы столкнулись с краем между текущим node и существующим node, тогда график имеет цикл.
Ответ 8
вот быстрый код, чтобы найти, имеет ли граф циклы:
func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{
if(breadCrumb[root] == true)
{
return true;
}
if(visited[root] == true)
{
return false;
}
visited[root] = true;
breadCrumb[root] = true;
if(G[root] != nil)
{
for child : Int in G[root]!
{
if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
{
return true;
}
}
}
breadCrumb[root] = false;
return false;
}
let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];
var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];
var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)
Идея такова: обычный алгоритм dfs с массивом для отслеживания посещенных узлов и дополнительный массив, который служит маркером для узлов, которые привели к текущему node, так что когда мы выполняем a dfs для node мы устанавливаем соответствующий элемент в массиве маркеров как истинный, так что когда когда-либо уже посещенный node столкнулся, мы проверяем, является ли его соответствующий элемент в массиве маркеров истинным, если его true, а затем его один из узлы, которые позволяют себе (следовательно, цикл), а трюк - всякий раз, когда возвращается dfs из node, мы возвращаем его соответствующий маркер в false, так что, если мы снова посетили его с другого маршрута, мы не обманевались.
Ответ 9
Вот моя рубиновая реализация отменить листовой алгоритм node.
def detect_cycles(initial_graph, number_of_iterations=-1)
# If we keep peeling off leaf nodes, one of two things will happen
# A) We will eventually peel off all nodes: The graph is acyclic.
# B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
graph = initial_graph
iteration = 0
loop do
iteration += 1
if number_of_iterations > 0 && iteration > number_of_iterations
raise "prevented infinite loop"
end
if graph.nodes.empty?
#puts "the graph is without cycles"
return false
end
leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }
if leaf_nodes.empty?
#puts "the graph contain cycles"
return true
end
nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
graph = Graph.new(nodes2, edges2)
end
raise "should not happen"
end