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

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

2 голосов
/ 14 мая 2009

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

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

Ответы [ 4 ]

5 голосов
/ 14 мая 2009

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

4 голосов
/ 12 июня 2009

Вот ваш 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.

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

1 голос
/ 14 мая 2009

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

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

0 голосов
/ 01 мая 2012

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

C = E − N + P

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

C = E - N + 1
...