Блог

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

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

Какие-нибудь намеки?

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

Выполните поиск в глубину, добавляя узлы в список по ходу работы и удаляя их из списка по возвращении.

Список представляет ваш текущий путь обхода.

Если вы сталкиваетесь с узлом, который уже есть в вашем списке, значит, есть цикл.

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

Для ребра (u,v):

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

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

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

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

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

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

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

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