#algorithm #graph-algorithm #depth-first-search
#алгоритм #граф-алгоритм #поиск в глубину
Вопрос:
Поиск в глубину позволяет обходить смежные вершины в произвольном порядке. Есть ли какие-либо преимущества при выборе случайных соседей по сравнению с выбором соседей по возрастанию?
Рассмотрим порядок исследования следующего графика:
0 -> 9 -> 8 -> 7 ..
0 -> 1 -> 8 -> 7 ..
Может ли случайный выбор привести к более благоприятным результатам?
Комментарии:
1. Как бы вы определили «более благоприятный»? Какую метрику вы используете? В противном случае ответ будет «это зависит»…
2. Пространство постоянно. Время может быть учтено @tucuxi
3. По возрастанию чего? Метка узла? Почему это должно иметь какое-либо значение?
4. Должны ли все ребра быть направленными (иметь стрелки?)
Ответ №1:
Могу ли я найти ситуацию, в которой есть преимущество?
Да. Легко. Если у меня есть связанный граф, обход со случайным выбором гарантированно в конечном итоге достигнет каждого узла. Перемещение по порядку гарантированно в конечном итоге приведет к циклу.
Есть ли преимущество в целом?
Нет. Например, в связном примере простое «отслеживать, где мы были» позволяет обоим достичь всего. Какой из них найдет целевой узел первым, будет вопросом случая.
Ответ №2:
Прежде всего, DFS не несет ответственности за произвольный порядок.
Способ обхода узлов зависит от 2 вещей:
-
Порядок, в котором вы вставили соседние узлы в список смежности (обычно зависит от порядка ребер, предоставленных во входных данных).
-
Пользовательский порядок, который вы выбираете для обхода (как вы упомянули, упорядоченный порядок).
Ответ на ваш вопрос:
-
Выбор порядка, в котором вы вставили соседние узлы в список смежности, не влияет на сложность.
-
Если вы решите обходить соседние узлы в отсортированном виде, вам необходимо соответствующим образом поддерживать список смежности, что достигается за счет дополнительного коэффициента V * log(V).
Общая временная сложность = O(V E) O(V * log(V)).
O(V E) => для DFS.
O(V * log(V)) => для очереди приоритетов / сортировки списка смежности.
Здесь V = количество узлов в графе и E = количество ребер.