4. Реализация основных операций над ориентированным графом

Вычисление адреса узла графапо значению его информационной части фактически представляет собой поиск этого узла в списке узлов:

functiontOrGraph.NodeAddr(v:tValue):pNode;// адрес узла со значением v

var

Node: pNode;

begin

if fHead=nil

then NodeAddr:=nil

else begin

Node:= fHead;

while (Node^.NextNode<>nil) and (Node^.Value<>v) do Node:=Node^.NextNode;

if Node^.Value=v then NodeAddr:= Node else NodeAddr:= nil;

end;

end;// function tOrGraph.NodeAddr

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

functiontOrGraph.ArcAddr(Node1,Node2: pNode): pArc;

// Проверка смежности узлов Node1 и Node2

var

Arc :pArc;

begin

ArcAddr:= nil; Arc:=Node1^.ArcList;

if Arc<>nil then begin // поиск узла Node2 в списке дуг узла Node1

while (Arc^.NextArc<>nil) and (Arc^.RearNode<>Node2) do Arc:= Arc^.NextArc;

if Arc^.RearNode=Node2 then ArcAddr:= Arc;

end;

end;// function tOrGraph.ArcAddr

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

functiontOrGraph.HeadNode(ArcNode: pArc): pNode;

// Начальный узел дуги

var

Node:pNode;

Arc :pArc;

begin

Node:= fHead; HeadNode:=nil;

while Node<>nil do begin

Arc:=Node^.ArcList;

if Arc<>nil then begin

while (Arc^.NextArc<>nil) and (Arc<>ArcNode) do Arc:= Arc^.NextArc;

if Arc=ArcNode then begin HeadNode:=Node; Break; end;

end;

Node:= Node^.NextNode;

end;

end;// function tOrGraph.HeadNode

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

proceduretOrGraph.AddArc(Node1,Node2:pNode);

// Включение дуги между узлами Node1 и Node2

var

Arc:pArc;

begin

Arc:=ArcAddr(Node1,Node2);

if Arc=nil

then begin

Arc:=New(pArc); Arc^.NextArc:=Node1^.ArcList;

Arc^.RearNode:=Node2; Node1^.ArcList:=Arc; Inc(fArcsNumber); end

else Writeln('Узлы ',Node1^.Value,' и ',Node2^.Value,' уже соединены дугой');

end;// procedure tOrGraph.AddArc

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

proceduretOrGraph.DeleteArc(Node1,Node2:pNode);

// Исключение дуги между узлами Node1 и Node2, если она есть

var

Arc,PrevArc:pArc;

begin

Arc:=Node1^.ArcList;// адрес начала списка смежности узла Node1

ifArc<>nil

then begin// если список дуг узла Node1 не пуст

PrevArc:=nil;// адрес дуги, предшествующей исключаемой

while (Arc^.RearNode<>Node2) and (Arc^.NextArc<>nil) do begin

PrevArc:=Arc; Arc:= Arc^.NextArc;

end;

if Arc^.RearNode=Node2 // если есть дуга, входящая в узел Node2

then begin // удаление

if PrevArc=nil

then Node1^.ArcList:= Arc^.NextArc // удаляется первая дуга

else PrevArc^.NextArc:= Arc^.NextArc; // удаляется не первая дуга

Dispose(Arc); Dec(fArcsNumber);

end

else WriteLn('Исключаемая дуга отсутствует');

end

elseWriteLn('Исключаемая дуга отсутствует');

end;// procedure tOrGraph.DeleteArc

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

proceduretOrGraph.AddNode(v: tValue);

// Включение узла со значением v в граф

var

NewNode:pNode;

begin

if NodeAddr(v)=nil

then begin

NewNode:=New(pNode); NewNode^.Value:=v;

NewNode^.NextNode:=fHead; NewNode^.ArcList:=nil;

fHead:=NewNode; Inc(fNodesNumber); end

else Writeln('Узел со значением ',v,' в графе уже есть');

end;// procedure tOrGraph.AddNode

При исключении узла из графанеобходимо исключить и все дуги, инцидентные этому узлу. Реализация графа с помощью линейных односвязных списков не позволяет иметь прямой доступ к дугам, входящим в узел, и для их поиска нужно просматривать все списки дуг графа. Операция выполняется в три этапа: сначала удаляются все дуги, выходящие из исключаемого узла, затем отыскиваются и удаляются все дуги, входящие в исключаемый узел, и только после этого исключается сам узел. Исключаемый узел должен присутствовать в списке узлов графа.

functiontOrGraph.DeleteNode(DisNode:pNode):tValue;

// Исключение узла DisNode из графа с исключением инцидентных ему дуг

