Поиск в ширину
Если в примере на рис. 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 и менее. ■
Еще по теме Поиск в ширину:
- Поиск смысла жизни – это поиск бессмертия!
- ПОИСК ИНФОРМАЦИОННЫЙ
- ЧАСТЬ 2 В ПОИСКАХ УТРАЧЕННОГО «Я»
- ТЕОРИЯ ПОИСКА СМЫСЛА ЖИЗНЕННОГО
- Направление поиска работы
- Направление поиска работы
- 3.11.6. Поиск на ощупь
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы
- Направление поиска работы