Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 5.41. Топологическая сортировка 
void SetVisit(int i) 
{ 
if (!Nodes[i].visit) 
{ 
if (Nodes[i].Edge != null) 
for (int j=0;j<=Nodes[i].Edge.Length-
1;j++) 
{ 
SetEdgeBlack(i, j); // 
закрасить ребро 
SetVisit(Nodes[i].Edge[j].numNode); 
} 
Lib.myStack.Push(i); 
VisitTrue(i); // 
отметить песеще-
ние 
} 
} 
Основная программа вызывает процедуру SetVisit() для всех N узлов: 
public void TopSort() 
{ 
int N = Nodes.Length; 
ClearVisit(); 
Lib.myStack = new MyStack(); 
for (int i = 0; i <= N - 1; i++) 
SetVisit(i); 
} 
9 / 23

---

194 
Чтобы доказать конечность последовательности рекурсивных вызовов 
для какой-либо вершины, рассмотрим максимальную длину пути по дугам, 
выходящим из этой вершины. Будем называть эту длину глубиной вершины. 
Условие отсутствия циклов гарантирует, что эта величина конечна. Очевид-
но, что из вершины нулевой глубины дуг не выходит. Глубина конца верши-
ны у конца дуги, по крайней мере, на единицу меньше, чем глубина вершины 
у ее начала. При работе процедуры SetVisit(i) все рекурсивные вызовы 
SetVisit
(j) относятся к вершинам меньшей глубины. 
На рисунке 5.24 представлены результаты работы. 
Рис. 5.24. Топологическая сортировка 
5.8.2. М
ИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО 
 
Остовным деревом связного неориентированного графа называется его 
ациклический, т.е. не содержащий циклов, подграф, в который входят все его 
вершины. Остовное дерево может быть получено удалением из графа избы-
точных ребер с сохранением его связности. Если ребра графа снабжены ве-
сами, то можно ставить задачу построения минимального остовного дерева, 
то есть остовного дерева с минимально возможной суммой весов ребер.
В качестве практического примера решения этой задачи можно про-
блему прокладки линий коммуникаций между заданным числом объектов 
при следующих дополнительных условиях: 
10 / 23

---

195 
− известны «расстояния» между каждой парой объектов (это может 
быть геометрическое расстояние или стоимость прокладки ком-
муникаций между ними); 
− объекты могут быть связаны как непосредственно, так и с участи-
ем произвольного количества промежуточных объектов; 
− разветвления линий могут иметь место только в местах располо-
жения объектов. 
В такой постановке задача сводится к нахождению минимального ос-
товного дерева во взвешенном графе, вершины которого соответствуют за-
данным объектам, а веса ребер равны «расстояниям» между ними. Возмож-
ность введения дополнительных объектов и, следовательно, дополнительных 
точек ветвления, позволяет минимизировать сумму «расстояний» между уз-
лами коммуникационной сети. Если к тому же дополнительные объекты мо-
гут выбираться только из некоторого имеющегося множества, то получаем 
задачу построения минимального остовного дерева, кратчайшее дерево, по-
крывающего заданное подмножество вершин взвешенного графа. Задача в 
такой постановке известна как задача Штейнера, она является чрезвычайно 
сложной с вычислительной точки зрения и практически может быть решена 
лишь при небольшом числе дополнительных вершин. Существует, однако, 
достаточно эффективный приближенный алгоритм, строящий остовное дере-
во графа, длина которого превышает длину минимального дерева не более 
чем в два раза. 
Задача поиска минимального остовного дерева для всего графа, в отли-
чие от задачи Штейнера, допускает эффективное решение. Далее будут рас-
смотрены два алгоритма решения этой задачи. 
1.
Упорядочить ребра графа по возрастанию весов. 
2.
Выбрать ребро с минимальным весом, не образующее цикл с 
выбранными ранее ребрами. Занести выбранное ребро в спи-
сок ребер строящегося остова. 
3.
Проверить, все ли вершины графа вошли в построенный ос-
тов. Если нет, то выполнить шаг 2. 
Данный алгоритм имеет скорость роста O(M), где M — число ребер. 
Предположим, что ориентированный граф без циклов имеет узлы Node[i] с 
номерами 1...N. Для каждого узла i известен динамический массив edge[j] 
выходящих из него ребер, каждый элемент которого указывает на номер уз-
ла, в который ведет одно из этих ребер. Напечатать все вершины в таком по-
рядке, чтобы конец любого ребра был напечатан перед его началом. 
Добавим к графу вершину 0, из которой ребра ведут в вершины 1, ... , N. 
Если ее удастся напечатать с соблюдением правил, то тем самым все верши-
ны будут напечатаны. 
Алгоритм хранит путь, выходящий из нулевой вершины и идущий по 
ребрам графа. Переменная L отводится для длины этого пути. Путь образован 
11 / 23

---

196 
вершинами vert[1], . . . , vert[L] и ребрами, имеющими номера edge[1], 
. . . , edge[L]. Номер edge[s] относится к нумерации ребер, выходящих из 
вершины vert[s]. Тем самым для всех s должны выполняться неравенство: 
edge[s] <= num[vert[s]] 
и равенство: 
vert[s+1] = dest [vert[s]] [edge[s]] 
Впрочем, для последнего ребра сделаем исключение, разрешив ему 
указывать «в пустоту», т. е. edge[L-1] может равняться num[vert[L-1]] + 1. 
В процессе работы алгоритм будет печатать номера вершин, соблюдая 
при этом требование: вершина печатается только после тех вершин, в кото-
рые из нее ведут ребра. Наконец, будет выполняться такое требование: вер-
шины пути, кроме последней (т. е. vert[0]..vert[L-1]) не напечатаны, но 
свернув с пути налево, мы немедленно упираемся в напечатанную вершину.