38. Графы

В этом разделе мы рассмотрим некоторые алгоритмы обработки графов: поиск в глубину, поиск в ширину, метод ветвей и границ, топологическую сортировку, “волновой алгоритм” и алгоритм Дейкстры. Во всех примерах предполагается, что граф задан матрицей смежности, в которой элемент с индексами i,j равен 1, если вершины i и j смежны, и равен 0 в противном случае. Если граф ориентированный, то матрица не симметрична, для взвешенного графа элементы матрицы могут быть произвольными положительными числами или нулями. Вершины графа пронумерованы натуральными числами от 1 до n.

Поиск в глубину, или обход графа в глубину - это префиксный обход универсального покрытия графа. Универсальным покрытием называют дерево, которое получается следующим образом: в качестве корня выбирают произвольную вершину графа, вершинами первого уровня становятся все вершины графа, смежные с корневой вершиной, вершинами второго уровня - все вершины, смежные с вершинами первого уровня, за исключением самих этих вершин, и так далее. Если граф не связен, то универсальное покрытие можно построить для каждой из компонент связности. Каждая вершина графа входит в универсальное покрытие только один раз. Конечно, универсальное покрытие можно построить не единственным образом, даже если зафиксировать корневую вершину. Алгоритм поиска в глубину довольно просто получается из рекурсивного алгоритма префиксного обхода дерева, нужно только учесть, что универсальное покрытие не является бинарным деревом, и запоминать в специальном множестве все обойденные вершины, чтобы предотвратить зацикливание. В приведенной ниже процедуре n - количество вершин в графе, G - матрица смежности, Start - корневая вершина, Used - множество пройденных вершин.

Procedure Pass_To_Depth_Recursive {Рекурсивный обход в глубину}

(n:Byte; Var G:T_Graf_Matrix; Start:Byte; Var Used:T_Set);

Var i : Byte;

Begin

Write(Start,'-');

Used:=Used+[Start];

For i:=1 To n Do

If Not(i In Used)And(G[Start,i]>0) Then Pass_To_Depth_Recursive(n,G,i,Used);

End;

Перед тем как обратиться к процедуре, необходимо присвоить аргументу Used пустое множество. Этот алгоритм легко можно записать в нерекурсивном виде, используя стек отложенных заданий.

Поиск в ширину, или обход графа в ширину, - это обход универсального покрытия графа в последовательности сверху вниз. Сначала обрабатывается корневая вершина, затем все вершины первого уровня, затем все вершины второго уровня и так далее. Алгоритм, основанный на использовании очереди, записывается практически так же, как и алгоритм обхода бинарного дерева. Идентификатор N_max в процедуре - это константа, равная наибольшему возможному количеству вершин в графе.

Procedure Pass_To_Width(n:Byte; G:T_Graf_Matrix; Start:Byte); {Нерекурсивный обход в ширину}

Var

i,t : Byte;

Used : T_Set;

Q : Array[0..N_max-1] Of Byte;

Top,Len: Byte;

Begin

Used:=[];

Len:=1;

Top:=1;

Q[1]:=Start;

While Len>0 Do Begin

t:=Q[Top];

Top:=(Top+1)Mod N_Max; Dec(Len);

If t In Used Then Continue;

Write(t,'-');

Used:=Used+[t];

For i:=1 To n Do

If Not(i In Used)And(G[t,i]>0) Then Begin

Inc(Len);

Q[(Top+Len-1)Mod N_Max]:=i;

End;

End;

End;

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

Procedure Topological_Sorting(n:Byte; G:T_Graf_Matrix);{Топологическая сортировка орграфа, проверяет отсутствие циклов.}

Var

i,j : Byte;

Used : T_Set;

Source,Flag : Boolean;

Begin

Used:=[]; {множество уже отсортированных вершин}

While Used<>[1..n] Do Begin

Flag:=False;{флажок означает : множество отсортированных вершин увеличилось на данном шаге цикла}

For i:=1 To n Do

If Not(i In Used) Then Begin

{вершина i еще не отсортирована}

Source:=True;

{проверяем, является ли эта вершина "источником", то есть проверяем отсутствие еще не отсортированных вершин, из которых в вершину i входят дуги}

For j:=1 To n Do

If (G[j,i]>0)And Not(j In Used) Then Begin

Source:=False;

Break;

End;

If Source Then Begin

{вершина i - "источник", добавляем ее в множество отсортированных вершин}

Flag:=True;

Used:=Used+[i];

Write(i,'>>>');

End;

End;

If Not Flag Then Begin

{множество отсортированных вершин не увеличилось, но есть еще не отсортированные вершины, следовательно, в графе есть циклы}

WriteLn('Есть цикл');

Exit;

End;

End;

End;

