Обнаружение цикла ациклического графа, ориентированного на один корень

Граф имеет только один корень. И сохраняется в следующем формате:

0 -> 1,
0 -> 2,
1 -> 3,
1 -> 4,
2 -> 4,
2 -> 5,
4 -> 5,
5 -> 2 (This is the cycle)

Каков наиболее эффективный способ определить, существует ли в графе хотя бы один цикл с использованием Java? Спасибо!

пример


java graph algorithm topological-sort
person billlipeng    schedule 11.07.2016    source источник
comment
Вы можете использовать алгоритм Кана (или, альтернативно, DFS), чтобы найти топологическую сортировку ориентированного графа. Если топологическая сортировка не может быть найдена, то существует цикл. Оба подхода имеют время работы, линейное по количеству узлов и количеству ребер, то есть O(|V| + |E|).   -  person Konstantin Yovkov    schedule 11.07.2016

Ответы (1)


arrow_upward
0
arrow_downward

Как уже упоминалось в комментариях, вероятно, какой-то DFS, например

SET isCyclic to false
DFS(node)
   IF isCyclic is true THEN 
       RETURN
   FOR each neighbor in node.neighbors
       IF node.visited is true THEN
           SET isCyclic to true
           RETURN
       SET neighbor.visited to true
       DFS(neighbor)
person Bobas_Pett    schedule 12.07.2016