Управление узлами и связями

 

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

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

Обход сети

 

Обход сети подобен обходу дерева. Для этого можно использовать обход либо в глубину, либо в ширину.

Обход в ширину обычно похож на прямой обход деревьев, хотя для сети можно также определить также обратный и симметричный обход.

 

Как известно, алгоритм прямого обхода двоичного дерева формулируется следующим образом:

 

1. Обратиться к узлу.

2. Выполнить рекурсивный прямой обход левого поддерева.

3. Выполнить рекурсивный прямой обход правого поддерева.

 

В дереве между связанными узлами существует отношение "родительский-дочерний". Поскольку алгоритм начинает с корня и всегда движется вниз через дочерние узлы, он никогда не обратится к узлу дважды.

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

 

Таким образом, алгоритм прямого обхода сети выполняется в следующем порядке:

 

1. Пометить узел.

2. Посетить узел.

3. Выполнить рекурсивный обход непомеченных соседних узлов.

 

Для хранения информации о посещенных узлах можно добавить логическую переменную Visited к записи TNode:

 

TNode=record

ID:integer; // Идентификатор узла

LinkSentinel:TLink; // Звенья, исходящие из данного узла

NextNode:PNode; // Следующий узел в списке узлов

Visited:boolean; // Был ли узел уже посещен при обходе

end;

 

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

 

procedure Traverse(node: PNode);

var

link: PLink;

neighbor: PNode;

begin

// Помечаем узел как посещенный.

Node^.Visited:= True;

// Посещение непомеченных соседних узлов.

link:= node^.LinkSentinel.NextLink;

while (link<>nil) do

begin

// Какой узел является соседним для данного.

if (link^.Node1 = node) then neighbor:= link^.Node2

else neighbor:= link^.Nodel;

// Посещаем соседний узел, если он еще не помечен

if (not neighbor^.Visited) then Traverse(neighbor);

// Исследуем следующее ребро

Link:=link^.NextLink;

end;

end;

 

Поскольку эта процедура не обращается дважды ни к одному узлу, набор обходимых связей не содержит циклов и образует дерево. В связанной сети дерево будет обходить каждый узел. Поскольку дерево охватывает каждый узел сети, оно названо остовным деревом, или каркасом. На рис. 34 показана небольшая сеть. Каркас ее дерева с корнем в узле А изображен жирными линиями.

 

 

 

Рис. 34. Каркас дерева

 

Методику пометки узлов можно также использовать для того, чтобы преобразовать алгоритм обхода дерева в ширину в сетевой алгоритм. Алгоритм обхода дерева начинает работу, помещая корневой узел дерева в очередь. Затем первый узел из очереди удаляется, происходит обращение к узлу, и его дочерние узлы помещаются в конце очереди. Этот процесс повторяется до тех пор, пока очередь не опустеет.

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

 

Ниже приводится алгоритм обхода сети в ширину:

1. Пометить первый узел (это будет корень остовного дерева) и добавить его в конец очереди.

2. Повторять следующие шаги, пока очередь не опустеет:

- удалить первый узел из очереди и обратится к нему;

- пометить каждый из непомеченных соседних узлов и добавить его в конец очереди.

Наименьший каркас дерева

 

Если задана сеть со стоимостями ребер, то минимальным, или наименьшим каркасом дерева именуется каркас, общая стоимость всех ребер в котором минимальна. Вы можете использовать минимальный каркас, чтобы выбрать самый дешевый способ соединения всех узлов сети.

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

 

Рис. 35. Телефонные линии, соединяющие шесть городов

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

Кратчайший путь

Алгоритмы поиска кратчайшего пути, рассматриваемые в данном разделе, находят все кратчайшие пути от одной точки сети до любой другой при условии что сеть связана. Набор связей, используемых всеми кратчайшими путями, образует дерево кратчайших путей.

На рис. 36 изображена сеть, в которой дерево кратчайших путей с корнем в узле А выделено жирными линиями. Оно показывает кратчайшие пути от узла А до любого другого узла сети. Например, кратчайший путь от узла А к узлу F проходит через узлы А, С, Е, F

 

Рис. 36. Дерево кратчайших путей

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

Алгоритм расстановки меток всегда выбирает ребро, которое гарантированно является частью конечного дерева кратчайших путей. Он работает аналогично алгоритму построения минимального остовного дерева. Если ребро было добавлено к дереву, оно уже не будет удалено.

Алгоритм коррекции меток добавляет ребра, которые могут быть, а могут и не быть частью конечного дерева кратчайших путей. В процессе выполнения алгоритм может определить, что вместо уже имеющегося ребра в дерево должно быть добавлено другое. В этом случае алгоритм заменяет старое ребро новым и продолжает работу. Замена ребра в дереве может открыть дополнительные пути. Чтобы проверить их, алгоритму приходится повторно исследовать пути, которые были добавлены к дереву раньше и использовали удаленное ребро.