Теперь рассмотрим одну из наиболее важных практических задач - поиск кратчайшего пути между двумя заданными вершинами графа. Сначала решим ее уже знакомым нам методом ветвей и границ. Алгоритм метода ветвей и границ легко получается из алгоритма поиска в глубину. В приведенной ниже процедуре Start - это текущая вершина графа (при первом обращении к процедуре она равна начальной вершине пути), Finish - конечная вершина пути, ее значение не изменяется, Len - текущая длина пути, Path - текущий путь (одномерный массив, в котором записываются номера вершин, составляющих путь), Used - множество вершин, входящих в текущий путь, MinLen - длина минимального пути, найденного к данному моменту, и MinPath - текущий минимальный путь.

Procedure Min_Path_in_Graf_Recursive

(n:Byte; Var G:T_Graf_Matrix; Start,Finish:Byte; Len:Byte; Path:T_Path; Used:T_Set; Var MinLen:Byte; Var MinPath:T_Path);

{Поиск кратчайшего пути между двумя заданными вершинами графа. Рекурсивный алгоритм - метод ветвей и границ}

Var i : Byte;

Begin

Inc(Len); {длина текущего пути увеличивается на 1}

If Len>=MinLen Then Exit; {если текущий путь не короче, чем минимальный из уже найденных, то продолжать рекурсию нет необходимости, какой бы путь мы ни нашли, он будет длиннее}

Path[Len]:=Start; {запоминаем очередную вершину пути}

Include(Used,Start);

If Start=Finish Then Begin

{путь достиг конечной вершины, этот путь обязательно минимальный среди всех найденных, иначе мы бы здесь не оказались, запоминаем новый минимальный путь}

MinLen:=Len;

MinPath:=Path;

Exit;

End;

For i:=1 To n Do {продолжаем поиск в глубину}

If Not(i In Used) Then

If G[Start,i]>0 Then

Min_Path_in_Graf_Recursive

(n,G,i,Finish,Len,Path,Used,MinLen,MinPath);

End;

В нерекурсивной записи этого алгоритма используется стек отложенных заданий. Операторы If Len>=MinLen Then Exit; и If Not(i In Used) Then... составляют суть метода ветвей и границ - с их помощью мы отсекаем ненужные ветви универсального покрытия. Слово “ветвей” в названии метода означает обход ветвей дерева решений (здесь - универсального покрытия графа), а слово “границ” означает, что ветви, заведомо не содержащие нужных решений, отсекаются и не обходятся. Метод ветвей и границ - довольно дорогой алгоритм, в худшем случае он имеет сложность n! . Известны алгоритмы меньшей сложности, мы рассмотрим здесь более быстрый волновой алгоритм со сложностью n³. Идея алгоритма заключается в следующем. Пометим конечную вершину пути числом 1. Затем пометим все вершины, смежные с конечной, числом 2. Затем пометим все еще не помеченные вершины, смежные хотя бы с одной вершиной, помеченной двойкой, числом 3. Будем поступать так до тех пор, пока или не окажется помеченной начальная вершина пути, или не выяснится, что не удалось пометить ни одной новой вершины. Во втором случае искомого пути не существует - начальная и конечная вершины не принадлежат одной компоненте связности. Если начальная вершина помечена, то ее метка - длина минимального пути; если в задаче не требуется найти сам путь, а лишь его длину, то алгоритм на этом завершается. Если сам путь (последовательность вершин) нужен, то найдем его так: начальная вершина известна, пусть она помечена числом k, следующая вершина - это любая вершина, помеченная числом k-1 и смежная с начальной, следующая вершина - любая вершина, помеченная числом k-2 и смежная со второй вершиной пути, и так далее. Волновой алгоритм требует выполнения не более n шагов, и на каждом шаге выполняется Сn² операций, следовательно, его сложность n³ даже в худшем случае. Нетрудно заметить, что волновой алгоритм похож на алгоритм поиска в ширину.

Procedure Min_Path_in_Graf_Wave

(n:Byte; G:T_Graf_Matrix; Start,Finish:Byte; Var Len:Byte; Var Path:T_Path);

{Поиск кратчайшего пути между двумя заданными вершинами графа. Волновой алгоритм. }

Var

i,j,Count : Byte;

T : T_Path;

Flag,OK : Boolean;

Begin

FillChar(T,SizeOf(T),0);

Len:=1; {текущее значение метки}

T[Finish]:=Len;

{в массив T записываются метки вершин, 0 означает непомеченную вершину}

If Start=Finish Then Exit;

OK:=False; {OK=True, если путь найден}

Repeat

Flag:=False;

{Flag=True, если на данном шаге удалось пометить хотя бы одну вершину}

For i:=1 To n Do Begin

If T[i]=Len Then Begin

{вершина i помечена на предыдущем шаге, ищем непомеченные вершины, смежные с ней}

For j:=1 To n Do

If (T[j]=0)And(G[j,i]>0) Then Begin

T[j]:=Len+1;

{помечаем новую вершину}

Flag:=True;

