союзной Найти алгоритм и определения, принадлежит ли ребро к циклу в графе

Question

Я читаю книгу о алгоритмах («Структуры данных и алгоритмы в C++») и наткнулись на следующее упражнение:

Пример. 20. Измените cycleDetectionDFS() так, чтобы он мог определить, является ли конкретное ребро частью цикла в неориентированном графе.

В главе о графиках, книга читается:

Вспомним из предыдущего раздела, поиск в глубину гарантированной генерации остовного дерева, в котором нет элементов edges не используемый depthFirstSearch() привело к циклу с другим элементом edges. Это связано с тем, что если вершины v и у принадлежали edges, то край (Vu) был проигнорирован depthFirstSearch(). Проблема возникает, когда depthFirstSearch() модифицирован так, что он может обнаружить , является ли конкретный край (vu) частью цикла (см. Упражнение 20). Если такой модифицированный поиск глубины сначала применяется к каждому ребру , то общий пробег будет равен O (E (E + V)), который может превращать в O (V^4) для плотных графов. Следовательно, лучший метод должен быть найден .

Задача состоит в том, чтобы определить, находятся ли две вершины в одном наборе. Два операции необходимы для выполнения этой задачи: найти множество, которому вершина v принадлежит и объединение двух множеств в одно, если вершина v принадлежит к одному из них и ж к другому. Это известно как union-find проблема.

Позже автор описывает, как объединить два набора в одно в случае преимущество перешло к функции union(edge e) соединяет вершины в различных наборах.

Однако, я не знаю, как быстро проверить, является ли край частью цикла. Может ли кто-нибудь дать мне приблизительное объяснение такого алгоритма, связанного с вышеупомянутой проблемой объединения-поиска?

Answer 1

может быть проверено, является ли ссылка обратной связью, всякий раз, когда у вас есть обратная связь, у вас есть цикл, и всякий раз, когда у вас есть цикл, у вас есть обратная связь (это верно для направленных и неориентированных графов).

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

Я дал вам несколько указателей на то, где искать, дайте мне знать, если это поможет вам прояснить ваши проблемы.