Циклические ориентированные и неориентированные графы

Как определить циклы в

  1. ориентированный граф
  2. неориентированный граф.

Для неориентированного графа ... один из алгоритмов, о которых я подумал, основан на использовании непересекающихся множеств.

  • for each vertex v in G
    • Make-set(v)
  • for each edge e(u,v) in G taken one by one
    • if Find-set(u) == Find-set(v)
      • return true // Cycle is present
  • вернуть ложь

graph directed-acyclic-graphs algorithm cyclic-graph
person user3533144    schedule 14.04.2014    source источник
comment
Ваш подход называется объединением-поиском, и да, его можно использовать для поиска цикла в неориентированном графе. В качестве альтернативы просто выполните DFS и посмотрите, сталкивались ли вы с узлом раньше. Для ориентированного графа используйте модифицированную DFS, которая отслеживает то, что вы просматривали во время текущего исследования, и помечает те, которые не были посещены при откате от DFS.   -  person rafalio    schedule 14.04.2014
comment
Возможный дубликат циклов в неориентированном графике и Лучший алгоритм для обнаружения циклов в ориентированном графе. Мне не удалось найти хорошую ссылку для обнаружения непересекающегося набора циклов в Stack Overflow, но которая работает.   -  person Bernhard Barker    schedule 14.04.2014
comment
Вы явно пытались решить (частично) проблему самостоятельно, поэтому, вероятно, не заслуживаете отрицательного голоса, но лично я считаю, что вам всегда следует выполнять поиск в Google, прежде чем задавать вопрос.   -  person Bernhard Barker    schedule 14.04.2014

Ответы (2)


arrow_upward
1
arrow_downward

Для неориентированного просто используйте DFS: если граница указывает на уже посещенная вершина, есть цикл.

Для ориентированного ознакомьтесь с этим вопросом .

person MarcoL    schedule 14.04.2014

arrow_upward
0
arrow_downward

Ваш подход к поиску цикла в неориентированном графе должен быть таким:

  • for each vertex v in G
    • Meke-set(v)
  • for each edge e(u,v) in G taken one by one
    • if Find-set(u) == Find-set(v)
      • return true
    • Union-set (u, v)
  • вернуть ложь

Для ориентированного графа вы должны использовать алгоритм сильно связанных компонентов Тарьяна, чтобы получить количество сильно компоненты в графе. Затем вы можете проверить, равно ли количество сильно связных компонентов количеству вершин. Поскольку если в ориентированном графе есть цикл, то в одних и тех же компонентах сильной связности есть как минимум две вершины. Это означает, что общее количество сильно связных компонент должно быть меньше количества вершин, если ориентированный граф имеет цикл.

person Ricky Ye    schedule 15.04.2014