Поиск в ширину

Вероятно, простейшим алгоритмом для проверки связности s–t является алгоритм поиска в ширину (BFS), при котором просмотр ведется от s во все возможных на- правлениях с добавлением одного «уровня» за раз.

Таким образом, алгоритм на- чинает с s и включает в поиск все узлы, соединенные ребром с s, — так формируется первый уровень поиска. Затем включаются все узлы, соединенные ребром с любым узлом из первого уровня, — второй уровень. Просмотр продолжается до того мо- мента, когда очередная попытка не обнаружит ни одного нового узла.

Как наглядно показывает этот пример, у алгоритма имеется естественная фи- зическая интерпретация. По сути, мы начинаем с узла s и последовательно «за- тапливаем» граф расширяющейся волной, которая стремится охватить все узлы, которых может достичь. Уровень узла представляет момент времени, в который данный узел будет достигнут при поиске.

Уровни L1, L2, L3, …, создаваемые алгоритмом BFS, более точно определяются следующим образом:

• Уровень L1 состоит из всех узлов, являющихся соседями s. (Для удобства записи мы иногда будем использовать уровень L0 для обозначения множества, состо- ящего только из s.)
• Если предположить, что мы определили уровни L1, …, Lj, то уровень Lj+1 состоит из всех узлов, не принадлежащих ни одному из предшествующих уровней и со- единенных ребром с узлом уровня Lj.

Если вспомнить, что расстояние между двумя узлами определяется как мини- мальное количество ребер в пути, соединяющем эти узлы, становится понятно, что уровень L1 представляет собой множество всех узлов, находящихся на расстоянии 1 от s, или в более общей формулировке — уровень Lj представляет собой множество всех узлов, находящихся от s на расстоянии ровно j.

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

(3.3) Для каждого j ≥ 1 уровень Lj, создаваемый алгоритмом BFS, состоит из всех узлов, находящихся от s на расстоянии ровно j. Путь от s к t существует в том, и только в том случае, если узел t встречается на каком-либо уровне.

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

А конкретнее, для каждого узла v (отличного от s) рассмотрим момент, когда v впервые «обнаруживается» алгоритмом BFS; это происходит в тот момент, когда проверяется некоторый узел u из уровня Lj и обнаруживается, что из этого узла ребро ведет к узлу v, который не встречался ранее.

В этот момент ребро (u, v) добавляется в дерево T — u становится родителем v, представляя тот факт, что u «отвечает» за завершение пути к v. Дерево, построенное таким образом, называется деревом поиска в ширину.