If j=Start Then Begin

OK:=True;

{путь найден}

Break;

End;

End;

End;

If OK Then Break;

End;

If OK Then Break;

Inc(Len);

Until Not Flag;

If Not OK Then Begin {путь не найден}

Len:=n+1;

Exit;

End;

Len:=T[Start];

{формируем последовательность вершин, составляющих минимальный путь}

i:=1;

Path[i]:=Start;

Count:=Len;

While Count>1 Do Begin

j:=1;

While (T[j]<>Count-1)Or(G[Path[i],j]=0) Do Inc(j);

Inc(i);

Path[i]:=j;

Dec(Count);

End;

End;

Приведенные алгоритмы ищут кратчайший и в неориентированном, и в ориентированном графе. Если в графе каждому ребру (дуге) приписан некоторый вес - неотрицательное число, то такой граф называют взвешенным графом, или сетью, или системой дорог. Мы будем использовать последний термин. Вершины в системе дорог называют городами, а ребра - дорогами. Для нахождения кратчайшего пути между двумя городами можно использовать метод ветвей и границ почти в том же самом виде, что и в процедуре Min_Path_in_Graf_ Recursive, только длина пути будет определяться не количеством вершин, а суммой длин входящих в него дорог. Такой алгоритм будет по-прежнему иметь сложность n! и, следовательно, будет неэффективным при больших n. Другой способ решения этой задачи предоставляет алгоритм Дейкстры, имеющий сложность n². Этот алгоритм использует дополнительную память, размер которой пропорционален n². В списке городов для каждого города, кроме начального, будем хранить минимальный путь к нему из начального города и длину этого минимального пути. Сначала для всех городов, смежных с начальным, записывается путь, состоящий из одного начального города, и длина, равная длине дороги из начального города. Для городов, не смежных с начальным, записывается пустой путь и бесконечно большая длина пути. На первом шаге находят город, у которого длина пути минимальна, он является ближайшим городом к начальному, пусть это город M. Затем для всех городов K, смежных с M, проверяют, нельзя ли “проехать в город быстрее” через город M. Для этого сравнивают длину пути, записанную для города K, и сумму длины пути, записанной для города M, и длины дороги из M в K. Если путь к K через M короче, то заменяют путь, записанный для K, на путь, записанный для M, плюс сам город M и меняют текущую длину пути. Проделав это для всех городов K, удаляют город M из списка городов, он больше не потребуется. Алгоритм заканчивается, когда ближайшим городом оказывается конечный город или минимальная длина пути оказывается равной бесконечности. В последнем случае пути из начального города в конечный не существует.

Procedure Min_Path_in_Net_Dijkstra

(n:Byte; G:T_Net_Matrix; Start,Finish:Byte; Var Len:Byte; Var Dist:LongInt;

Var Path:T_Path);

{Поиск кратчайшего пути между двумя заданными городами системы дорог. Алгоритм Дейкстры}

Var

NotUsed : T_Set;

TmpLen : T_Path;

TmpDist : Array[1..N_max] Of LongInt;

{массив минимальных расстояний}

TmpPath: Array[1..N_max] Of T_Path; {массив минимальных путей}

j,Jmin : Byte;

Min : LongInt;

Begin

If Start=Finish Then Begin

Len:=1;

Dist:=0;

Path[1]:=Start;

Exit;

End;

NotUsed:=[1..n]-[Start]; {множество городов, остающихся в списке}

For j:=1 To n Do If j<>Start Then {инициализируем список городов}

If G[Start,j]>0 Then Begin

TmpLen[j]:=1;

TmpDist[j]:=G[Start,j];

TmpPath[j][1]:=Start;

End

Else

TmpDist[j]:=High(LongInt);

Repeat

Min:=High(LongInt);{ищем минимальную длину пути}

Jmin:=0;

For j:=1 To n Do

If j In NotUsed Then

If TmpDist[j]<Min Then Begin

Min:=TmpDist[j];

Jmin:=j;

End;

If Jmin=0 Then Begin {пути не существует}

Dist:=High(LongInt);

Exit;

End;

If Jmin=Finish Then Begin {конечный город - ближайший}

Len:=TmpLen[Jmin]+1;

Dist:=TmpDist[Jmin];

Path:=TmpPath[Jmin];

Path[Len]:=Jmin;

Exit;

End;

NotUsed:=NotUsed-[Jmin];

{удаляем ближайший город из списка}

For j:=1 To n Do {изменяем содержимое списка городов}

If (j In NotUsed) And (G[Jmin,j]>0) And

(TmpDist[j]>Min+G[Jmin,j])Then Begin

TmpDist[j]:=Min+G[Jmin,j];

TmpLen[j]:=TmpLen[Jmin]+1;

TmpPath[j]:=TmpPath[Jmin];

TmpPath[j,TmpLen[j]]:=Jmin;

End;

Until False;

End;

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

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