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

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

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

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

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 — количество ребер).

Упражнения

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

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

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

1. Проснуться.

2. Принять душ.

3. Почистить зубы.

4. Позавтракать.

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

1. Проснуться.

2. Почистить зубы.

3. Принять душ.

4. Позавтракать.

6.3 Для каждого из следующих трех списков укажите, действителен он или недействителен.

А

б

в

1. Проснуться

2. Принять душ

3. Позавтракать

4. Почистить зубы

1. Проснуться

2. Почистить зубы

3. Позавтракать

4. Принять душ

1. Принять душ

2. Проснуться

3. Почистить зубы

4. Позавтракать

6.4 Немного увеличим исходный граф. Постройте действительный список для этого графа.

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

Допустим, имеется генеалогическое древо.

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

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

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

Шпаргалка

• Поиск в ширину позволяет определить, существует ли путь из A в B.

• Если путь существует, то поиск в ширину находит кратчайший путь.

• Если в вашей задаче требуется найти «кратчайшее X», попробуйте смоделировать свою задачу графом и воспользуйтесь поиском в ширину для ее решения.

• В направленном графе есть стрелки, а отношения действуют в направлении стрелки (Рама —> Адит означает «Рама должен Адиту»).

• В ненаправленных графах стрелок нет, а отношение идет в обе стороны (Росс – Рэйчел означает «Росс встречается с Рэйчел, а Рэйчел встречается с Россом».)

• Очереди относятся к категории FIFO («первым вошел, первым вышел»).

• Стек относится к категории LIFO («последним пришел, первым вышел»).

• Людей следует проверять в порядке их добавления в список поиска, поэтому список поиска должен быть оформлен в виде очереди, иначе найденный путь не будет кратчайшим.

• Позаботьтесь о том, чтобы уже проверенный человек не проверялся заново, иначе может возникнуть бесконечный цикл.

7. Алгоритм Дейкстры