ОБХОД ОРИЕНТИРОВАННОГО ГРАФА
При решении многих задач, связанных с графами, необходим эффективный способ систематического обхода всех узлов и дуг графа.
Известны два способа обхода графов: обход в глубину и обход в ширину (в теории графов они называются поиском в глубину и поиском в ширину).
Способ обхода в глубину DFS (от depth-first search — поиск в глубину) составляет основу многих других эффективных алгоритмов работы с графами и состоит в следующем.
Обход начинается с некоторого начального узла v графа G. Для каждого узла, смежного с узлом v и не посещавшегося ранее, рекурсивно применяется поиск в глубину. Когда все узлы, которые можно достичь из узла v, посещены, поиск заканчивается. Этот способ называется поиском в глубину, поскольку поиск непосещенных узлов идет в направлении вперед (вглубь) до тех пор, пока это возможно.
Для решения этой задачи необходимо переопределить тип tNode, включив в него дополнительное поле Visited логического типа — признак посещения узла. Начальное значение этого поля для всех узлов равно False.
Приведенный ниже метод tOrGraph.DFS для обхода графа в глубину содержит внутреннюю рекурсивную процедуру DFSR, выполняющую обход в глубину от заданного узла Node.
Посещение узла в данном методе заключается в выводе значения его содержательного поля Value в файл f.
procedure tOrGraph.DFS(StartNode: pNode; var f: Text);
// Обход в глубину, начиная с узла с адресом StartNode,
// с выводом значений узлов в файл f
procedure DFSR(Node:pNode);
// Внутренняя рекурсивная процедура обхода в глубину от узла Node
var
Arc:pArc; //дуга графа
NextNode:pNode; //узел, следующий за узлом Node
begin
NodeA.Visited:=True; //отметка узла как посещенного
Write(f,NodeA. Value,' > '); //посещение узла - вывод его значения
Arc:=NodeA.Arcl_ist; //первая дуга из списка дуг, инцидентных Node
while Arc<>Nil do begin //поиск всех узлов, смежных с Node NextNode:=ArcA.RearNode; //узел, смежный с узлом Node if not NextNodeA.Visited
then DFSR(NextNode); //узел не посещен - поиск от него Arc:=ArcA.NextArc; //переход к следующему узлу, смежному с Node
end;
end; //procedure DFSR
var
Node:pNode;
begin
Node:=fHead;
while Node<>nil do begin
// отметка всех узлов графа как непосещенных NodeA.Visited:=False;
Node:=NodeA.NextNode;
end;
DFSR(StartNode);
Writeln(f);
end; //procedure tOrGraph.DFS
Способ обхода в ширину BFS (от breadth-first search — поиск в ширину) получил свое название из-за того, что при достижении во время обхода любого узла v далее рассматриваются все узлы, смежные с узлом V. После того как посещены и отмечены все не посещенные ранее узлы, смежные с узлом у, выбирается один из этих узлов и обход в ширину начинается от него, затем процесс повторяется для оставшихся смежных с v узлов.
Для реализации этого алгоритма необходимо запоминать посещенные смежные с V узлы и, рассматривая их в порядке посещения, начинать процесс посещения всех узлов, смежных с ними. Для этой цели хорошо подходит такая структура данных как очередь (действительно, посещенные узлы становятся в очередь для продолжения процесса поиска от них).
procedure tOrGraph.BFS(StartNode: pNode; var f:Text);
// Обход в ширину, начиная с узла с адресом StartNode,
// с выводом значений узлов в файл f
var
Arc: pArc; // дуга графа
Node, NextNode:pNode; //очередной и следующий за ним узлы q:tQueue; // очередь с элементами типа pNode
begin
Node:=fHead;
while Nodeonil do begin
// отметка узлов графа как непосещенных NodeA.Visited:=False;
Node:=NodeA.NextNode;
end;
q:= tQueue.Create; //создание экземпляра очереди
StartNodeA.Visited:=True; //отметка начального узла - посещен Write(f,StartNodeA.Value,' > '); //посещение начального узла
q.lnsert(StartNode); //включение элемента StartNode в очередь while not q.Empty do begin //пока очередь не пуста Node:=q.Remove; // исключение первого элемента из очереди Arc:=NodeA.ArcList; //первая дуга из списка дуг, инцидентных Node while Arc<>nil do begin //поиск всех узлов, смежных с Node NextNode:=ArcA.RearNode; //узел, смежный с узлом Node if not NextNodeA.Visited // если смежный узел не посещен, then begin
NextNodeA.Visited:=True; //то отметка его как посещенного,
Write(f,NextNodeA.Value,' > '); //посещение узла q.lnsert(NextNode); //и включение его в очередь
end;
Arc:=ArcA.NextArc; //переход к следующему смежному с Node узлу
end;
end;
Writeln(f);
q.Free; //удаление очереди
end; //procedure BFS
Для графа G7, приведенного на рис. 4.3, обход в глубину дает последовательность узлов А, В, С, D, Е, F, обход в ширину — А, В, D, С, Е, F.
Если некоторые узлы графа при поиске от начального узла остались непосещенными, то выбирается один из них и поиск повторяется. Этот процесс продолжается до тех пор, пока обходом не будут охвачены все узлы графа.
