
64 Глава 4. Алгоритмы поиска по графу и поиска пути
Рис. 4.4. Поиск в глубину, начиная с Гааги.
Номера вершин означают порядок обхода
Обратите внимание, насколько отличается порядок вершин по срав-
нению с BFS. В данном варианте DFS мы начинаем с перехода из Гааги в
Амстердам, а затем можем добраться до всех остальных вершин на графе
вообще без необходимости возврата назад!
Вы увидели, как алгоритмы поиска определяют основные принципы
перемещения по графам. Теперь давайте рассмотрим алгоритмы поиска
пути, которые находят самый дешевый путь с точки зрения количества пе-
реходов или веса. Вес может быть любым измеримым параметром, ...