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

РЕАЛИЗАЦИЯ ОСНОВНЫХ ОПЕРАЦИЙ НАД ОРИЕНТИРОВАННЫМ ГРАФОМ

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

function tOrGraph.NodeAddr(v: tValue): pNode;

// Возвращение адреса узла со значением v

var

Node: pNode;

begin

if fHead=nil then NodeAddr:=nil

else begin // поиск узла со значением v в списке узлов Node:= fHead;

while (NodeA.NextNode<>nil) and (NodeA.Value<>v) do Node:=NodeA.NextNode; if NodeA.Value=v then NodeAddr:= Node else NodeAddr:= nil; end;

end; //function tOrGraph.NodeAddr

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

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

function tOrGraph.ArcAddr(Node1 ,Node2: pNode): pArc;

//Возвращение адреса дуги, соединяющей узлы Nodel и Node2

var

Arc :pArc;

begin

ArcAddr:= nil;

Arc:=Node1 A.ArcList;

if Arc<>nil then begin //поиск узла Node2 в списке дуг узла Nodel while (ArcA.NextArc<>nil) and (ArcA.RearNode<>Node2) do Arc:= ArcA.NextArc; if ArcA.RearNode=Node2 then ArcAddr:= Arc; end;

end; //function tOrGraph.ArcAddr

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

function tOrGraph.HeadNode(ArcNode: pArc): pNode;

//Возвращение адреса начального узла дуги с адресом ArcNode

var

Node:pNode;

Arc :pArc;

begin

Node:=fHead; HeadNode:=nil;

while Node<>nil do begin Arc:=NodeA.ArcList; if Arc<>nil then begin

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

then begin

HeadNode:=Node; Break;

end;

end;

Node:= NodeA.NextNode;

end;

end; //function tOrGraph.HeadNode

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

procedure tOrGraph.AddArc(Node1 ,Node2:pNode);

// Включение дуги между узлами с адресами Node 1 и Node2

var

Arc:pArc;

begin

Arc:=ArcAddr(Node1 ,Node2); if Arc=nil then begin

Arc:=New(pArc);

ArcA.NextArc:=Node1 A.ArcList;

ArcA.RearNode:=Node2;

Nodel A.ArcList:=Arc;

Inc(fArcsNumber);

end

end; //procedure tOrGraph.AddArc

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

procedure tOrGraph.DeleteArc(Node1 ,Node2:pNode);

//Исключение дуги между узлами с адресами Nodel и Node2

var

Arc, PrevArc:pArc;

begin

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

if Arc<>nil

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

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

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

end;

if ArcA.RearNode=Node2 //если есть дуга, входящая в узел Node2 then begin //то удаление

if PrevArc=nil

then Nodel A.ArcList:= ArcA.NextArc //удаляется первая дуга else PrevArcA.NextArc:= ArcA.NextArc; //удаляется не первая дуга Dispose(Arc); Dec(fArcsNumber);

end;

end;

end; //procedure tOrGraph.DeleteArc

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

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

procedure tOrGraph.AddNode(v: tValue);

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

var

NewNode:pNode;

begin

if NodeAddr(v)=nil

then begin

NewNode:=New(pNode);

NewNodeA.Value:=v;

NewNodeA.NextNode:=fHead;

NewNodeA.ArcList:=nil;

fHead:=NewNode;

Inc(fNodesNumber);

end;

end; //procedure tOrGraph.AddNode

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

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

function tOrGraph.DeleteNode(DisNode:pNode): tValue;

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

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

var

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

begin

// 7. Удаление дуг, исходящих из узла DisNode while DisNodeA.ArcList<>nil do begin

Arc:=DisNodeA.ArcList;

DisNodeA.ArcList:= ArcA.NextArc;

Dispose(Arc);

Dec(fArcsNumber);

end;

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

while Node<>nil do begin

Arc:=NodeA.Arcl_ist;

PrevArc:=nil;

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

while (ArcA.RearNode<>DisNode) and (ArcA.NextArc<>nil) do begin PrevArc:=Arc;

Arc:= ArcA.NextArc;

end;

if ArcA.RearNode=DisNode

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

if PrevArc=nil

then NodeA.ArcList:= ArcA.NextArc //удаляется первая дуга else PrevArcA.NextArc:= ArcA.NextArc; // не первая дуга Dispose(Arc); Dec(fArcsNumber);

end;

end;

Node:=NodeA.NextNode;

end;

// 3. Исключение узла DisNode из списка узлов графа DeleteNode:=DisNodeA.Value;

PrevNode:=nil;

Node:=fHead;

while DisNode<>Node do begin PrevNode:=Node;

Node:= NodeA.NextNode;

end;

if PrevNode=nil

then fHead:=DisNodeA.NextNode //Node - первый узел

else PrevNodeA.NextNode:=DisNodeA.NextNode;//He первый узел Dispose(Node);

Dec(fNodesNumber); end; //function tOrGraph.DeleteNode

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

procedure tOrGraph.Revision(var f:Text);

// Просмотр графа - вывод в файл f узлов и исходящих из них дуг

var

Node :pNode;

Arc :pArc;

begin

Node:= fHead;

while Node<>nil do begin

Write(f,'y3en ',NodeValue(Node),':');

Arc:=NodeA.ArcList;

while Arc<>nil do begin

Write(f,,<',NodeA.Value,',,,ArcA.RearNodeA.Value,'> ');

Arc:= ArcA.NextArc;

end;

Node:= NodeA.NextNode;

Writeln(f);

end;

end; //procedure tOrGraph.Revision

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

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

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

• • • 9 9 9

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

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

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

9 9 9 9 9 9

На рис. 4.5 приведен ориентированный граф с символьными значениями узлов и множества узлов и дуг этого графа в формате, необходимом для его построения.

Способ задания информации о графе

Рис. 4.5. Способ задания информации о графе

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

procedure tOrGraph.Build(var f:Text);

// Построение графа по данным файла f

var

Valuel ,Value2:tValue;

Node1,Node2 :pNode;

begin

while not SeekEof(f) do begin //формирование списка узлов графа Readln(f,Valuel); // чтение значения узла

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

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

end;

while not SeekEof(f) do begin //формирование списков дуг узлов Readln(f,Valuel ,Value2); // чтение начального и конечного узлов

Nodel :=NodeAddr(Value1); //адрес узла со значением Valuel Node2:=NodeAddr(Value2); //адрес узла со значением Value2 if (Nodel <>nil) and (Node2<>nil) then AddArc(Node1 ,Node2);

end;

end; //procedure tOrGraph.Build

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

procedure tOrGraph.Clear;

// Удаление всех узлов и дуг из графа

var

Node:pNode;

Arc :pArc;

begin

while fHead<>nil do begin while fHeadA.ArcList<>nil do begin Arc:=fHeadA.Arcl_ist; fHeadA.ArcList:= ArcA.NextArc;

Dispose(Arc);

end;

Node:= fHead; fHead:= NodeA.NextNode;

Dispose(Node);

end;

fArcsNumber := 0;

fNodesNumber := 0;

end; //procedure tOrGraph.Clear

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

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