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

Вероятно, простейшим алгоритмом для проверки связности 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, ..., L., то уровень Lj+1 состоит из всех узлов, не принадлежащих ни одному из предшествующих уровней и со- единенных ребром с узлом уровня L.

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

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

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

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

На рис. 3.3 изображен процесс построения дерева BFS с корнем в узле 1 для графа, изображенного на рис. 3.2. Сплошными линиями обозначены ребра T, а пунктирными — ребра G, не принадлежащие T. Ход выполнения алгоритма BFS, приводящего к построению этого дерева, можно описать следующим образом.

Рис. 3.3. Построение дерева поиска в ширину T для графа на рис. 3.2; фазы (a), (b) и (c) обозначают добавляемые уровни. Сплошными линиями обозначаются ребра T; пунктирные ребра входят в компоненту связности G, содержащую узел 1, но не

принадлежащую T


(a) Начиная от узла 1 уровень L1 состоит из узлов {2, 3}.

(b) Затем для построения уровня L2 узлы L1 последовательно проверяются в некотором порядке (допустим, сначала 2, а потом 3). При проверке узла 2 обнаруживаются узлы 4 и 5, поэтому узел 2 становится их родителем. При проверке узла 2 также обнаруживается ребро к узлу 3, но оно не добавляется в дерево BFS, потому что узел 3 нам уже известен.

Узлы 7 и 8 впервые обнаруживаются при проверке узла 3. С другой стороны, ребро от 3-го к 5-му становится еще одним ребром G, которое не включается в T, потому что к моменту обнаружения этого ребра, выходящего из узла 3, узел 5 уже известен.

(c) Затем по порядку проверяются узлы уровня L2. Единственным новым узлом, обнаруженным при проверке L2, оказывается узел 6, который добавляется в уро- вень L3. Обратите внимание: ребра (4, 5) и (7, 8) не добавляются в дерево BFS, потому что они не приводят к обнаружению новых узлов.

(d) При проверке узла 6 новые узлы не обнаруживаются, поэтому в уровень L4 ничего не добавляется, и работа алгоритма на этом завершается. Полное дере- во BFS изображено на рис. 3.3(c).

Стоит заметить, что при выполнении алгоритма BFS для этого графа ребра, не входящие в дерево, соединяют либо узлы одного уровня, либо узлы смежных уровней. Сейчас мы докажем, что это свойство присуще деревьям BFS вообще.

(3.4) Пусть T — дерево поиска в ширину, x и у — узлы T, принадлежащие уров- ням L. и L. соответственно, а (x, у) — ребро G. В таком случае i и j отличаются не более чем на 1.

Доказательство. Действуя от противного, предположим, что i и j отличаются более чем на 1 — например, что i < j - 1. Рассмотрим точку алгоритма BFS, в кото- рой проверяются ребра, инцидентные x. Так как x принадлежит уровню L, то все узлы, обнаруженные от x, принадлежат уровням L+ и менее; следовательно, если у является соседом x, то этот узел должен быть обнаружен к текущему моменту, а это означает, что он должен принадлежать уровню L+1 и менее. ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Поиск в ширину:

  1. Поиск смысла жизни – это поиск бессмертия!
  2. ПОИСК ИНФОРМАЦИОННЫЙ
  3. ЧАСТЬ 2 В ПОИСКАХ УТРАЧЕННОГО «Я»
  4. ТЕОРИЯ ПОИСКА СМЫСЛА ЖИЗНЕННОГО
  5. Направление поиска работы
  6. Направление поиска работы
  7. 3.11.6. Поиск на ощупь
  8. Направление поиска работы
  9. Направление поиска работы
  10. Направление поиска работы
  11. Направление поиска работы
  12. Направление поиска работы
  13. Направление поиска работы
  14. Направление поиска работы
  15. Направление поиска работы
  16. Направление поиска работы
  17. Направление поиска работы
  18. Направление поиска работы
  19. Направление поиска работы
  20. Направление поиска работы