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

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

Оценим время работы описанной процедуры. В
процессе работы вершины только темнеют, так что каждая вершина кладётся в
очередь не более одного раза (благодаря проверке в строке 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.