Проверить, содержит ли неориентированный граф цикл или нет

Для заданного неориентированного графа задача состоит в том, чтобы проверить, есть ли у него цикл или нет, и если есть цикл, вернуть вершины цикла.

Примеры:

Input:

Example-1

Output: Cycle exists. 3 -> 2 -> 1
Explanation: Cycle exists for 3 -> 2 ->1

Input: 

Example-2

Output: Cycle does not exist.

Подход: Эту проблему можно решить, используя DFS of Graph и Stack для хранения вершин Graph.

• Создайте переменную x для хранения начала цикла и создайте стек для хранения вершин цикла.
• DFS проходит по заданному графу и помечает узел как посещенный.
• Для каждого дочернего элемента этого узла проверьте, не посетил ли дочерний элемент DFS, пройдя дочерний элемент.
• В противном случае, если дочерний элемент посещается, а также он не является родителем текущего узла, то мы обнаружили цикл, и, таким образом, значение x становится значением дочернего узла.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(V + E), где V — количество вершин, а E — количество ребер в графе.
Вспомогательное пространство: O(V), где V — количество вершин в графе.

Другой метод: проверить цикл существует или нет: -

Для нахождения цикла в неориентированном графе мы используем поиск в глубину. Используйте dfs для каждого непосещенного узла. Цикл в неориентированном графе существует только в том случае, если в графе присутствует обратная грань. Чтобы найти задний край для любого из его предков, сохраните посещенный массив, и если есть задний край для любого посещенного узла, тогда будет цикл и возврат true.

Подход:

Выполните следующие шаги, чтобы реализовать описанный выше подход:

• Сначала выполните итерацию по всем узлам графа и сохраните массив vis[] для отслеживания посещенных узлов.
• Запустите обход DFS (поиск в глубину) для данного подграфа, подключенного к текущему узлу, а затем передайте родителя текущего узла.
• Для каждой рекурсии установите vis[root] = 1.
• Перебрать все соседние узлы текущего узла в списке смежности
  • если его не посещают
    • затем запустите DFS на этом узле, верните результат DFS.
  • В противном случае, если соседний узел посещается
    • если это не родитель текущего узла
      • затем верните true .
• иначе вернуть ложь .

Выход:

Graph1 contains cycle

Сложность:

Временная сложность: O(V + E), где V — количество вершин, а E — количество ребер в графе.
Вспомогательное пространство: O(V), где V — количество вершин в графе.