Page 128 - Bkhargava_-_Grokaem_algoritmy

6 Поиск в ширину

В этой главе

./ Вы научитесь моделировать сети при помощи новой
абстрактной структуры данных - графов .

../ Вы освоите поиск в ширину - алгоритм, который при­
меняется к графам для получения ответов на вопросы
вида «Какой кратчайший путь ведет к Х?»

,,,, Вы узнаете, чем направленные графы отличаются от
ненаправленных.

,,,, Вы освоите топологическую сортировку - другой алго­
ритм сортировки, раскрывающий связи между узлами.

Эта глава посвящена графам. Сначала вы узнаете, что такое граф. Затем
я покажу первый алгоритм, работающий с графами. Он называется поиском
в ширину (BFS, Breadth-First Search).

Поиск в ширину позволяет найти кратчайшее расстояние между двумя объ­
ектами. Однако сам термин «кратчайшее расстояние» может иметь много
разных значений! Например, с помощью поиска в ширину можно:

о написать программу для игры в шашки, которая вычисляет кратчайший
путь к победе;

www.trk.kg