На этом шаге продолжим рассматривать реализацию алгоритма поиска в ширину.
У Клэр и Боба есть один общий друг: Филипп. Следовательно, Филипп будет добавлен в очередь дважды: при добавлении друзей Клер и при добавлении друзей Боба. В результате Филипп появится в очереди поиска в двух экземплярах.
Но проверить, является ли Филипп продавцом кнцелярии, достаточно всего один раз. Проверяя его дважды, вы выполняете лишнюю, ненужную работу. Следовательно, после проверки человека нужно пометить как проверенного, чтобы не проверять его снова.
Если этого не сделать, может возникнуть бесконечный цикл. Предположим, граф выглядит так:
В начале очеередь поиска содержит всех ваших соседей (Клэр). Теперь вы проверяете Клэр. Она не является продавцом канцтоваров, поэтому все ее соседи добавляются в очередь поиска (а это Алекса). Вы проверяете себя. Вы не являетесь продавцом, поэтому все ваши соседи добавляются в очередь поиска (а это стова Клэр). И так далее. Возникает бесконечный цикл, потому что очередь поиска будет поочередно переходить от Алексы к Клэр. Прежде чем проверять человека, следует убедиться в том, что он не был проверен ранее. Для этого мы будем вести список уже проверенных людей. А вот окончательная версия кода поиска в ширину, в которой учтено это обстоятельство:
from collections import deque graph = {} graph["Алекса"] = ["Алиса", "Боб", "Клэр"] graph["Алиса"] = ["Пэгги","Чак"] graph["Клэр"] = ["Филипп"] graph["Боб"] = ["Филипп","Анна"] graph["Пэгги"] = [] graph["Чак"] = [] graph["Филипп"] = [] graph["Анна"] = [] def person_is_seller(name): return name[-1] == 'п' 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 + ". Поиск завершен! ") return True else: search_queue += graph[person] searched.append(person) return False search("Алекса")
Архив с примером можно взять здесь.
На следующем шаге познакомимся с алгоритмом Дейкстры.
