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

while searchqueue: ч Пока очередь не пуста...
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[-l] == 'm'
Эта функция проверяет, заканчивается ли имя на букву «т», и если за­канчивается, этот человек считается продавцом манго. Проверка довольно глупая, но для нашего примера сойдет. А теперь посмотрим, как работает поиск в ширину.
sea*cVuy>eu£ = deque ()
S
ТЕКУЩЕЕ СОСТОЯНИЕ
SEARCH.QUEUE
ПУСТО

)ШСА КЛЭР	1боб1
J J J J	Л л
£лии КЛЭР	БОБ
J 3-^J У~)—	т j^J
КЛЭР J	БОБ ^ЛшГГ

earcV^ueue-Vo V\ (j“y>v’9
ПОйС.^ ulhiLe search.c^ueue:
П
^Ц’*^бКит^СЯKAVICK Ht
Ss&r-*


‘AV-^LYHK


if person _is_ seller Cpe^Tso^,'i)^: else-
searcV.^ueue + ' graph CpersovC) voVvile se.arc.V.
iF person.is. Se-Lucr(^person): else:
S earcVi^usue +• = graph Qersonj ... u ид. 3. ...


КЛЭР БОБ J J JJ


ГкЛЭР БОБ)
J J П


ti—тгзг


КЛЭР TJ -


БОБ
onr


ПЕГГИ\


n


БОБ
"J-J-


ПЕГГЙ]
J


БОБ


ПЕГГИ


J j j J
[Б0Б|ПЁТТЙ1


(jOpnp™}^^


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

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

ЕРЕМЕННАЯ PERSON ^ pgv'soh - 5взг*ск-йЫ««*.рорЕбРЬО СОДЕРЖИТ ALICE ^J
У Алисы и Боба есть один общий друг: Пегги. Следовательно, Пегги будет добавлена в очередь дважды: при добавлении друзей Алисы и при добав­лении друзей Боба. В результате Пегги появится в очереди поиска в двух экземплярах.

ОЙ, ПЕГГИ ВСТРЕЧАЕТСЯ В ОЧЕРЕДИ ПОИСКА

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

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

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

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

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

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

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

А
вот окончательная версия кода поиска в ширину, в которой учтено это обстоятельство: def search(name):
search_queue = deque() search queue += graph[name]
searched - [1 < Этот массив используется для отслеживания
while search_queue: уже проверенных людей
p
Человек проверяется только в том случае, если он не проверялся ранее

erson = search_queue.popleft() if not person in searched:
if person_is_seller(person):
print person + " is a mango seller!" return True
_el_se; Человек помечается как
search queue += graphfperson] уже проверенный
searched. append(person) ■*
return False
search("you")
Попробуйте выполнить этот код самостоятельно. Замените функцию person_is_seller чем-то более содержательным и посмотрите, выведет ли она то, что вы ожидали.
Время выполнения
Если поиск продавца манго был выполнен по всей сети, значит, вы прошли но каждому ребру (напомню: ребром называется соединительная линия или линия со стрелкой, ведущая от одного человека к другому). Таким образом, время выполнения составляет как минимум 0(количество ребер).
Также в программе должна храниться очередь поиска. Добавление одно­го человека в очередь выполняется за постоянное время: 0(1). Выпол­нение операции для каждого человека потребует суммарного времени 0{количество людей). Поиск в ширину выполняется за время 0(количество людей + количество ребер), что обычно записывается в форме 0( V+E) (V — количество вершин, Е — количество ребер).
Упражнения
Перед вами небольшой граф моего утреннего распорядка.

Из графа видно, что я завтракаю только после того, как почищу зубы. Таким образом, узел «Позавтракать» зависит от узла «Почистить зубы».

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

1. 
   Проснуться.
   
2. 
   Принять душ.
   
3. 
   Почистить зубы.
   
4. 
   Позавтракать.
   

Следует заметить, что действие «Принять душ» может перемещаться в спи­ске, поэтому следующий список тоже действителен:

1. 
   Проснуться.
   
2. 
   Почистить зубы.
   
3. 
   Принять душ.
   
4. 
   Позавтракать.
   

3. 
   Д
   
   1. 
      ПРОСНУТЬСЯ
      
   2. 
      ПРИНЯТЬ ДУШ
      
   3. 
      ПОЗАВТРАКАТЬ
      
   4. 
      ПОЧИСТИТЬ ЗУБЫ
      
   
   
   \. ПРОСНУТЬСЯ
   г. почистить зубы
   
   3. 
      ПОЗАВТРАКАТЬ
      
   4. 
      ПРИНЯТЬ ДУШ
      
   
   
   Т ПРИНЯТЬ ДУШ
   г. проснуться
   
   3. 
      ПОЧИСТИТЬ ЗУБЫ
      
   4. 
      ПОЗАВТРАКАТЬ
      
   
   ля каждого из следующих трех списков укажите, действителен он или недействителен.
   
4. 
   Н
   емного увеличим исходный граф. Постройте действительный список для этого графа.
   

Можно сказать, что этот список в некотором смысле отсортирован. Если задача А зависит от задачи В, то задача А находится в более поздней по­зиции списка. Такая сортировка называется топологической; фактически она предоставляет способ построения упорядоченного списка на основе графа. Предположим, вы планируете свадьбу и у вас составлен большой граф с множеством задач, но вы не знаете, с чего начать. Проведите топо­логическую сортировку графа — и получите список задач, которые можно выполнять одну за другой.
Допустим, имеется генеалогическое древо.

Генеалогическое древо — тоже граф, потому что в нем есть узлы (люди) и ребра. Ребра указывают на родителей человека. Естественно, все ребра направлены вниз — в генеалогическом дереве ребро, указывающее вверх, не имеет смысла. Ведь ваш отец никак не может быть дедушкой вашего дедушки!

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

5. 
   К
   акие из следующих графов также являются деревьями?
   

Шпаргалка

• 
  Поиск в ширину позволяет определить, существует ли путь из А в В.
  
• 
  Если путь существует, то поиск в ширину находит кратчайший путь.
  
• 
  Если в вашей задаче требуется найти «кратчайшее X», попробуйте смо­делировать свою задачу графом и воспользуйтесь поиском в ширину для ее решения.
  
• 
  В направленном графе есть стрелки, а отношения действуют в направле­нии стрелки (Рама -* Адит означает «Рама должен Адиту»),
  
• 
  В ненаправленных графах стрелок нет, а отношение идет в обе стороны (Росс - Рэйчел означает «Росс встречается с Рэйчел, а Рэйчел встреча­ется с Россом».)
  
• 
  Очереди относятся к категории FIFO («первым вошел, первым вышел»),
  
• 
  Стек относится к категории LIFO («последним пришел, первым вышел»),
  
• 
  Л
  юдей следует проверять в порядке их добавления в список поиска, поэтому список поиска должен быть оформлен в виде очереди, иначе найденный путь не будет кратчайшим.
  
• 
  Позаботьтесь о том, чтобы уже прове­ренный человек не проверялся заново, иначе может возникнуть бесконечный цикл.
  

А