На этом шаге рассмотрим реализацию алгоритма поиска в ширину.
Начинаем с создания очереди. В Python для создания двусторонней очереди (дека) используется функция deque:
from collections import deque search_queue = deque() #Создание новой очереди search_queue += graph ["you"] #Все соседи добавляются в очередь поиска
Выражение graph ["Алекса"] вернет список всех ваших соседей, например ["Алиса", "Боб", "Клэр"]. Все они добавляются в очередь поиска.
Рассмотрим реализацию алгоритма поиска ближайшего к вам продавца канцелярских товаров.
while search_queue: person = search_queue. popleft() if person_is_seller(person) : print person + " поиск завершен! " return True else: search_queue += graph[person] return False
Нужно определить функцию person_is_seller, которая сообщает, является ли человек продавцом канцелярии (для простоты будем считать продавцом канцелярии человека, у которого имя заканчивается на "п"). Например, функция может выглядеть так:
def person_is_seller(name): return name[-1] == 'п'
Эта функция проверяет, заканчивается ли имя на букву "п", и если заканчивается, этот человек считается продавцом канцелярских товаров.
На следующем шаге продолжим рассматривать алгоритм поиска в ширину.
