While fHead^.ArcList<>nil do begin

Arc: =fHead^.ArcList; fHead^.ArcList: = Arc^.NextArc;

Dispose(Arc);

end;

Node: = fHead; fHead: = Node^.NextNode;

Dispose(Node);

end;

fArcsNumber: = 0; fNodesNumber: = 0;

end; //procedure tOrGraph.Clear

5. Обход ориентированного графа

При решении многих задач, связанных с графами, необходим эффективный способ систематического обхода всех узлов и дуг графа. Известны два способа обхода графов: обход в ширину и обход в глубину (в теории графов они называются поиском в глубину и поиском в ширину).

Способ обхода в глубину 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

Node^.Visited: =True; // отметка узла как посещенного

Write(f, Node^.Value, ' > '); // посещение узла - вывод его значения в файл f

Arc: =Node^.ArcList; // первая дуга из списка дуг, инцидентных узлу Node

while Arc< > Nil do begin // поиск всех узлов, смежных с Node

NextNode: =Arc^.RearNode; // узел, смежный с узлом Node

if not NextNode^.Visited

then DFSR(NextNode); // узел не посещен - поиск от него

Arc: =Arc^.NextArc; // переход к следующему узлу, смежному с Node

end;

end; //procedure DFSR

Var

Node: pNode;

Begin

Node: =fHead;

while Node< > nil do begin // отметка всех узлов графа как непосещенных

Node^.Visited: =False; Node: =Node^.NextNode;

end;

DFSR(StartNode); Writeln(f);

end; // procedure tOrGraph.DFS

Способ обхода в ширину BFS (от breadth-first search – поиск в ширину) получил свое название из-за того, что при достижении во время обхода любого узла v далее рассматриваются все узлы, смежные с узлом 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 Node< > nil do begin // отметка всех узлов графа как непосещенных

Node^.Visited: =False; Node: =Node^.NextNode;

end;

q: = tQueue.Create; // создание экземпляра очереди

StartNode^.Visited: =True; // отметка начального узла как посещенного

Write(f, StartNode^.Value, ' > '); // посещение начального узла

q.Insert(StartNode); // включение элемента StartNode в конец очереди

while not q.Empty do begin // пока очередь не пуста

Node: =q.Remove; // исключение первого элемента из очереди

Arc: =Node^.ArcList; // первая дуга из списка дуг, инцидентных узлу Node

while Arc< > nil do begin // поиск всех узлов, смежных с Node

NextNode: =Arc^.RearNode; // узел, смежный с узлом Node

if not NextNode^.Visited // если смежный узел не посещен,