// и возвращение информации, содержащейся в исключенном узле

var

Node,PrevNode:pNode;// текущий и предшествующий узлы

Arc,PrevArc:pArc;// текущая и предшествующая дуги

begin

// 1. Удаление дуг, исходящих из узла DisNode

while DisNode^.ArcList<>nil do begin

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

Dispose(Arc); Dec(fArcsNumber);

end;

// 2. Поиск и удаление дуг, входящих в узел DisNode

Node:=fHead;

while Node<>nil do begin

Arc:=Node^.ArcList; PrevArc:=nil;

if Arc<>nil then begin // если список дуг узла Node не пуст

while (Arc^.RearNode<>DisNode) and (Arc^.NextArc<>nil) do begin

PrevArc:=Arc; Arc:= Arc^.NextArc;

end;

ifArc^.RearNode=DisNode

then begin // удаление

if PrevArc=nil

then Node^.ArcList:= Arc^.NextArc // удаляется первая дуга

else PrevArc^.NextArc:= Arc^.NextArc; // удаляется не первая дуга

Dispose(Arc); Dec(fArcsNumber);

end;

end;

Node:=Node^.NextNode;

end;

// 3. Исключение узла DisNode из списка узлов графа

DeleteNode:=DisNode^.Value; PrevNode:=nil; Node:=fHead;

while DisNode<>Node do begin

PrevNode:=Node; Node:= Node^.NextNode;

end;

if PrevNode=nil

then fHead:=DisNode^.NextNode // Node – первый узел

else PrevNode^.NextNode:=DisNode^.NextNode; // Node – не первый узел

Dispose(Node); Dec(fNodesNumber);

end; // function tOrGraph.DeleteNode

При выполнении операции просмотра графав файл поочередно выводятся узлы графа и для каждого узла перечисляются исходящие из него дуги:

procedure tOrGraph.Revision(var f:Text); // просмотр графа

var

Node :pNode;

Arc :pArc;

begin

Node:= fHead;

while Node<>nil do begin

Write(f,'Узел ',NodeValue(Node),':');

Arc:=Node^.ArcList;

while Arc<>nil do begin

Write(f,'<',Node^.Value,',',Arc^.RearNode^.Value,'> '); Arc:= Arc^.NextArc;

end;

Node:= Node^.NextNode; Writeln(f);

end;

end;// procedure tOrGraph.Revision

Для реализации метода построения графанеобходимо выбрать способ задания информации о графе. Приведенная ниже процедураBuildпостроена в предположении, что во входном файле хранится множество узлов и дуг графа в формате:

Узел 1 (значение типа tValue)

Узел 2 (значение типа tValue)

... ...

& (разделитель – символ с кодом 33)

Дуга 1 (2 значения типа tValue)

Дуга 2 (2 значения типа tValue)

... ...

Сначала из входного файла поочередно читаются и включаются в граф узлы. Каждый узел включается только в том случае, если ранее он не был включен в граф. После чтения разделителя цикл формирования списка узлов графа завершается и начинается чтение и включение в граф дуг. Каждая дуга представлена во входном файле парой значений типа tValue– значениями начального и конечного узла дуги. Дуга включается в граф только в том случае, если оба узла есть в графе.

procedure tOrGraph.Build(var f:Text); // построение графа

var

Value1,Value2:tValue;

Node1,Node2 :pNode;

begin

whilenotEof(f)dobegin// формирование списка узлов графа

Readln(f,Value1);// чтение значения узла

if Value1='&' then Break; // разделитель - узлы исчерпаны

if NodeAddr(Value1)=nil then AddNode(Value1);

end;

while not Eof(f) do begin // формирование списков дуг узлов

Readln(f,Value1,Value2); // чтение начального и конечного узлов

Node1:=NodeAddr(Value1);// адрес узла со значением Value1

Node2:=NodeAddr(Value2);// адрес узла со значением Value2

if Node1=nil

then Writeln('Узла ',Value1,' в графе нет')

else if Node2=nil

then Writeln('Узла ',Value2,' в графе нет')

else AddArc(Node1,Node2);

end;

end;// procedure tOrGraph.Build

При реализации операции очистки графапоочередно просматриваются узлы графа в списке узлов. Сначала для каждого узла очищается список инцидентных ему дуг путем исключения очередной дуги из начала списка до тех пор, пока список дуг не опустеет. Затем указательfHeadпередвигается на следующий за удаляемым элемент списка узлов, и удаляется сам этот узел.

proceduretOrGraph.Clear;// удаление всех узлов и дуг из графа

var

Node:pNode;

Arc :pArc;

begin

while fHead<>nil do begin

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