Iv. Динамические структуры данных

Весовая матрица графа с N вершинами – это матрица размером N на N, где каждый элемент с 
индексами (i,j) равен «весу» ребра из вершины i в вершину j. 
a) 
б) 
A
B
C
D
E
10
5
12
7
8
9
A B C D E 
A
B
C
D
E
10
5
12
7
8
9
A B C D E 
A 0 5 10 12 0 
A 0 5 10 12 0 
B 5 0 0 7 9 
B 0 0 0 7 0 
C 10 0 0 8 0 
C 0 0 0 0 0 
D 12 7 8 0 0 
D 0 0 8 0 0 
E 0 9 0 0 0 
E 0 9 0 0 0 
 
Задача Прима-Краскала 
 Формулировка задачи 
Задача. Дана плоская страна и в ней n городов с известными координатами. Нужно соединить 
все города телефонной сетью так, чтобы длина телефонных линий была минимальная.
Город будем изображать узлом (точкой). Телефонные линии могут разветвляться только на те-
лефонных станциях, а не в чистом поле. Поскольку требуется линия минимальной общей дли-
ны, в ней не будет циклов, потому что иначе можно было бы убрать одно звено цикла и станции 
по-прежнему были бы связаны. В терминах теории графов эта задача звучит так: 
Дан граф с n вершинами; длины ребер заданы матрицей {d
ij
}, i,j=1..n. Найти набор ре-
бер, соединяющий все вершины графа (он называется остовным деревом) и имеющий мини-
мальную длину
Эта задача – одна из тех немногих, для которых известно точное и несложное решение, причем 
алгоритм предельно прост. 
 Жадные алгоритмы 
Представим себе зимовщика, которому предоставили некоторый запас продуктов на всю 
зиму. Конечно, он может сначала съесть все самое вкусное – шоколад, мясо и т.п., но за такой 
подход придется жестоко расплачиваться в конце зимовки, когда останется только соль и мар-
гарин. 
Подобным образом, если оптимальное решение строится по шагам, обычно нельзя выби-
рать на каждом этапе «самое вкусное» – за это придется расплачиваться на последних шагах. 
Такие алгоритмы называют жадными. 

---

IV. Динамические структуры данных
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
34