Алгоритмы расстановки и коррекции меток используют аналогичные классы для представления узлов и связей. Класс узла TNode содержит поле Dist, которое указывает расстояние от корня до узла в растущем дереве кратчайшего пути. В алгоритме расстановки меток для Dist задается True, как только узел добавлен к дереву и этот параметр уже не будет изменяться. В алгоритме коррекции меток параметр Dist может быть исправлен позже, когда ребро будет заменено другим.

Класс TNode также содержит поле Status, которое определяет, есть ли в настоящее время данный узел в дереве или списке возможных связей. В поле InLink указывается ребро, ведущее к узлу в растущем дереве кратчайшего пути.

 

type

TStatus=(nsNotInList, nsWasInList, nsNowInList);

 

TNode=record

ID:integer; // Идентификатор узла

LinkSentinel:TLink; // Звенья, исходящие из данного узла

NextNode:PNode; // Следующий узел в списке узлов

Status:TStatus; // Есть ли узел в дереве

Dist:integer; // Расстояние от корня

InLink:PLink; // Ребро, ведущее в данный узел

end;

 

Класс TLink включает поле InTree, которое указывает, является ли ребро частью дерева кратчайшего пути.

 

type

TLink=record

Node1: PNode; // Узел на одном конце дуги

Node2: PNode; // Узел на другом конце

Cost:integer; // Стоимость

NextLink:PLink; // Следующее звено в списке звеньев

InTree:boolean; // Есть ли ребро в дереве

end;

 

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

 

Расстановка меток

 

Алгоритм расстановки меток начинает с присвоения полям Status всех узлов значения nsNotInList и полями Dist значения INFINITY, которое должно быть больше суммы стоимостей по всем дугам графа. Затем он присваивает полю Dist корневого узла значение 0 и помещает корневой узел в список возможных связей. Полю Status корня присваивается значение nsNowInList - это указывает, что корень в настоящее время находится в списке возможных связей.

Затем алгоритм выполняет поиск узла с минимальным значением Dist. Сначала будет найден корневой узел, так как он единственный в списке.

Алгоритм удаляет выбранный узел из списка и устанавливает для него значение поля Status в значение nsWasInList, поскольку теперь он является постоянной частью дерева кратчайшего пути. Поля Dist и InLink узла уже имеют правильные значения. Для каждого корневого узла значение поля InLink равно nil, а значение поля Dist- нулю.

После этого алгоритм исследует каждую связь, исходящую из выбранного узла. Если соседний узел на другом конце ребра не был в списке возможных связей, то алгоритм добавляет его к списку. Он устанавливает значение поля Status соседнего узла равным nsNowInList, а значение поля Dist - расстоянию от корневого узла до выбранного узла плюс стоимость ребра. И наконец, он присваивает полю соседнего узла InLink значение, которое указывает на связь с соседним узлом.

Если во время проверки алгоритмом связей, исходящих из выбранного узла, значение поля соседнего узла Status равно nsNowInList, то он уже занесен в список возможных. Алгоритм исследует текущее значение поля Dist соседнего узла, определяя, будет ли новый путь через выбранный узел короче. Если это так, он обновляет поля InLink и Dist соседнего узла и оставляет его в списке возможных связей. Алгоритм повторяет весь описанный процесс, удаляя узлы из списка возможных связей, исследуя соседние с ними узлы и добавляя их в список, пока он не опустеет.

На рис. 37 показана часть дерева кратчайшего пути. В этой точке алгоритм уже проверил узлы А и В, удалил их из списка возможных и исследовал их связи. Узлы А и В уже добавлены к дереву кратчайшего пути, и список возможных связей теперь содержит узлы С, D и Е. Жирные стрелки на рисунке указывают значение InLink в этой точке. Например, значение поля InLink для узла Е соответствует связи между узлами Е и В.

 

Рис. 37. Часть дерева кратчайшего пути

Важно, чтобы алгоритм обновлял значения полей InLink и Dist только для узлов со значением Status = nsNowInList. Для большинства сетей нельзя получить более короткий путь, добавляя узлы, не имеющиеся в списке возможных. Однако если сеть содержит цикл с отрицательной общей длиной, алгоритм обнаружит, что можно уменьшить расстояние до некоторых узлов, которые уже находятся в дереве. Он соединит две ветви дерева таким образом, чтобы оно перестало быть деревом. На рис. 38 показана сеть с отрицательной стоимостью цикла и «дерево» кратчайшего пути, которое получится, если алгоритм модифицирует стоимость уже имеющихся в дереве узлов.

 

 

 

Рис. 38. Решение задачи для сети с циклом отрицательной стоимости