Алгоритмы и структуры данных

В худшем случае этот алгоритм дает временную сложность T_max(n), пропорциональную O(n³).

2.6.2. Алгоритмы обхода графа

При решении многих задач, касающихся графов, необходимы эффективные методы систематического обхода вершин и ребер графов. К таким методам относятся:

- поиск в глубину;

 

- поиск в ширину.

Эти методы чаще всего рассматриваются на ориентированных графах, но они применимы и для неориентированных, ребра которых считаются двунаправленными.

2.6.2.1. Поиск в глубину

Поиск в глубину является обобщением метода обхода дерева в прямом порядке (см. 1.3.4.2).

Предположим, что есть ориентированный граф G, в котором первоначально все вершины помечены как непосещенные. Поиск в глубину начинается с выбора начальной вершины v графа G, и эта вершина помечается как посещенная. Затем для каждой вершины, смежной с вершиной v и которая не посещалась ранее, рекурсивно применяется поиск в глубину. Когда все вершины, которые можно достичь из вершины v, будут «удостоены» посещения, поиск заканчивается. Если некоторые вершины остались не посещенными, то выбирается одна из них и поиск повторяется. Этот процесс продолжается до тех пор, пока обходом не будут охвачены все вершины орграфа G.

Этот метод обхода вершин орграфа называется поиском в глубину, поскольку поиск непосещенных вершин идет в направлении вперед (вглубь) до тех пор, пока это возможно. Например, пусть x - последняя посещенная вершина. Для продолжения процесса выбирается какая-либо нерассмотренная дуга x ^ y, выходящая из вершины x. Если вершина у уже посещалась, то ищется другая вершина, смежная с вершиной x. Если вершина y ранее не посещалась, то она помечается как посещенная и поиск начинается заново от вершины y. Пройдя все пути, которые начинаются в вершине y, возвращаемся в вершину x, т. е. в ту вершину, из которой впервые была достигнута вершина y. Затем продолжается выбор нерассмотренных дуг, исходящих из вершины x, и так до тех пор, пока не будут исчерпаны все эти дуги (рис. 51).

Для представления вершин, смежных с вершиной v, можно использовать список смежных (см. 1.3.3.2), а для определения вершин, которые ранее посещались, - массив Visited:

Graph: TAdjacencyList;

Visited: array[1..n]  of boolean;

Чтобы применить эту процедуру к графу, состоящему из n вершин, надо сначала присвоить всем элементам массива Visited значение false, затем начать поиск в глубину для каждой вершины, помеченной как false.

155

Procedure DepthSearch(v:  integer); begin

Visited[v]   := true;

for каждой вершины y,  смежной с v do if not Visited[y]  then DepthSearch(y);

end; begin

while есть непомеченные вершины do begin v := любая непомеченная вершина; DepthSearch(v); end; end.

Поиск в глубину для полного обхода графа с n вершинами и m дугами требует общего времени порядка O(max(n, m)). Поскольку обычно m > n, то получается O(m).

2.6.2.2. Поиск в ширину (волновой алгоритм)

Этот алгоритм поиска в графе также называют волновым алгоритмом из-за того, что обход графа идет по принципу распространения волны. Волна растекается равномерно во все стороны с одинаковой скоростью. На i-м шаге будут помечены все вершины, достижимые за i ходов, если ходом считать переход из одной вершины в другую.

 

Метод поиска в ширину получается из программы поиска в глубину (см. 2.6.2.1), если заменить стек возврата на очередь. Эта простая замена модифицирует порядок обхода вершин так, что обход идет равномерно во все стороны, а не вглубь как при поиске в глубину (рис. 52).

Здесь используются те же структуры Graph и Visited, что были описаны в алгоритме поиска в глубину.

Procedure WidthSearch(v:  integer); var

Delayed: array[1..n] of integer;  {Очередь} 
Count, {Хвост очереди}

Head: integer; {Голова очереди}

Current, j: integer; begin

Count := 1; Head := 0; Delayed[Count]   := v;

Visited[v]   := true;

repeat

Head := Head +1;    Current := Delayed[Head]; for каждой вершины y, смежной с Current do if not Visited[y]  then begin Count := Count + 1; Delayed[Count]   := Graph[y]; Visited[y]   := true; end;

until Count = Head; end; begin

while есть непомеченные вершины do begin

v := любая непомеченная вершина;

WidthSearch(v); end;

Поиск в ширину для полного обхода графа с n вершинами и m дугами требует столько же времени, как и поиск в глубину, т. е. времени порядка O(max(n, m)). Поскольку обычно m > n, то получается O(m).

2.6.3. Нахождение кратчайшего пути

