Деревья поиска в ширину

Анализ поиска в ширину

 

Оценим время работы описанной процедуры. В
процессе работы вершины только темнеют, так что каждая вершина кладётся в
очередь не более одного раза (благодаря проверке в строке 12). Следовательно,
и вынуть её можно только один раз. Каждая операция с очередью требует O
(1) шагов, так что всего на операции с очередью уходит время O(V). Теперь
заметим, что список смежных вершин просматривается, лишь когда вершина
извлекается из очереди, то есть не более одного раза. Сумма длин всех этих
списков равна |Е| (2|Е| для неориентированного графа) и всего на их обработку
уйдёт время O(Е). Инициализация требует O(V) шагов, так что всего полу-
чается O(V + Е). Тем самым время работы процедуры BFS пропорционально
размеру представления графа G в виде списков смежных вершин.

Поиск в ширину для полного обхода графа с n вершинами и m дугами требует столько же времени, как и поиск в глубину, то есть времени порядка O(max(n, m)). Поскольку обычно m ³ n, то получается O(m).

 

В ходе работы процедуры BFS выделяется некоторый подграф – дерево
поиска в ширину, задаваемое полями [v]. Более формально, применим процеду-
ру BFS к графу G = (V, Е) с начальной вершиной s. Рассмотрим подграф,
вершинами которого являются достижимые из s вершины, а рёбрами являются
рёбра ([v], v) для всех достижимых v, кроме s.

Лемма 5.1.Построенный таким образом подграф графа G представляет
собой дерево, в котором для каждой вершины v имеется единственный простой
путь из s в v. Этот путь будет кратчайшим путём из s в v в графе G.

Доказательство. Существование пути из s в и (как и то, что он будет крат-
чайшим) следует из теоремы 5.1. (индукция по расстоянию от s до v). Поэтому
граф связен. Поскольку число рёбер в нём на единицу меньше числа вершин,
то он является деревом.

Дерево называется подграфом предшествования (predecessor subgraph), а
также деревом поиска в ширину (breadth-first tree)для данного графа и данной начальной вершины. (Заметим, что построенное дерево зависит от того, в каком порядке просматриваются вершины в списках смежных вершин.)

Если значения полей уже вычислены с помощью процедуры BFS, то крат-
чайшие пути из s легко найти: их печатает процедура PRINT-PATH.

 

Листинг 5.3 – Поиск в глубину

 

Время выполнения пропорционально длине печатаемого пути (каждый рекурсивный вызов уменьшает расстояние от s на единицу).