Правильный обход ненаправленного графа с использованием поиска в глубину?
У меня есть неориентированный график, который мне нужно пройти, используя поиск в глубину.
Диаграмма Excel ниже показывает, что каждый узел был отмечен после обхода в отмеченном столбце, а столбец edgeTo показывает, какой узел привел нас к этому узлу. Например, мы получили узел 1 от узла 5, мы получили узел 2 от узла 7 и т. Д.
Мой вопрос к узлам 6 и 8, так как они отделены от основного графа, как мне правильно пройти его? Я предполагаю, что я начинаю с 6 и перехожу на 8, но, поскольку 6 уже будет посещен в этот момент, я не возвращаюсь к 6 из 8. Следовательно, строка 6 остается пустой в столбце edgeTo.
Я прав? Мой график правильный?
1 ответ
Поиск по глубине в основном используется для поиска пути между двумя узлами в графе. График вашего примера отключен, то есть в вашем графе есть два узла, так что ни один путь в вашем графе не имеет этих узлов в качестве конечных точек.
6 и 8, очевидно, являются узлами, которые принадлежат другому подграфу, и поэтому вы не можете найти путь между 0 и 8, и DFS вернет НЕВОЗМОЖНО или путь не найден. Кроме того, ваша диаграмма верна.