Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава

• Хеш-таблицы хорошо подходят для обнаружения дубликатов.

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

В этой главе

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

• Вы освоите поиск в ширину — алгоритм, который применяется к графам для получения ответов на вопросы вида «Какой кратчайший путь ведет к X?»

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

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

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

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

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

• реализовать проверку правописания (минимальное количество изменений, преобразующих ошибочно написанное слово в правильное, например АЛГОРИФМ -> АЛГОРИТМ — одно изменение);

• найти ближайшего к вам врача.

Одни из самых полезных алгоритмов, известных мне, работают с графами. Внимательно прочитайте несколько следующих глав — этот материал неоднократно пригодится вам в работе.

Знакомство с графами

Предположим, вы находитесь в Сан-Франциско и хотите добраться из Твин-Пикс к мосту Золотые Ворота. Вы намереваетесь доехать на автобусе с минимальным количеством пересадок. Возможные варианты:

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

Можно ли сделать это за один шаг? На следующем рисунке выделены все места, в которые можно добраться за один шаг.

Мост на этой схеме не выделен; до него невозможно добраться за один шаг. А можно ли добраться до него за два шага?

И снова мост не выделен, а значит, до него невозможно добраться за два шага. Как насчет трех шагов?

Ага! На этот раз мост Золотые Ворота выделен. Следовательно, чтобы добраться из Твин-Пикс к мосту по этому маршруту, необходимо сделать три шага.

Есть и другие маршруты, которые приведут вас к мосту, но они длиннее (четыре шага). Алгоритм обнаружил, что кратчайший путь к мосту состоит из трех шагов. Задача такого типа называется задачей поиска кратчайшего пути. Часто требуется найти некий кратчайший путь: путь к дому вашего друга, путь к победе в шахматной партии (за наименьшее количество ходов) и т.д. Алгоритм для решения задачи поиска кратчайшего пути называется поиском в ширину.

Чтобы найти кратчайший путь из Твин-Пикс к мосту Золотые Ворота, нам пришлось выполнить два шага:

1. Смоделировать задачу в виде графа.

2. Решить задачу методом поиска в ширину.

В следующем разделе я расскажу, что такое графы. Затем будет рассмотрен более подробно поиск в ширину.

Что такое граф?

Граф моделирует набор связей. Представьте, что вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, условие «Алекс должен Раме» можно смоделировать так:

А полный граф может выглядеть так:

Граф задолженностей при игре в покер

Алекс должен Раме, Том должен Адиту и т.д. Каждый граф состоит из узлов и ребер.

Вот и все! Графы состоят из узлов и ребер. Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называются соседями. На этом графе Рама является соседом Алекса. С другой стороны, Адит соседом Алекса не является, потому что они не соединены напрямую. При этом Адит является соседом Рамы и Тома.

Графы используются для моделирования связей между разными объектами. А теперь посмотрим, как работает поиск в ширину.

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

В главе 1 уже рассматривался пример алгоритма поиска: бинарный поиск. Поиск в ширину также относится к категории алгоритмов поиска, но этот алгоритм работает с графами. Он помогает ответить на вопросы двух типов:

• тип 1: существует ли путь от узла A к узлу B?

• тип 2: как выглядит кратчайший путь от узла A к узлу B?

Вы уже видели пример поиска в ширину, когда мы просчитывали кратчайший путь из Твин-Пикс к мосту Золотые Ворота. Это был вопрос типа 2: как выглядит кратчайший путь? Теперь разберем работу алгоритма более подробно с вопросом типа 1: существует ли путь?

Представьте, что вы выращиваете манго. Вы ищете продавца, который будет продавать ваши замечательные манго. А может, продавец найдется среди ваших контактов на Facebook? Для начала стоит поискать среди друзей.

Поиск происходит вполне тривиально.

Сначала нужно построить список друзей для поиска.

Теперь нужно обратиться к каждому человеку в списке и проверить, продает ли этот человек манго.

Предположим, ни один из ваших друзей не продает манго. Теперь поиск продолжается среди