Поиск в ширину в графе

Теперь рассмотрим несколько иной метод поиска в графе, называемый поиском в ширину (англ.: breadth first search). Прежде чем описать его, отметим, что при поиске в глубину чем позднее будет посещена вершина, тем раньше она будет использована — точнее, так будет при допущении, что вторая вершина посещается перед использованием первой. Это прямое следствие того факта, что просмотренные, но еще не использованные вершины скапливаются в стеке. Поиск в ширину, грубо говоря, основывается на замене стека очередью. После такой модификации чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью просмотра сразу всех еще непросмотренных соседей этой вершины. Вся процедура представлена ниже:

1. procedure WS (v); (* поиск в ширину в графе с началом в вершине v; переменные НОВЫЙ, ЗАПИСЬ-глобальные*}
2. begin
3. ОЧЕРЕДЬ:=ø; ЗАПИСЬ<= v; НОВЫЙ[ v ]:=ложь
4. while ОЧЕРЕДЬ ≠ ø do
5. begin p <= ОЧЕРЕДЬ; посетить p;
6. for u є ЗАПИСЬ[ p ] do
7. if НОВЫЙ[ u ] then
8. begin ОЧЕРЕДЬ<=[ u ]; НОВЫЙ[ u ]:=ложь
9. end
10. end
11. end

Способом, аналогичным тому, какой был применен для поиска в глубину, можно легко показать, что вызов процедуры WS(u) приводит к посещению всех вершин связной компоненты графа, содержащей вершину v. причем каждая вершина просматривается в точности один раз. Вычислительная сложность поиска в ширину также имеет порядок m + n, так как каждая вершина помещается в очередь и удаляется из очереди в точности один раз, а число итераций цикла б, очевидно, будет иметь порядок числа ребер графа.

Оба вида поиска в графе — в глубину и в ширину могут быть использованы для нахождения пути между фиксированными вершинами v и u. Достаточно начать поиск в графе с вершины v и вести его до момента посещения вершины u. Преимуществом поиска в глубину является тот факт, что в момент посещения вершины u стек содержит последовательность вершин, определяющую путь из v в u. Это становится очевидным, если отметить, что каждая вершина, помещаемая в стек, является соседом верхнего элемента в стеке. Однако недостатком поиска в глубину является то, что полученный таким образом путь в общем случае не будет кратчайшим путем из v в u.

От этого недостатка свободен метод нахождения пути, основанный на поиске в ширину. Модифицируем процедуру WS, заменяя строки 7-9 на if НОВЫЙ[ u ]

then
begin ОЧЕРЕДЬ<= u; НОВЫЙ[ u ]:=ложь
end

По окончании работы модифицированной таким образом процедуры таблица ПРЕДЫДУЩИЙ содержит для каждой просмотренной вершины u вершину ПРЕДЫДУЩИЙ[ u ], из которой мы попали в u. Отметим, что кратчайший путь из u в v обозначается последовательностью вершин u = u ₁, u ₂,..., u _k = v, где u _i+1 = ПРЕДЫДУЩИЙ[ u _i] для 1 ≤ i < k и k является первым индексом i, для которого u _i = v. Действительно, в очереди помещены сначала вершины, находящиеся на расстоянии 0 от v (т.е. сама вершина v), затем поочередно все новые вершины, достижимые из v, т.е. вершины, находящиеся на расстоянии 1 от v и т.д. Под расстоянием здесь мы понимаем длину кратчайшего пути. Предположим теперь, что мы уже рассмотрели все вершины, находящиеся на расстоянии, не превосходящем r, от u, что очередь содержит все вершины, находящиеся от v на расстоянии r, и только эти вершины и что таблица ПРЕДЫДУЩИЙ правильно определяет кратчайший путь от каждой, уже просмотренной вершины до u способом, описанным выше. Использовав каждую вершину р, находящуюся в очереди, наша процедура просматривает некоторые новые вершины, и каждая такая новая вершина u находится, очевидно, на расстоянии r + 1 от v, причем, определяя ПРЕДЫДУЩИЙ[ u ]:= р, мы продлеваем кратчайший путь от р до v до кратчайшего пути от u до v. После использования всех вершин из очереди, находящихся на расстоянии r от u, она (очередь), очевидно, содержит множество вершин, находящихся на расстоянии r + 1 от v, и легко заметить, что условие индукции выполняется и для расстояния r + 1.

Дата добавления: 2014-01-07