Грокаем алгоритмы

Теперь, когда вы знаете, как работает очередь, можно переходить к реализации поиска в ширину!

Упражнения

Примените алгоритм поиска в ширину к каждому из этих графов, чтобы найти решение.

6.1 Найдите длину кратчайшего пути от начального до конечного узла.

6.2 Найдите длину кратчайшего пути от «cab» к «bat».

Реализация графа

Для начала необходимо реализовать граф на программном уровне. Граф состоит из нескольких узлов. И каждый узел соединяется с соседними узлами. Как выразить отношение типа «вы –> боб»? К счастью, вам уже известна структура данных, способная выражать отношения: хеш-таблица!

Вспомните: хеш-таблица связывает ключ со значением. В данном случае узел должен быть связан со всеми его соседями.

А вот как это записывается на Python:

graph = {}

graph["you"] = ["alice", "bob", "claire"]

Обратите внимание: элемент «вы» (you) отображается на массив. Следовательно, результатом выражения graph["you"] является массив всех ваших соседей.

Граф — всего лишь набор узлов и ребер, поэтому для представления графа на Python ничего больше не потребуется. А как насчет большего графа, например такого?

Код на языке Python выглядит так:

graph = {}

graph["you"] = ["alice", "bob", "claire"]

graph["bob"] = ["anuj", "peggy"]

graph["alice"] = ["peggy"]

graph["claire"] = ["thom", "jonny"]

graph["anuj"] = []

graph["peggy"] = []

graph["thom"] = []

graph["jonny"] = []

Контрольный вопрос: важен ли порядок добавления пар «ключ—зна­чение»?

Важно ли, какую запись вы будете использовать, — такую:

graph["claire"] = ["thom", "jonny"]

graph["anuj"] = []

или такую:

graph["anuj"] = []

graph["claire"] = ["thom", "jonny"]

Вспомните предыдущую главу. Ответ: нет, не важно. В хеш-таблицах элементы не упорядочены, поэтому добавлять пары «ключ—значение» можно в любом порядке.

У Ануджа, Пегги, Тома и Джонни соседей нет. Линии со стрелками указывают на них, но не существует стрелок от них к другим узлам. Такой граф называется направленным — отношения действуют только в одну сторону. Итак, Анудж является соседом Боба, но Боб не является соседом Ануджа. В ненаправленном графе стрелок нет, и каждый из узлов является соседом по отношению друг к другу. Например, оба следующих графа эквивалентны.

Реализация алгоритма

Напомню, как работает реализация.

Все начинается с создания очереди. В Python для создания двусторонней очереди (дека) используется функция deque:

from collections import deque

search_queue = deque()      Создание новой очереди

search_queue += graph["you"]   Все соседи добавляются в очередь поиска

Напомню, что выражение graph["you"] вернет список всех ваших соседей, например ["alice", "bob", "claire"]. Все они добавляются в очередь поиска.

А теперь рассмотрим остальное:

while search_queue:  Пока очередь не пуста…

    person = search_queue.popleft()    из очереди извлекается первый человек

    if person_is_seller(person):   Проверяем, является ли этот человек продавцом манго

        print person + " is a mango seller!"      Да, это продавец манго

        return True

    else:

        search_queue += graph[person]     Нет, не является. Все друзья этого человека добавляются в очередь поиска

return False   Если выполнение дошло до этой строки, значит, в очереди нет продавца манго

И последнее: нужно определить функцию person_is_seller, которая сообщает, является ли человек продавцом манго. Например, функция может выглядеть так:

def person_is_seller(name):

    return name[-1] == 'm'

Эта функция проверяет, заканчивается ли имя на букву «m», и если заканчивается, этот человек считается продавцом манго. Проверка довольно глупая, но для нашего примера сойдет. А теперь посмотрим, как работает поиск в ширину.

И так далее. Алгоритм продолжает работать до тех пор, пока:

• не будет найден продавец манго,

или

• очередь не опустеет (в этом случае продавца манго нет).

У Алисы и Боба есть один общий друг: Пегги. Следовательно, Пегги будет добавлена в очередь дважды: при добавлении друзей Алисы и при добавлении друзей Боба. В результате Пегги появится в очереди поиска в двух экземплярах.

Но проверить, является ли Пегги продавцом манго, достаточно всего один раз. Проверяя ее дважды, вы выполняете лишнюю, ненужную работу. Следовательно, после проверки человека нужно пометить как проверенного, чтобы не проверять его снова.

Если этого не сделать, может возникнуть бесконечный цикл. Предположим, граф выглядит так:

В начале очередь поиска содержит всех ваших соседей.

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

Вы проверяете себя. Вы не являетесь продавцом манго, поэтому все ваши соседи добавляются в очередь поиска.