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

В ходе работы процедуры 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 на единицу).