Здесь рассматриваются алгоритмы нахождения путей в ориентированном графе. Эти алгоритмы работают на ориентированном графе, у которого все дуги имеют неотрицательные метки (стоимости дуг). Задача алгоритмов состоит в нахождении кратчайших путей между вершинами графа. Длина пути здесь определяется как сумма меток (длин) дуг, составляющих путь.

2.6.3.1. Алгоритм Дейкстры

Этот алгоритм находит в графе кратчайший путь из заданной вершины, определенной как источник, во все остальные вершины.

В процессе своей работы алгоритм строит множество S вершин, для которых кратчайшие пути от источника уже известны. На каждом шаге к множеству S добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. При этом используется массив D, в который записываются длины кратчайших путей для каждой вершины. Когда множество S будет содержать все вершины графа, тогда массив D будет содержать длины кратчайших путей от источника к каждой вершине.

Помимо указанных массивов, в алгоритме Дейкстры используется матрица длин C, где элемент C[i, j] - метка (длина) дуги (i, j), если дуги нет, то ее длина полагается равной бесконечности, т. е. больше любой фактической длины дуг. Фактически, матрица C представляет собой матрицу смежности, в которой все нулевые элементы заменены на бесконечность.

Для определения самого кратчайшего пути (т. е. последовательности вершин) необходимо ввести еще один массив P вершин, где P[v] содержит вершину, непосредственно предшествующую вершине v в кратчайшем пути (рис. 53).

Алгоритм:

procedure Dijkstra; begin

S := источник;

for i := 2 to n do begin

D[i]   := С[источник, i]; P[i]   := источник; end;

for i := 1 to n-1 do begin

выбор из множества V\S такой вершины w,

что значение D[w] минимально; добавить w к множеству S;

for каждая вершина v из множества V\S do begin D[v]   := min(D[v], D[w]  + C[w, v]); if D[w]  + C[w, v]< D[v]  then P[v]   := w; end; end; end;

Рис. 53. Алгоритм Дейкстры

После выполнения алгоритма кратчайший путь к каждой вершине можно найти с помощью обратного прохождения по предшествующим вершинам массива P, начиная от конечной вершины к источнику.

Время выполнения этого алгоритма, если для представления графа используется матрица смежности, имеет порядок O(n²), где n - количество вершин графа.

2.6.3.2. Алгоритм Флойда

Этот алгоритм решает задачу нахождения кратчайших путей между всеми парами вершин графа. Более строгая формулировка этой задачи следующая: есть ориентированный граф G = (V, Е), каждой дуге (v, w) этого графа сопоставлена неотрицательная стоимость C[v, w]. Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин (v, w) любого пути из вершины v в вершину w, длина которого минимальна среди всех возможных путей из вершины v к w.

Можно решить эту задачу, последовательно применяя алгоритм Дей-кстры для каждой вершины, объявляемой в качестве источника. Но существует прямой способ решения данной задачи, использующий алгоритм Флойда. Для определенности положим, что вершины графа последовательно пронумерованы от 1 до n. Алгоритм Флойда использует матрицу A размера nXn, в которой вычисляются длины кратчайших путей. В начале A[i, j] = C[i, j] для всех i < > j. Если дуга (i, j) отсутствует, то C[i, j] = °°. Каждый диагональный элемент матрицы A равен 0.

Над матрицей A выполняется n итераций. После k-й итерации A[i, j] содержит значение наименьшей длины путей из вершины i в вершину j, которые не проходят через вершины с номером, большим k. Другими словами, между концевыми вершинами пути i иj могут находиться только вершины, номера которых меньше или равны k (рис. 54).

На k-й итерации для вычисления матрицы A применяется следующая формула: А$}, j] = min(Ak_i[i, j], A^i, k] + A^[k, j]).

Нижний индекс k обозначает значение матрицы А после k-й итерации, но это не означает, что существует n различных матриц, этот индекс используется для сокращения записи.

Равенства A^[i, k] = A^[i, k] и A^[k, j] = A^[k, j] означают, что на k-й итерации элементы матрицы A, стоящие в k-й строке и k-м столбце, не изменяются. Более того, все вычисления можно выполнить с применением только одного экземпляра матрицы A. Представим алгоритм Флойда в виде следующей процедуры:

procedure Floyd  (var A: array[1..n,  1..n]  of real;

С: а^тау^..^ 1..n] of real);

var

i, j, k: integer; begin

for i := 1 to n do

for j  := 1 to n do A[i, j]   := C[i, j]; for i := 1 to n do A[i, i]   := 0; for k := 1 to n do for i := 1 to n do for j  : = 1 to n do

if (A[i, k] + A[k, j]) < A[i, j] then

A[i, j] := A[i, k] + A[k, j];

end;

