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

Листинг 5.42. Алгоритм построения минимального остовного дерева 
int L = 1; vert[0] := 0; edge[0] := 1; 
while (! ((L = 1) && (edge[0] = n + 1))) 
if (edge[L-1]==num[vert[L-1]]+1) 
{
// 
путь кончается, поэтому все вершины,
// 
следующие за vert[L], 
// 
напечатаны - можно печатать vert[L-1]
Console.WriteLine(vert[L-1]); 
edge[--L]++; 
} 
else
{ 
// edge[L-1] <= num[vert[L-1]],
// 
путь кончается в вершине
lastvert = dest[vert[L-1]][edge[L-1]];
// 
последняя
if (lastvert == 
напечатана) edge[L-1]++; 
12 / 23

---

197 
else
{ 
vert[++L] = lastvert; edge[L-1] = 1; 
} 
} 
// 
путь сразу же ведет в пустоту, поэтому все вер-
шины 
// 
левее, т. е. 1...n, напечатаны 
Докажем, что если в графе нет циклов, то алгоритм заканчивает работу. 
Предположим, что это не так. Каждая вершина может печататься только один 
раз, поэтому с некоторого момента вершины не печатаются. В графе без цик-
лов длина пути ограничена (одна и та же вершина не может входить дважды), 
поэтому, подождав еще, мы можем прийти к тому, что путь перестанет удли-
няться. После этого может разве что увеличиваться edge[L], но и это не бес-
предельно. 
5.8.3. П
ОСТРОЕНИЕ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА
 
Алгоритм предназначен для нахождения минимального остовного де-
рева, т. е. такого подграфа, который бы имел столько же компонент связно-
сти, сколько и исходный, но не содержал бы петель и сумма весов всех его 
ребер была бы минимальной. 
Вначале опишем алгоритм (возможно недостаточно строго), а затем об-
судим, какой способ задания графа был бы наилучшим в данном случае, а 
также покажем, как от тех способов задания, которые мы использовали ра-
нее, перейти к способу, применимому здесь. 
Алгоритм Краскала выглядит так. 
1.
Отсортировать ребра графа по возрастанию весов. 
2.
Полагаем, что каждая вершина относится к своей компоненте 
связности. 
3.
Пройти ребра в «отсортированном» порядке. Для каждого 
ребра выполнить следующие действия: 
• если вершины, соединяемые данным ребром, лежат в разных 
компонентах связности, то объединить эти компоненты в од-
ну, а рассматриваемое ребро добавить к минимальному ос-
товному дереву; 
• если вершины, соединяемые данным ребром, лежат в одной 
компоненте связности, то исключить ребро из рассмотрения. 
13 / 23

---

198 
4. 
Если есть еще нерассмотренные ребра и не все компоненты 
связности объединены в одну, то перейти к шагу 3, иначе 
выйти из алгоритма. 
В данном случае работать с матрицей весов неудобно, это выявляется 
уже на этапе упорядочивания ребер по весу, поэтому создадим временный 
массив ребер Edges[] с соответствующими весами. Каждый элемент этого 
массива имеет три поля: начальная вершина, конечная вершина и вес: 
struct TEdges
// 
временная структура для ребра 
{ 
public int n1; // 
№ первой вершины 
public int n2; // 
№ второй вершины 
public int A; // 
вес ребра 
} 
Упорядочиваем ребра по неубыванию весов пузырьковой сортировкой. 
Далее в алгоритме вводится массив int[] Link, элементы которого характе-
ризуют номер компоненты связности соответствующих вершин (две верши-
ны u1, u2 лежат в одной компоненте связности, если и только если 
Link
[u1] = Link[u2]). 
В алгоритме (листинг 5.43) используется переменная q, которая ини-
циализируется значением N-1, и затем при объединении двух компонент 
связности на шаге 3 q уменьшается на единицу, таким образом, условие q = 0 
будет означать, что все вершины лежат в одной компоненте связности и ра-
бота алгоритма завершена. Найденное дерево будет определено с помощью 
стека, в который мы помещаем номера ребер.