Ответ 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.