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

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», и если заканчивается, этот человек считается продавцом манго. Проверка довольно глупая, но для нашего примера сойдет. А теперь посмотрим, как работает поиск в ширину.

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

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

или

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

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

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

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

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

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

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

И так далее. Возникает бесконечный цикл, потому что очередь поиска будет поочередно переходить от вас к Пегги.

Прежде чем проверять человека, следует убедиться в том, что он не был проверен ранее. Для этого мы будем вести список уже проверенных людей.

А вот окончательная версия кода поиска в ширину, в которой учтено это обстоятельство:

def search(name):

    search_queue = deque()

    search_queue += graph[name]

    searched = []   Этот массив используется для отслеживания уже проверенных людей

    while search_queue:

        person = search_queue.popleft()

        if not person in searched:   Человек проверяется только в том случае, если он не проверялся ранее

            if person_is_seller(person):

                print person + " is a mango seller!"

                return True

            else:

                search_queue += graph[person]

                searched.append(person)      Человек помечается как уже проверенный

    return False

search("you")

Попробуйте выполнить этот код самостоятельно. Замените функцию person_is_seller чем-то более содержательным и посмотрите, выведет ли она то, что вы ожидали.

Время выполнения

Если поиск продавца манго был выполнен по всей сети, значит, вы прошли по каждому ребру (напомню: ребром называется соединительная линия или линия со стрелкой, ведущая от одного человека к другому). Таким образом, время выполнения составляет как минимум O(количество ребер).

Также в программе должна храниться очередь поиска. Добавление одного человека в очередь выполняется за постоянное время: O(1). Выполнение операции для каждого человека потребует суммарного времени O(количество людей). Поиск в ширину выполняется за время O(количество людей + количество ребер), что обычно записывается в форме O(V+E) (V — количество вершин, E — количество ребер).

Упражнения

Перед вами небольшой граф моего утреннего распорядка.

Из графа видно, что я завтракаю только