Я читаю-читаю статьи по этому вопросу, и никак не могу понять, какой должен быть результат.
Я думал, что этот алгоритм должен выдать последовательность вершин начиная с заданной, такую, чтобы обойти весь граф (побывать в каждой вершине один раз). И, собственно, то же самое от меня хочет преподаватель.
Но, видимо, это что-то другое?
Например, вот в статье (Поиск в ширину), со входными данными "2" получаем результат "2 3 4 1" (при этом на графе нет пути из 4 в 1).
В общем, объясните, пожалуйста?
-
4Вот простое и понятное описание, даже с анимированными картинками.– VladDCommented 25 окт. 2013 в 15:43
2 ответа
В ширину:
- Выбираешь начальную вершину.
- Затем по очереди проверяешь все соединенные с ней вершины(потомки).
- Когда они закончатся, за начальную берешь одну из проверенных вершин (потомков).
В глубину:
Выбираешь начальную вершину.
Затем проверяешь соединенную с ней вершину(потомка) и сразу делаешь ее новой основной вершиной.
Если у проверенной вершины нет еще одной связи(с потомком), возвращаешься на предыдущую вершину(предка) и ищешь у нее непроверенную связь с потомкам, если такой связи к нет - снова назад(к предку).
Мы на дискретке делали примерно так:
В очередь записывали первую точку, потом шли в алфавитном порядке во все доступные стороны и записывали точки в очередь. Когда пути из этой точки заканчивались, мы ее вычеркивали и переходили к той, которая следующая в очереди.
В данном случае (см. рисунок) записываем "a", потом пишем "b" "d" "l", пути из "a" закончились, вычеркиваем "a". Переходим к "b", из нее нет никаких путей - вычеркиваем, переходим к "d", из нее попадаем в "f", "g" - записываем. Из "d" пути закончились - вычеркиваем, переходим к l и т.д.
Примечание к рисунку:
В рисунке ошибка, когда я делал это задание, я забыл английский алфавит и посчитал, что k идет раньше, чем j. На самом деле их просто нужно поменять местами.
Пунктирной линией помечались пути, которые мы не проходим потому, что они приведут в точку которую мы уже обошли.
Жирной линией отмечен пройденный, в процессе обхода, путь.
Жирные, пунктирные линии и зачеркнутые буквы возникали в процессе обхода, их не было в изначальном задании.