Подтвердить что ты не робот

Поиск длины кратчайшего цикла в неориентированном графе

Я попробовал следующее:

1) DFS, отслеживая уровень каждой вершины в моем дереве DFS

2) Каждый раз, когда видим задний край (x, y), я вычисляю длину цикла = уровень [x] - уровень [y] + 1 и сохраняю его, если он меньше кратчайшего

Может кто-нибудь сказать пример счетчика, для которого этот подход неверен?

Что может быть лучшим способом найти кратчайший цикл в неориентированных графах?

Спасибо.

Ответ 1

Почему DFS не работает

Вы не можете использовать DFS для поиска кратчайшего круга. Мы можем легко создать встречный пример, в котором DFS ведет поиск только самого длинного круга. Давайте посмотрим на следующий график:

Как видите, у нас есть девять узлов. Если мы начнем с самого левого node A, можно было бы использовать следующий уровень DFS:

У нас есть два задних края при итерации:

(B , A), поэтому мы нашли круг с длиной 8
(D , A), поэтому мы нашли круг с длиной 8

Однако самый короткий круг имеет длину 5. Он показан синим на следующем рисунке, тогда как один из найденных ранее кругов показан красным:

Вы не видели синий круг, потому что ваш путь DFS не содержит его. Дагупа и др. Также упоминают это поведение в своей книге:

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

Почему BFS не работает

Ну, это не совсем так, можно использовать BFS (см. следующий подраздел), но вы не можете использовать свою формулу. Возьмем следующий график:

No fancy picture for this graph yet.

Every "o" is a node.

        o---o
        |   |
+-------o---o-------+
|                   |
o----o----o----o----o

Давайте посмотрим, какие уровни возможны в BFS. Если я начинаю с node посередине, я получаю следующие уровни:

        5~~~5            ~~~ are back-edges
        |   |
+-------4~~~4-------+
|                   |
3----2----1----2----3

И если я начинаю слева node, я получаю следующие уровни:

        3~~~4
        |   |
+-------2---3-------+
|                   |
1----2----3----4~~~~4

Следовательно, вы не можете использовать формулу уровня.

Решение

Хотя это и не эффективно, использование корректного решения с использованием алгоритма с парной кратчайшей траекторией и проверки расстояния (i, i) для каждого node.

Ответ 2

Я думаю, что это то, что вы ищете: http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf

Вы создаете BFS из каждого node, поэтому у вас есть сложность O (V * E)

Ответ 3

Скажем, у нас есть график со следующими ребрами,

1 ↔ 4, 4 ↔ 2, 4 ↔ 3, 2 ↔ 3, 3 ↔ 1

Затем цикл 1, 4, 2, 3, 1 может быть пройден до 1, 4, 3, 1 и, поскольку мы рассматриваем DFS, no node будет посещаться дважды. Поэтому, если первый, 1, 4, 2, 3, 1 пройден сначала, то вероятность того, что 1, 4, 3, 1 или 4, 2, 3, 3 будет пройдена вообще. Поэтому с DFS он может НЕ быть уверенным, что мы получим самый короткий цикл.

Возможное улучшение: Дерево BFS должно работать нормально, так как оно идет по уровню и для дерева дерева BFS от root до любого node фиксировано, независимо от того, в каком порядке выбираются узлы. Runtime: O (V + E), а модифицированный алгоритм Флойда-Варшалла в худшем случае будет работать в O (V ^ 3).