Следует заметить, что если в графе существует контур отрицательной суммарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, «прокрутившись» в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае, описанном выше, алгоритм Флойда не применим. Останавливаясь подробнее надо заметить, что если граф неориентированный, то ребро с отрицательным весом является как раз таким контуром (проходя по нему в обоих направлениях столько раз пока не сделаем вес достаточно малым).

Заметим, что если граф неориентированный, то все матрицы, получаемые в результате преобразований симметричны и, следовательно, достаточно вычислять только элементы расположенные выше главной диагонали.

Время выполнения этого алгоритма, очевидно, имеет порядок O(n³), поскольку в нем присутствуют вложенные друг в друга три цикла.

2.6.3.3. Переборные алгоритмы

Рассмотрим переборные алгоритмы, основанные на методах обхода графа (см. п. 2.6.2) на примере задачи нахождения кратчайшего пути в лабиринте. Поскольку существует два метода обхода графа, то и переборных алгоритмов будем рассматривать два.

Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером mXn. Элемент матрицы A[i, j] = 0, если клетка (i, j) проходима. В противном случае A[i, j] = °°.

Требуется найти кратчайший путь из клетки (1, 1) в клетку (m, n).

Фактически дана инвертированная матрица смежности (в ней нули заменены °°, а единицы - нулями). Лабиринт представляет собой граф.

Метод перебора с возвратом (по-английски называемый backtracking) основан на методе поиска в глубину. Перебор с возвратом - это метод проб и ошибок («попробуем сходить в эту сторону: не получится - вернемся и попробуем в другую»). Поскольку речь идет о переборе вариантов методом поиска в глубину, то во время работы алгоритма надо хранить текущий путь в дереве. Этот путь представляет собой стек Way. Кроме того, необходим массив Dest, размерность которого соответствует количеству вершин графа, хранящий для каждой вершины расстояние от нее до исходной вершины.

Вернемся к нашей задаче. Пусть текущей является некоторая клетка (в начале работы алгоритма - клетка (1, 1)). Далее

if для текущей клетки есть клетка-сосед Neighbor, такая что: (отсутствует в Way) and

(Dist[Neighbor]=0 or (Dist[Neighbor] > Length(Way))) then begin добавить Neighbor в Way; текущая клетка := Neighbor; end else

извлечь из Way;

Из приведенного выше фрагмента ясно, почему этот метод называется перебором с возвратом. Возврату здесь соответствует операция «извлечь из Way», которая уменьшает длину Way на 1.

Перебор заканчивается, когда Way пуст и делается попытка возврата назад. В этой ситуации возвращаться уже некуда (рис. 55).

Way - это путь текущий, но в процессе работы необходимо хранить еще и оптимальный путь OptimalWay.

Заметим, что алгоритм можно усовершенствовать, если не позволять, чтобы длина Way была больше или равна длине OptimalWay. В этом случае если и будет найден какой-то вариант большей длины, он заведомо не будет оптимальным. Такое усовершенствование в общем случае означает, что как только текущий путь станет заведомо неоптимальным, надо вернуться назад. В некоторых случаях это улучшение алгоритма позволяет сильно сократить перебор.

Переборный алгоритм, основанный на поиске в ширину, состоит из двух этапов:

1. распространение волны;
2. обратный ход.

Распространение волны и есть собственно поиск в ширину (см. п. 2.6.2.2), при котором клетки помечаются номером шага метода, на

 

 

котором клетка посещается. При обратном ходе, начиная с конечной вершины, идет восстановление кратчайшего пути, по которому в нее попали путем включения в него клеток с минимальной пометкой.

Важно, что восстановление начинается с конца (с начала оно зачастую невозможно) (рис. 56).

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

2.6.4. Нахождение минимального остовного дерева

Приведем без доказательства следующее свойство MST (minimal spanning tree - минимальное остовное дерево на английском языке).

В графе G = (V, E) рассмотрим U - некоторое подмножество V, такое что Uи V\Uне пусты. Пусть (u, v) - ребро наименьшей стоимости, одна вершина которого - u e U, а другая - v e V\U. Тогда существует некоторое MST, содержащее ребро (u, v). Пример графа G и его минимального основного дерева приведен на рис. 57.

На этом свойстве основаны два известных алгоритма.

2.6.4.1. Алгоритм Прима

В этом алгоритме строится множество вершин U, из которого «вырастает» остовное дерево (рис. 58).

Сначала U = 0. На каждом шаге алгоритма находится ребро наименьшей стоимости (u, v) такое, что u e U, v e V\U, затем вершина v переносится из V\U в U. Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V:

U := 0;

U:= U u любая вершина;

164

Очевидно, данный алгоритм для графа с n вершинами имеет сложность, пропорциональную O(n²)

2.6.4.2. Алгоритм Крускала