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

15 СЕНТЯБРЯ



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

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

Эта глава посвящена графам. Сначала вы узнаете, что такое граф. Затем я покажу первый алгоритм, работающий с графами. Он называется поиском в ширину (BFS, Breadth-First Search).
Поиск в ширину позволяет найти кратчайшее расстояние между двумя объ­ектами. Однако сам термин «кратчайшее расстояние» может иметь много разных значений! Ь1апример, с помощью поиска в ширину можно:
□ написать программу для игры в шашки, которая вычисляет кратчайший путь к победе;

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

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

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

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

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

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

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

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

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

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

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


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