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

5.3.3. О
СТОВ ГРАФА
 
В любом связном неориентированном графе можно исключить часть 
ребер, превратив его в стягивающее дерево — остов (рис. 5.9). Достаточно 
легко доказать, что дерево с N вершинами имеет (N 
− 1) ребро. Мы будем 
строить стягивающее дерево с помощью слегка измененного алгоритма по-
иска в глубину. 
Рис. 5.9. Стягивающее дерево графа 
4 / 23

---

166 
В этом алгоритме нам потребуется какая-нибудь начальная вершина, но 
искать какую-нибудь вершину не надо. Поэтому вместо функции, используе-
мой при поиске в глубину, напишем рекурсивную функцию FindDepth 
(листинг 5.28). 
Листинг 5.28. Функция построения стягивающего дерева 
void FindDepth(int n) 
{ 
VisitTrue(n); // 
отметить посещенный 
int LL = 0; 
if (Nodes[n].Edge != null) 
{ 
LL = Nodes[n].Edge.Length; int i = -1; 
while (i < LL - 1) 
{ 
int m = Nodes[n].Edge[++i].numNode; 
if (!Nodes[m].visit) 
{ 
SetEdgeBlack(n, i); // 
закрасить ребро 
FindDepth(m); 
} 
} 
} 
} 
public void SetTreeDepth(int n) 
// 
построение стягивающего дерева (остов) –
// 
поиск в глубину 
{ 
ClearVisit(); 
FindDepth(n); 
} 
5 / 23

---

167 
5.4. К
РАТЧАЙШИЕ ПУТИ
 
Задачи о кратчайших путях относятся к фундаментальным задачам 
комбинаторной оптимизации. 
Пусть дан взвешенный неориентированный граф, и необходимо опре-
делить наилучший путь от узла s до узла t. Такая задача выглядит достаточно 
простой, но наилучший путь могут определять многие факторы, например: 
− расстояние в километрах; 
− время прохождения маршрута с учетом ограничений скорости; 
− ожидаемая продолжительность поездки с учетом дорожных усло-
вий и плотности движения; 
− задержки, вызванные проездом через города или объездом горо-
дов; 
− число городов, которое необходимо посетить, например, в целях 
доставки грузов. 
Известно, что все веса неотрицательны. Нужно найти наименьшую ми-
нимальную сумму весов s → i для всех i = 1. . . n за время O(N
2
). На самом 
деле это ограничение можно ослабить требованием отсутствия циклов с от-
рицательным суммарным весом. В противном случае двигаясь от вершины s 
к вершине t и обходя такой цикл несколько раз, мы можем получить сколь 
угодно малую сумму весов. 
Сформулируем две задачи о кратчайших путях. 
1.
Определить кратчайшие пути от вершины s до всех осталь-
ных вершин x
i
. 
2.
Найти кратчайшие пути между всеми парами вершин. 
При реализации алгоритмов предполагается, что матрица смежности, 
вообще говоря, не удовлетворяет условию треугольника A
ij
 <= A
ik
 + A
kj
и ес-
ли между вершинами i и j отсутствует дуга, то вес дуги равен 
∞ (при реали-
зации – максимальное целое).