Самый быстрый алгоритм обнаружения петли в графе

Какой алгоритм лучше всего подходит для неориентированного графа, чтобы определить, содержит ли он цикл или нет?

Поиск в ширину или в глубину при отслеживании посещенных узлов — это один метод, но это O (n ^ 2). Есть ли что-нибудь быстрее?


algorithm graph-theory cycle
person Frederick The Fool    schedule 14.05.2009    source источник

Ответы (4)


arrow_upward
6
arrow_downward

Алгоритмы BFS и DFS для заданного графа G(V,E) имеют временную сложность O(|V|+|E|). Итак, как вы можете видеть, это линейная зависимость ввода. Вы можете выполнить некоторые эвристики, если у вас очень специализированный граф, но в целом не так уж плохо использовать для этого DFS. Вы можете проверить некоторую информацию здесь. В любом случае вам придется пройти весь график.

person Artem Barger    schedule 14.05.2009
comment
Спасибо, наверное, я проигнорировал тот факт, что набор всех посещенных узлов вначале очень мал и растет только по мере продвижения алгоритма. - person Frederick The Fool; 14.05.2009

arrow_upward
4
arrow_downward

Вот ваш O(V) алгоритм:

def hasCycles(G, V, E): 
    if E>=V:
        return True
    else:
        # here E<V
        # perform O(E+V) = O(V) algorithm 
        ...

... можно выполнить с помощью DFS. Если у вас есть E<V и ребра хранятся значимым образом (в виде списка), вы, вероятно, можете сделать O (E) + журналы, что сделает весь алгоритм O(min(E,V))+logs.

Надеюсь, вам понравился этот ответ, хотя и немного поздно!

person ilya n.    schedule 12.06.2009
comment
Как видите, я активно использую тот факт, что неориентированный граф без циклов является подграфом дерева и, следовательно, должен иметь E‹V - person ilya n.; 12.06.2009

arrow_upward
1
arrow_downward

Проверка наличия цикла в графе G(V,E) с использованием поиска в глубину выполняется за O(|V|,|E|), если граф представлен с помощью списка смежности.

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

person mealnor    schedule 14.05.2009

arrow_upward
0
arrow_downward

Если у вас есть простой график, вы можете рассчитать цикломатическое число:

C = E − N + P

Где C — количество циклов, E — количество ребер, N — количество узлов, а P — количество компонентов. Если у вас график подключен, то это:

C = E - N + 1
person Moa    schedule 01.05.2012