Проверить, содержит ли неориентированный граф цикл или нет
Для заданного неориентированного графа задача состоит в том, чтобы проверить, есть ли у него цикл или нет, и если есть цикл, вернуть вершины цикла.
Примеры:
Input:
Output: Cycle exists. 3 -> 2 -> 1
Explanation: Cycle exists for 3 -> 2 ->1Input:
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 — количество вершин в графе.