3.3. Алгоритм поиска в ширину(очередь – queue)
Основная идея такого поиска – последовательный просмотр списков инцидентности вершин, смежных с данной. При поиске в ширину, попав в новую вершину, просматривают все смежные с ней непросмотренные вершины и заносит их в список, после чего эта вершина считается обработанной. Далее переходят в новую вершину, стоящую первой в списке необработанных вершин. Иными словами, просмотр осуществляется по принципу очереди: чем раньше вершина просмотрена, тем раньше она будет обработана.
Например, для графа, изображенного на рис. 3.1, последовательность просмотра вершин с помощью поиска в ширину имеет вид: 1, 2, 4, 7, 5, 6, 3.
Сложность реализации алгоритма в том, что рекурсивные процедуры действуют по принципу стека, а не очереди. Поэтому в этом случае возможен только нерекурсивный вариант алгоритма.
procedure BREADTH( v ) ;
begin ОЧЕРЕДЬ:=; {ОЧЕРЕДЬ – локальная структура }
ОЧЕРЕДЬ v; NOWY[v]:= False;
while ОЧЕРЕДЬ <> do
begin p ОЧЕРЕДЬ; write(p);
for u СПИСОК[p] do
If nowy[u] then
begin ОЧЕРЕДЬ u;
NOWY[u]:= False
end
end
end;
Как мы уже говорили,
основная программа отличается от
соответствующей программы поиска в
глубину только именем вызываемой во
втором цикле процедуры. Аналогично
можно показать, что алгоритм корректен,
а его вычислительная сложность также
равна
.
3.4. Модификации алгоритмов
С помощью алгоритмов поиска в глубину и в ширину легко решаются следующие задачи:
Определение числа связных компонент графа.
Для этого в основной программе вводится переменная, обозначающая число связных компонент, которая увеличивается при обнаружении каждой непросмотренной вершины в этой программе.
2. Поиск маршрута (пути) между двумя фиксированными вершинами u и v и определение его длины.
Маршрут (путь) строится с помощью любого алгоритма поиска. Поиск начинается из вершины u и продолжается, пока не встретится вершина v или не произойдет возврат в основную программу. Если после возврата из процедуры вершина v не найдена, значит нужного маршрута (пути) не существует, и задача не имеет решения.
3.5. Путь минимального веса в графе. Алгоритм Флойда
Предположим, что каждому ребру графа присвоен некоторый вес (е). Необходимо построить такой путь, чтобы суммарный вес входящих в него ребер был минимален. Чаще всего вес ребра ассоциируют с длиной, поэтому задачу называют задача о кратчайшем пути, хотя в разных прикладных задачах его смысл может быть различным.
Существует много модификаций и методов решения этой задачи, зависящих от свойств графа (ориентированный или неориентированный, есть ли в нем контуры и т.д.), так и от свойств весов (неотрицательные или произвольные и т.д.). Одной из самых популярных является задача поиска кратчайших путей между всеми парами вершин. Для ее решения найден весьма эффективный алгоритм, созданный Уоршаллом и Флойдом.
Идея
алгоритма следующая. Пусть граф имеет
n
вершин. Обозначим aij
– расстояние между вершинами vi
и vj
(aij
= (
vi,
vj),
если vi
и vj
смежны и aij
= +
в противном случае);
–
длина кратчайшего пути изvi
в vj
с промежуточными вершинами в множестве
{ v1,
v2
, …, vk
}.
Имеем следующие равенства:
Первое
равенство очевидно. Чтобы обосновать
второе уравнение, рассмотрим кратчайший
путь из vi
в vj
с промежуточными вершинами из множестве
{ v1,
v2
, …, vk,
vk+1}.
Если этот путь не содержит vk+1,
то 
,
иначе, деля путь из vi
в vj
на отрезки от vi
до vk+1
и от vk+1
до vj,
получим второе равенство. Заменяя во
втором уравнении k
+ 1 на k,
изменяющееся от 1 до n,
и убирая верхние индексы, получим
следующий алгоритм.
begin for i:=1 to n do
for j:=1 to n do D[i,j] := A[i,j];
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
D[i,j]:=min( D[i,j], D[i,k]+D[k,j] );
end.
Зная матрицу D[i, j] кратчайших расстояний между всеми парами вершин, несложно построить сам кратчайший путь между двумя заданными вершинами s и t. Предлагается следующий алгоритм, определяющий путь с его конца.
begin write(t);
v:=t;
while v <> s do
for u:=1 to n do
if( D[s,v] = D[s,u]+A[u,v] ) and (u<>v) then
begin write(u); v:=u; break; end;
end.
Вычислительная сложность алгоритма Флойда равна, очевидно, О(n3), т.к. необходимо выполнить тройной цикл от 1 до n.