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

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

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

Если в примере на рис. 3.2 начать с узла 1, первый уровень будет состоять из узлов 2 и 3, второй — из узлов 4, 5, 7 и 8, а третий только из узла 6. На этой стадии поиск останавливается, потому что новых узлов уже не осталось (обратите внимание на то, что узлы 9–13 остаются недостижимыми для поиска).

Как наглядно показывает этот пример, у алгоритма имеется естественная физическая интерпретация. По сути, мы начинаем с узла 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. Дерево, построенное таким образом, называется деревом поиска в ширину.