G 3 G 4 G 5 G 6
Граф называется полным, если любые два его различных узла соединены дугой. Например, графы G 3 и G 5 полные.
Дополнением графа называется граф с тем же множеством узлов, что и исходный граф, причем два различны узла в дополнении графа смежны тогда и только тогда, когда они не смежны в исходном графе.
С каждой дугой графа может быть связано некоторое значение, как в графе G 2. Такой граф называется взвешенным графом, а связанное с каждой дугой значение называется весом.
Путь от узла a до узла b – это последовательность узлов n 0, n 1,..., n k, такая, что n 0= a, nk = b и для любого i от 0 до k -1 узел ni +1 смежен узлу ni, т.е. существует дуга из ni в ni +1. Длина пути n 0, n 1,..., n k равна количеству его дуг, то есть k. Например, в графе G 7 путь A, B, C, D имеет длину 3 и соединяет узлы A и D.
Граф G 7
Длина пути во взвешенном графе равна сумме весов дуг, входящих в этот путь.
Путь, не содержащий одинаковых узлов (за исключением, может быть, n 0= n k), называется простым.
Путь от узла к самому себе, не содержащий одинаковых дуг, называется циклом. Если граф содержит цикл, то он называется циклическим, в противном случае – ациклическим.
Расстояние между двумя узлами – это длина кратчайшего пути, соединяющего эти узлы.
Граф называется связным, если для любой пары узлов существует соединяющий их путь. Например, граф G 3 связный, а графы G 4 – G 6 – нет. Очевидно, что ориентированный граф не будет связным, если в нем есть узлы, не имеющие входящих или исходящих дуг. Неориентированный граф несвязный, если он содержит узлы, не имеющие инцидентных с ним дуг.
Связный ориентированный граф без петель называется сетью.
2. Операции над графом
Над графом g могут быть выполнены следующие операции:
|
|
– возвращение адреса узла со значением v – NodeAddr (g, v);
– проверка смежности узлов Node1 и Node 2 – ArcAddr (g, Node1, Node2);
– возвращение начального узла дуги Arc – HeadNode (g, Arc);
– возвращение конечного узла дуги Arc – RearNode (g, Arc);
– возвращение информации, содержащейся в узле, – Value (g, Node);
– проверка наличия узлов в графе – Empty (g);
– включение дуги между узлами Node1 и Node2 – AddArc (g, Node1, Node2);
– исключение дуги между узлами Node1 и Node2 – DeleteArc (g, Node1, Node2);
– включение узла со значением v в граф – AddNode (g, v);
– исключение из графа узла Node с исключением инцидентных ему дуг и возвращение значения информационного поля узла – DeleteNode (g, Node);
– определение количества узлов в графе – NodesQuantity (g);
– просмотр графа – Revision (g);
– создание пустого графа – Create (g);
– удаление всех узлов и дуг графа – Clear (g);
– построение графа – Build (g).
С использованием вышеперечисленных операций можно реализовать более сложные операции: определение расстояния (кратчайшего пути) между двумя заданными узлами графа; поиск узлов в графе; определение путей между двумя заданными узлами графа и их длин и др.
Графы применяют для решения задач планирования и распределения работ проекта, транспортных задач, задач о потоках в сетях и других.
3. Реализация графа
Одним из способов представления графа является матричный способ. При представлении графа с помощью матрицы инцидентности строки матрицы соответствуют узлам графа, а столбцы – дугам; на пересечении каждой строки и столбца ставится 1, если дуга инцидентна узлу, и 0 в противном случае.
Граф представляют также с помощью матрицы смежности узлов. И строки и столбцы матрицы при этом соответствуют узлам графа, а на пересечении каждой строки и столбца ставится 1, если соответствующие узлы смежные, и 0 в противном случае.
|
|
Несмотря на очевидные преимущества (простота включения и исключения дуг, простота реализации большинства основных алгоритмов обработки графа), матричное представление графа не всегда удобно, поскольку число узлов (и дуг для матрицы инцидентности) требуется знать заранее. Если граф должен создаваться или изменяться во время выполнения программы, то для каждого добавления или удаления узла надо строить новую матрицу. Кроме того, память должна быть отведена для всех возможных дуг.
Очевидным решением является представление графа, при котором все узлы графа и инцидентные им дуги объединены в связанные списки. Конкретные реализации списковых структур могут быть различными: односвязные и двусвязные, линейные и циклические списки.
Списковое представление является одним из наиболее удобных и универсальных способов представления графа и позволяет представлять любые графы: ориентированные и неориентированные, взвешенные и невзвешенные, хранить информацию, связанную с дугами и узлами графа.
Рассмотрим один из способов связанного представления графа. Узлы графа объединяются в список, каждый элемент которого содержит три поля: Value (информация, связанная с узлом графа), NextNode (указатель на следующий элемент списка узлов графа) и ArcList (указатель на список дуг, выходящих из данного узла, – список смежности). Каждый элемент списка смежности представляет дугу графа и содержит два поля: RearNode (указатель на элемент в списке узлов графа, которым заканчивается дуга) и NextArc (указатель на следующий элемент списка смежности данного узла). Для взвешенного графа элемент списка дуг должен содержать дополнительное поле Weight (вес дуги). Для неориентированного графа список дуг для каждого узла должен содержать все дуги, инцидентные этому узлу (входящие и выходящие), при этом каждая дуга будет присутствовать в представлении графа дважды, так как инцидентна двум узлам.
|
|
Пример ориентированного невзвешенного графа и его представление с помощью линейных односвязных списков:
Переменная ссылочного типа Head указывает на начало списка узлов графа. Каждый узел Node графа состоит из трех полей: Value, ArcList и NextNode. Дуга Arc содержит два поля: NextArc и RearNode. Последний узел графа и последняя дуга из списка дуг каждого узла содержат указатель nil. Поле ArcList узла содержит значение nil в том случае, если этот узел не имеет исходящих из него дуг.
Описание класса tOrGraph (Oriented Graph – ориентированный граф) с использованием линейных односвязных списков имеет вид:
Type
tValue = Char; // тип информационной части узла графа – Char
pArc = ^tArc; // тип указателя на дугу графа
pNode = ^tNode; // тип указателя на узел графа
tNode = record // тип узла графа
Value: tValue; // информационная часть узла графа
NextNode: pNode; // указатель на следующий узел графа
ArcList: pArc; // указатель на список смежности узла
end; // tNode
tArc = record // тип элемента списка смежности узла - дуги графа
RearNode: pNode; // указатель на узел, являющийся концом дуги
NextArc: pArc; // указатель на следующую дугу узла графа
end; // tArc
tOrGraph= class // класс – ориентированный граф
Protected
fHead: pNode; // поле - указатель на начало списка узлов
fNodesNumber: Word; // поле - количество узлов графа
fArcsNumber: Word; // поле - количество дуг графа
Public
property Head: pNode read fHead write fHead;
property NodesNumber: Word read fNodesNumber write fNodesNumber;
property ArcsNumber: Word read fArcsNumber write fArcsNumber;
function NodeValue(Node: pNode):tValue; // значение узла Node
function NodeAddr(v: tValue): pNode; // адрес узла графа со значением v
function ArcAddr(Node1,Node2: pNode):pArc; // смежность узлов
function HeadNode(ArcNode: pArc): pNode; // начальный узел дуги
function RearNode(ArcNode: pArc): pNode; // конечный узел дуги
function Empty: Boolean; // наличие узлов в графе
procedure AddArc(Node1,Node2: pNode); // включение дуги
procedure DeleteArc(Node1,Node2: pNode); // исключение дуги
procedure AddNode(v: tValue); // включение узла
function DeleteNode(DisNode:pNode): tValue; // исключение узла
procedure Build(var f:Text); // построение графа
procedure Revision(var f:Text); // просмотр графа
procedure Clear; // удаление всех узлов графа
constructor Create; // конструктор графа
destructor Destroy; // деструктор графа
end; // tOrGraph
4. Реализация основных операций над ориентированным графом
Вычисление адреса узла графа по значению его информационной части фактически представляет собой поиск этого узла в списке узлов:
function tOrGraph.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 в противном случае. Перед использованием операции необходимо убедиться, что оба узла присутствуют в списке узлов графа.
function tOrGraph.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
Операция определения начального узла дуги возвращает адрес узла, из которого выходит заданная дуга (дуга задается своим адресом). Перед применением операции необходимо убедиться, что дуга присутствует в одном из списков дуг графа.
function tOrGraph.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
При реализации операции включения дуги между двумя заданными узлами графа дуга помещается в начало списка дуг узла, из которого она выходит (такое включение выполняется наиболее просто для линейного односвязного списка). При этом дуги в представлении графа хранятся в порядке, обратном их включению. Перед применением операции необходимо убедиться, что оба узла присутствуют в списке узлов графа.
procedure tOrGraph.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
Исключение дуги между двумя заданными узлами, если она есть. Оба узла должны присутствовать в списке узлов графа.
procedure tOrGraph.DeleteArc(Node1,Node2:pNode);
// Исключение дуги между узлами Node1 и Node2, если она есть
Var
Arc, PrevArc:pArc;
Begin
Arc:=Node1^.ArcList; // адрес начала списка смежности узла Node1
if Arc<> 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
else WriteLn('Исключаемая дуга отсутствует');
end; // procedure tOrGraph.DeleteArc
При реализации операции включения узла в граф новый узел помещается в начало списка узлов графа, так как такое включение выполняется наиболее просто для линейного односвязного списка. Необходимо помнить, что при этом узлы в представлении графа хранятся в порядке, обратном их включению (как в стеке), поэтому операция обхода графа будет выводить узлы графа в том же обратном порядке. Узел включается в граф только в том случае, если он отсутствует в графе.
procedure tOrGraph.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
При исключении узла из графа необходимо исключить и все дуги, инцидентные этому узлу. Реализация графа с помощью линейных односвязных списков не позволяет иметь прямой доступ к дугам, входящим в узел, и для их поиска нужно просматривать все списки дуг графа. Операция выполняется в три этапа: сначала удаляются все дуги, выходящие из исключаемого узла, затем отыскиваются и удаляются все дуги, входящие в исключаемый узел, и только после этого исключается сам узел. Исключаемый узел должен присутствовать в списке узлов графа.
function tOrGraph.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;
if Arc^.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
while not Eof(f) do begin // формирование списка узлов графа
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 передвигается на следующий за удаляемым элемент списка узлов, и удаляется сам этот узел.
procedure tOrGraph.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
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 // если смежный узел не посещен,
Then begin
NextNode^.Visited:=True; // то отметка его как посещенного,
Write(f,NextNode^.Value,' > '); // посещение узла
q.Insert(NextNode); // и включение его в конец очереди
end;
Arc:=Arc^.NextArc; // переход к следующему смежному с Node узлу
end;
end;
Writeln(f); q.Free; // удаление очереди
end; // procedure BFS
Для графа
обход в глубину дает последовательность узлов A, B, C, D, E, F, обход в ширину – A, B, D, C, E, F.
Если некоторые узлы графа при поиске от начального узла остались непосещенными, то выбирается один из них и поиск повторяется. Этот процесс продолжается до тех пор, пока обходом не будут охвачены все узлы графа.
6. Вычисление расстояния между узлами ориентированного графа
Напомним, что расстоянием между двумя узлами n1 и n2 называется длина кратчайшего пути между этими узлами. Очевидно, что представляет интерес не только значение расстояния между двумя узлами, но и перечень узлов, входящих в кратчайший путь. Для решения этой задачи необходимо переопределить тип tNode, включив в него дополнительные поля: Dist – расстояние до данного узла от некоторого другого узла, PrevNode – указатель на узел, предшествующий текущему в кратчайшем пути. Начальное значение поля Dist для всех узлов равно нулю. Определяем расстояния от узла n1 до всех остальных узлов графа, для чего последовательно обходим граф от узла n1 по спискам смежности и в поле Dist узла, являющегося концом очередной дуги, записываем значение, равное сумме уже вычисленного расстояния до начального узла дуги плюс 1. Изменять значение поля Dist конечного узла дуги надо только в том случае, если оно меньше того значения, которое в этом поле хранится (расстояние – длина кратчайшего пути до узла). При каждом изменении значения поля Dist необходимо переопределять значение поля PrevNode, записывая в него указатель на тот узел, длина пути от которого до текущего узла оказалась меньшей.
Дополнительно необходимо хранить сведения об уже пройденных узлах (можно использовать поле Visited логического типа), чтобы не посещать их повторно. Начальное значение этого поля для всех узлов равно False. В основе алгоритма вычисления кратчайшего пути между узлами n1 и n2 лежит рекурсивный обход графа в глубину.
Метод tOrGraph.SPath возвращает строку с перечнем информационных полей узлов графа (типа tValue=Char), входящих в кратчайший путь между узлами Node1 и Node2. Длина кратчайшего пути (расстояние) равна длине этой строки, уменьшенной на 1.
function tOrGraph.SPath(Node1,Node2:pNode):String;
// Кратчайший путь между узлами Node1 и Node2
procedure PathFromNode(Node:pNode);
// Внутренняя рекурсивная процедура
// вычисления расстояния от узла Node до всех узлов графа
Var
Arc:pArc; // дуга графа
NextNode:pNode; // узел графа, следующий за Node
Begin
Node^.Visited:=True; // отметка о посещении узла Node
Arc:=Node^.ArcList; // указатель на список смежности узла Node
while Arc<> nil do begin // пока не исчерпан список смежности узла Node
NextNode:=Arc^.RearNode; // узел, смежный с узлом Node
if not NextNode^.Visited
then begin // если узел NextNode еще не посещался,
NextNode^.Dist:=Node^.Dist+1; // то расстояние до него равно 1,
PathFromNode(NextNode); // продолжаем обход от него
NextNode^.PrevNode:=Node; // предыдущий узел для NextNode - Node
End
else // если узел NextNode уже посещался и,
if Node^.Dist+1<NextNode^.Dist // длина пути к нему через узел Node меньше
Then begin
NextNode^.Dist:=Node^.Dist+1; // то изменяем длину пути на меньшую и
NextNode^.PrevNode:=Node; // запоминаем узел, через который пришли
end;
Arc:=Arc^.NextArc; // переход к следующей дуге списка смежности
end;
end; // procedure PathFromNode
Var
Node:pNode; // текущий узел графа
S: string; // строка – перечень узлов кратчайшего пути
Begin
Node:=fHead;
// установка начальных значений всех узлов графа
while Node<> nil do begin
Node^.Visited:=False; Node^.Dist:=0;
Node:=Node^.NextNode;
end;
// вычисление расстояний от узла Node1 до всех остальных
PathFromNode(Node1);
Node:=Node2; s:=NodeValue(Node2); // включение Node2 в начало строки
while Node<>Node1 do begin
// для всех узлов в кратч. пути от Node2 до Node1
Node:=Node^.PrevNode; // переход к узлу, предшествующему Node2
Insert(NodeValue(Node),S,1); // включение предш. узла в начало строки
end;
SPath:=S;
end; // function tOrGraph.SPath
Если значение, хранящееся в узле графа, имеет тип, отличный от Char, то можно хранить кратчайший путь в виде списка.
Лабораторная работа 4.
Ориентированные графы
Задание
Опишите класс – ориентированный граф, необходимый для решения задачи, указанной в вашем варианте задания, и реализуйте его методы. Составьте программу решения задачи, указанной в вашем варианте задания. В программе необходимо продемонстрировать работу основных методов работы с графом: построение, вывод, просмотр (т.е. программа должна иллюстрировать работу с графом как в примере выполнения задания).
Исходный граф может содержать петли и циклы.
Если требуется реализовать граф с помощью циклического или двусвязного списка, то в число обязательных операций должны быть включены: построение, обход, очистка графа и операции, необходимые для их реализации. Специальные для каждого задания операции указаны в скобках.
Варианты заданий
1. Определить кратчайший путь между узлами n 1 и n 2 и его длину во взвешенном графе.
2. Определить, является ли один граф подграфом другого.
3. Задана карта дорог в виде графа. Найти города, расположенные на расстоянии более X от заданного узла.
4. Реализовать граф с помощью односвязных циклических списков (включение и исключение узла).
5. Найти все узлы графа, к которым можно добраться из заданного узла.
6. Определить кратчайший путь между узлами n 1 и n 2 и его длину во взвешенном графе.
7. Определить, является ли ориентированный граф несвязным.
8. Составить список узлов, расстояние от которых до заданного узла не превышает величину X.
9. Определить, является ли один граф суграфом другого.
10. Реализовать граф с помощью односвязных циклических списков (определение начального и конечного узлов каждой дуги).
11. Найти все узлы графа, из которых можно добраться до заданного узла.
12. Определить расстояние между узлами n 1 и n 2 во взвешенном циклическом графе.
13. Определить, является ли один граф частью другого.
14. На основе обхода в ширину найти все узлы заданного графа, недостижимые из заданного узла.
15. На основе поиска в ширину определить, является ли граф несвязным.
16. Перечислить узлы графа по возрастанию расстояния до них от заданного узла.
17. Реализовать граф с помощью двусвязных списков (включение и исключение узла).
18. Задана карта дорог в виде графа. Найти города, расположенные на расстоянии X от заданного узла.
19. На основе обхода в ширину найти узел с заданным значением в графе и исключить его.
20. Найти узел графа, ближайший к заданному злу.
21. На основе поиска в ширину определить, является ли граф связным.
22. Реализовать граф с помощью односвязных циклических списков (включение и исключение дуги, определение количества узлов).
23. Найти все циклы в графе.
24. Определить, является ли один граф дополнением другого.
25. Задана карта дорог в виде графа. Найти города, расположенные на расстоянии не более X от заданного узла.
26. На основе обхода в глубину найти все узлы заданного графа, недостижимые из заданного узла.
27. Определить, является ли граф полным.
28. Найти все узлы графа, к которым можно добраться из заданного узла по пути не длиннее заданного значения.
29. Определить длины всех путей между узлами n 1 и n 2 в невзвешенном графе.
30. Найти узел графа, наиболее удаленный от заданного узла.