Как проверить, находится ли ребро в каком-то цикле?

Question

У меня есть проблема hw, которая запрашивает алгоритм, который обнаруживает, есть ли цикл в любом неориентированном графе, который содержит любое заданное ребро 'E'.Алгоритм должен работать за O (N) линейное время.

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

Есть какие-нибудь подсказки?

Answer 1

Выньте этот край (и, v) из G. 1. Запустите BFS, чтобы увидеть, доступен ли v из u. 2. если да, то у исходного графа есть цикл, содержащий e. в противном случае нет.

Answer 2

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

Список представляет текущий путь обхода.наткнуться на узел, который уже находится в вашем списке, то есть цикл / цикл.

Answer 3

Запустите DFS на G и сделайте следующее. Рассмотрим первый раз, когда ребро e пройдено.

Есть два случая:

1. е является задним ходом. В этом случае e, очевидно, является частью цикла, и цикл может быть напечатан.
2. e = (a, b) - ребро дерева (направление обхода от u до v). Теперь начните второй этап алгоритм. Для каждого заднего края (w, x), найденного в DFS, проверьте, является ли w потомком v, а x предок тебя. Если это так, мы нашли цикл, включающий ребро е.

Answer 4

Для края (u, v):

1 - выполнить поиск по глубине, начиная с u, определить, найден ли v и существует ли задний край вдоль пути к v.

2 - выполнить поиск в глубину из v, если u найден, и задний край существует для u, то есть цикл, который включает в себя и u, и v.

Другими словами,

1 - выполнить DFS, начиная с u, проверить, существует ли задний фронт и v еще не завершено.

2 - выполнить DFS, начиная с v, проверить, существует ли задний фронт и u еще не закончил если оба условия выполняются, то ребро (u, v) принадлежит циклу.

Answer 5

Вы начинаете с края 'e'.Из него вы должны получить две вершины, которые он соединяет.Из них вы получаете другие ребра и другие вершины, а также другие ребра и другие вершины, и ... вам понадобится способ выяснить, была ли вершина уже «посещена» вашим алгоритмом.Если это так, то есть цикл, частью которого является «е».