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

Question

Как обнаружить циклы в

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

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

• для каждой вершины v в G
  • Make-набор (v)
• для каждого ребра e(u,v) в G, взятого один за другим
  • if Find-set (u) == Find-set (v)
    • return true // Цикл присутствует
• вернуть ложь

Answer 1

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

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

Answer 2

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

• для каждой вершины v в G
  • Meke-множество (v)
• для каждого ребра e(u,v) в G, взятого один за другим
  • if Find-set(u) == Find-set(v)
    • вернуть истину
  • Союз-набор (U, V)
• вернуть ложь

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