9.5.3. Алгоритм Краскала

Следующий жадный алгоритм, известный как алгоритм Краскала, находит крат­чайший остов в связном графе.

Алгоритм 9.7. Алгоритм Краскала

Вход: список Е ребер графа G с длинами.

Выход: множество Т ребер кратчайшего остова.

Т: = 

упорядочить Е в порядке возрастания длин

k : = 1 { номер рассматриваемого ребра }

for i from I to p — 1 do

while добавление ребра E(k) образует цикл в Т do

k: = k + 1 { пропустить это ребро }

end while

Т: = Т  {E[k]} { добавить это ребро в SST }

end for

обоснование

Заметим, что множество подмножеств множества ребер, не содержащих циклов, образует матроид (см. раздел 2.7). Действительно, если множество ребер не со­держит цикла, то любое подмножество также не содержит цикла. Пусть теперь Е'  Е — произвольное множество ребер, a G' — правильный подграф графа G, определяемый этими ребрами. Очевидно, что любое максимальное не содержа­щее циклов подмножество множества Е' является объединением остовов ком­понент связности G' и по теореме об основных свойствах деревьев (см. подраз­дел 9.1.2) содержит p(G') - k(G') элементов. Таким образом, по теореме подраз­дела 2.7.2 множество ациклических подмножеств ребер образует матроид. Далее, рассматриваемый алгоритм, как жадный алгоритм, находит кратчайшее ацикли­ческое подмножество множества ребер. По построению оно содержит р — 1 эле­мент, а значит, является искомым остовом. 

ОТСТУПЛЕНИЕ

Задача о нахождении кратчайшего остова принадлежит к числу немногих задач теории графов, которые можно считать полностью решенными. Между тем, если изменить усло­вия задачи, на первый взгляд даже незначительно, то она оказывается значительно более трудной. Рассмотрим следующую задачу. Пусть задано множество городов на плоскости и нужно определить минимальный (по сумме расстояний) набор железнодорожных линий, который позволил бы переехать из любого города в любой другой. Кратчайший остов пол­ного графа расстояний между городами не будет являться решением этой (практически, очевидно, очень важной) задачи, известной как задача Штейнера. На рис. 9.15 приведены, соответственно, диаграммы кратчайшего остова, наивного «решения» задачи Штейнера и правильного решения для случая, когда города расположены в вершинах квадрата.

Комментарии

Материал этой главы затрагивает вопросы, которые очень часто возникают в практическом программировании. Поэтому различные сведения о деревьях мож­но найти не только в специальных учебниках по теории графов, но и в книгах по программированию и конструированию эффективных алгоритмов. В качестве рекомендуемых источников назовем [1, 8, 13]. В частности, алгоритмы операций с деревом сортировки описаны в [8], откуда они заимствованы с некоторыми дополнительными уточнениями способов реализации. В книге [13] можно найти краткие и доступные описания алгоритмов работы с АВЛ-деревьями, которые здесь опущены за недостатком места.

Упражнения

1. Нарисовать диаграммы всех деревьев с 7 вершинами.

2. Допустим, что в ордереве все узлы, кроме листьев, имеют одну и ту же по­ лустепень исхода n. В этом случае говорят, что дерево имеет постоянную ширину ветвления n. Оценить высоту h ордерева, которое имеет р узлов и постоянную ширину ветвления n.

3. Составить алгоритм преобразования обратной польской записи арифмети­ческого выражения в прямую польскую запись.

4. Какой вид будет иметь дерево сортировки после того, как в него последо­вательно добавили следующие текстовые элементы: «1», «2», «3», «4», «5»,«6», «7», «8», «9», «10», «И», «12», «13», «14», «15», «16», «17», «18», «19»?

5. Доказать, что полный граф К_р имеет р^(p-2) остовов (это утверждение из­ вестно как формула Кэли).