Определить, существует ли цикл в неориентированном графе

Question

Мой вопрос касается ОБНАРУЖЕНИЯ, если существует цикл. Мне все равно, где цикл происходит, но только если существует цикл. В частности, я работаю над реализацией (максимально) алгоритма связующего дерева. Я отсортировал ребра по убыванию, а затем выбрал одно ребро за раз и поместил его в набор ребер графа, если он не вызывает цикл.

Я обнаружил, что для неориентированных графов достаточно только проверить, если no_of_edges> no_of_vertices - 1 . Это правильно? Я пытаюсь найти случай, когда это не так, но я не могу. Конечно, это не значит, что это правильно.

Спасибо

Answer 1

Просто запустите поиск DFS; он автоматически обнаруживает циклы, потому что это условие остановки для DFS - вы останавливаетесь, когда входите в узел, который уже находится в стеке, и именно тогда вы нашли цикл.

Answer 2

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

Но да, если число ребер <= число вершин-1 в связном графе, тоне может быть циклов. </p>

Answer 3

В сущности, ваша идея верна. Но могут быть некоторые подводные камни:

1) Сначала запустите DFS и найдите все подключенные компоненты, проверьте, выполняется ли условие no_of_edges <= no_of_vertices - 1 </strong> во всех подключенных компонентах.

2) Проверьте, содержит ли каждый подключенный компонент несколько ребер.