Правильный обход ненаправленного графа с использованием поиска в глубину?

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

Диаграмма Excel ниже показывает, что каждый узел был отмечен после обхода в отмеченном столбце, а столбец edgeTo показывает, какой узел привел нас к этому узлу. Например, мы получили узел 1 от узла 5, мы получили узел 2 от узла 7 и т. Д.

Мой вопрос к узлам 6 и 8, так как они отделены от основного графа, как мне правильно пройти его? Я предполагаю, что я начинаю с 6 и перехожу на 8, но, поскольку 6 уже будет посещен в этот момент, я не возвращаюсь к 6 из 8. Следовательно, строка 6 остается пустой в столбце edgeTo.

Я прав? Мой график правильный?

1 ответ

Решение

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

6 и 8, очевидно, являются узлами, которые принадлежат другому подграфу, и поэтому вы не можете найти путь между 0 и 8, и DFS вернет НЕВОЗМОЖНО или путь не найден. Кроме того, ваша диаграмма верна.

Другие вопросы по тегам