На этом шаге продолжим рассматривать поиск в ширину.
Поиск в ширину также относится к категории алгоритмов поиска, но этот алгоритм работает с графами. Он помогает ответить на вопросы двух типов:
- тип 1: существует ли путь от узла А к узлу В?
- тип 2: как выглядит кратчайший путь от узла А к узлу В?
Пример поиска в ширину, рассмотренный нами на шаге 35, позволяет найти кратчайший путь из А в В. Это был вопрос типа 2: как выглядит кратчайший путь? Теперь разберем работу алгоритма более подробно с вопросом типа 1: существует ли путь?
Представьте, что вы открыли бизнес по изготовлению шариковых ручек. Вы ищете покупателя, который будет реализовывать ваши изделия. Для начала стоит поискать среди друзей.
Поиск происходит вполне тривиально. Сначала нужно построить список друзей для поиска. Теперь нужно обратиться к каждому человеку в списке и проверить, продает ли этот человек канцелярские принадлежности.
Предположим, ни один из ваших друзей не продает канцтовары. Теперь поиск продолжается среди друзей ваших друзей. Каждый раз, когда вы проверяете кого-то из списка, вы добавляете в список всех его друзей.
В таком случае поиск ведется не только среди друзей, но и среди друзей друзей тоже. Напомним: нужно найти в сети хотя бы одного продавца канцтоваров. Если Алиса не продает ручки, то в список добавляются ее друзья. Это означает, что со временем вы проверите всех ее друзей, а потом их друзей и т. д. С этим алгоритмом поиск рано или поздно пройдет по всей сети, пока вы все-таки не наткнетесь на продавца канцелярии. Такой алгоритм и называется поиском в ширину.
На следующем шаге рассмотрим поиск кратчайшего пути.
