Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

ОБХОД ОРИЕНТИРОВАННОГО ГРАФА

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

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

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

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

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы