Первая страница / Теория / Графы. Покрывающие деревья /

Минимальные остовные деревья

Голосование: 67, 6

Введение

В статье рассматривается задача о построении минимального остовного дерева (minimum-spanning-tree problem). В начале статьи дано общее описание проблемы и история подходов к ее решению. Далее описан базовый алгоритм и некоторые теоретические сведения о минимальных остовных деревьях. В конце статьи представлены основные алгоритмы (Крускал, Прим, Борувка).

Постановка задачи

Итак, имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна?

В общем случае, задачу можно сформулировать так. Пусть дан связный, неориентированный граф с весами на ребрах G(VE), в котором V — множество вершин (контактов), а E — множество их возможных попарных соединений (ребер). Пусть для каждого ребра (u,v) однозначно определено некоторое вещественное число w(u,v) — его вес (длина или стоимость соединения). w() называется весовой функцией. Задача состоит в нахождении такого связного ациклического подграфа T ⊂ G, содержащего все вершины, что суммарный вес его ребер будет минимален.

Так как T связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом (spanning tree). Остовное дерево T, у которого суммарный вес его ребер w(T) = ∑(u,v)∈T w(u,v) минимален, называется минимальным остовным или минимальным покрывающим деревом (minimum spanning tree).

Рис. 1
Рис. 1. Минимальное остовное дерево. Суммарный вес дерева равен 37. Это минимальное остовное дерево не уникально: удалением ребра (c,d) и добавлением ребра (a,b) получается новое минимальное остовное дерево.

Так как рассматриваются только деревья, можно считать все ребра положительными (достаточно добавить к весу всех ребер некоторую относительно большую положительную константу). В противном случае, если стоимость соединения между двумя вершинами равна отрицательному числу, можно несколько раз параллельно соединить их для уменьшения суммарного веса остовного подграфа.

Рис.2-а. Минимальное остовное дерево.
Суммарный вес равен 3.
Рис.2-б. Минимальный покрывающий подграф.
Суммарный вес равен 0.

Также считаем, что для любой пары ребер их весовые характеристики будут различны. Это гарантирует уникальность построенного минимального остовного дерева. Для примера, если все ребра имеют единичный вес, то любое остовное дерево будет минимальным (с суммарным весом v-1, где v – количество вершин в графе).

Рис.3. Все возможные минимальные остовные деревья для данного графа.

В данном случае, любой алгоритм построит одно из минимальных остовных деревьев. Один из вариантов разрешения неопределенности заключается в модификации алгоритма сравнения ребер по весу, например, так:

SHORTER-EDGE(i;j;k;l)
1: if w(i,j) < w(k,l) then return (i,j)
2: if w(i,j) > w(k,l) then return (k,l)
3: if min(i,j) < min(k,l) then return (i,j)
4: if min(i,j) > min(k,l) then return (k,l)
5: if max(i,j) < max(k,l) then return (i,j)
6: return (k,l)

Области применения

  • Разработка сетей. Ранее был приведен пример о соединении n городов в единую телефонную сеть с минимальной суммарной стоимостью соединений.
  • Производство печатных плат. По аналогии с сетью: мы хотим соединить n контактов проводами с минимальной суммарной стоимостью. (Здесь стоит отметить, что задача о минимальном остовном дереве является упрощением реальности. В самом деле, если соединяемые контакты находятся в вершинах единичного квадрата, разрешается соединять любые его вершины, и вес соединения равен его длине, то минимальное покрывающее дерево будет состоять из трех сторон квадрата. Между тем все его четыре вершины можно электрически соединить двумя пересекающимися диагоналями, суммарная длина которых будет равна 2√2, что меньше 3 в первом случае).
  • Минимальное остовное дерево может использоваться для визуализации многоаспектных, многомерных данных, например, для отображения их взаимосвязи (на картинке ниже продемонстрировано дерево схожести различных животных видов по размеру костей).

Рис.4. Минимальное остовное дерево может нагляднее представить эволюцию животных видов.
С помощью него можно разбивать животных на группы и классы.
  • Наука, и в частности биология, используют многомерные данные для группировки объектов, растений, животных. Минимальное остовное дерево позволяет разбивать их на взаимосвязанные классы, четко отслеживая близкие по строению и характеристикам группы.

Историческая справка

У задачи построения минимального остовного дерева длинная и богатая история. Грэхем и Хелл в своей статье «История задачи построения минимального остовного дерева» [2] начинают отсчет истории проблемы с работы Чекановского (Czekanowski) 1909 года. Первый и, наверное, простейший алгоритм восходит к Борувке (Boruvka), который в 1926 году, намного раньше, чем появились первые компьютеры, и даже раньше, чем была создана конструктивная теория графов, представил свое решение данной задачи. Немного позднее, в 1938 году Шоке (Choquet), а затем Флорек (Florek), Лукасевич (Lukaziewicz), Перкал (Perkal), Штейнгауз (Stienhaus) и Зубжицкий (Zubrzycki) в 1951 году и Соллин (Sollin) в начале шестидесятых снова переоткрывают алгоритм.

Другой известный алгоритм построения минимального остовного дерева восходит к Войтеху Ярнику (Vojtech Jarnik) [1930]. Он больше известен под именем алгоритма Прима (Robert Prim). Р.Прим независимо от Ярника придумал его в 1956 и представил более подробное и детальное описание, чем первооткрыватель. Еще раз этот алгоритм открыл Эдсгер Дейкстра (Edsger Wybe Dijkstra) в 1958 году, но название осталось за Примом, т.к. у Дейкстры уже был алгоритм с его именем (поиск кратчайших путей в ориентированном графе). Этот алгоритм можно отнести к группе алгоритмов, построенных на наращивании дерева: существует только одна нетривиальная компонента (остальные представляют собой одиночные вершины), и она постепенно наращивается добавлением «безопасных» ребер. Время работы алгоритма Джарника-Прима может достигать O(E+VlogV) при использовании фибоначчиевых куч.

Другой наиболее известный подход носит название алгоритма Крускала (Joseph Kruskal). Он был придуман автором в 1956 году. Основная стратегия этого алгоритма такова: ребра упорядочиваются по весу; на каждом шаге к строящемуся остову добавляется самое легкое ребро, которое соединяет вершины из различных компонент. Таким образом на каждом шаге строящееся множество состоит из одной или более нетривиальных компонент, каждая из которых является подграфом некоторого минимального остова. Время работы алгоритма Крускала составляет O(ElogE) при использовании для хранения компонент связности системы непересекающихся множеств с объединением по рангу и сжатием путей (самый быстрый известный метод). Большая часть времени уходит на сортировку ребер.

В последнее время (с 1980-х годов) было предложено много различных подходов для оптимизации и улучшения скорости работы известных алгоритмов. Если количество ребер в графе достаточно велико, то реализация алгоритма Прима с использованием фибоначчиевых куч дает временную оценку O(E). Для разреженных графов (sparser graphs) Фредман и Тарьян (Fredman, Tarjan, 1987) предложили алгоритм, работающий с эффективностью O(ElogV), комбинирующий идеи из алгоритмов Прима и Борувки с использованием дополнительных структур данных. Немного позднее Габов, Галил, Спенсер и Тарьян улучшили этот алгоритм, добившись оценки времени O(EloglogV) (H.N. Gabow, Z. Galil, T. Spencer, and R.E. Tarjan. 1986. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6, 109 –122).

Интересный подход для уменьшения времени работы алгоритма построения минимального остовного дерева предложили Сан Чунг и А. Кондон в статье, посвященной параллельной имплементации алгоритма Борувки на нескольких скоростных процессорах [3]. Они показали, что, разделяя подзадачи для нескольких вычислительных центров и оптимизируя механизм синхронизации, можно добиться небольшого увеличения производительности по сравнению с базовой версией алгоритма.

Принципиально отличающийся от представленных алгоритм, работающий со временем O(Eα’(E,V), где α’ – функция, обратная к функции Аккермана, предложил Чазел [4]. Так как α’ растет очень медленно, то время работы близко к линейному. В отличие от всех предыдущих, этот алгоритм не следует жадной стратегии, тем не менее используя алгоритм Борувки для препроцессинга графа.

Много алгоритмов посвящено связанной задаче верификации остовного дерева (spanning tree verification problem). Эту проблему можно сформулировать следующим образом. Пусть нам дан граф G и некоторое его покрывающее дерево. Требуется проверить, является ли данное дерево минимальным.

Вопрос о том, является ли текущее остовное дерево минимальным, был исследован Тарьяном (1979), Комлосом (Komlos, 1984) и позднее Диксоном, Раухом и Тарьяном в 1992 году (B. Dixon, M. Rauch and R. E. Tarjan. 1992. Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput. 21, 1184 –1192). В алгоритме 1979 года Тарьян использовал сжатие путей и давал приблизительно линейную оценку времени. Алгоритм Комлоса был первым, который использовал линейное количество сравнений, хотя и нелинейное время для определения, что сравнивать. Единственный известный линейный алгоритм для решения этой задачи, предложенный в 1992 году, использует идеи алгоритмов 1979 и 1984 годов, применяя алгоритм Комлоса для выполнения небольших подзадач (например, препроцессинг графа). Упрощенную и улучшенную версию этого алгоритма приводит В. Кинг в своей работе «Упрощенный алгоритм верификации минимальных остовных деревьев» [6].

Каргер, Клейн и Тарьян в 1995 году представили рандомизированный алгоритм построения минимального остовного дерева [5], работающий со временем O(V+E) и использующий алгоритм Борувки для промежуточных шагов и алгоритм Кинга для верификации остовных деревьев. Стратегия заключалась в идентификации подмножества ребер, не входящих в минимальное остовное дерево.

Наконец, Фредман и Уиллард (M. Fredman and D. E. Willard. 1993. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48, 424 – 436) показали, как найти минимальное остовное дерево со временем O(V+E), используя детерминистический алгоритм, не основанный на сравнении ребер. Их подход полагает, что данные представлены в виде b-битных целых чисел и компьютерная память оперирует с b-битными словами.

Задача построения минимального остовного дерева встречается в различных областях. Интересным ее применением является проблема построения смешанного остовного дерева (Dana Richards and Jeffrey S. Salowe. Mixed spanning trees in theory and practice. International Journal Of Computational Geometry & Applications. Vol. 9, No. 3 (1999), 277-292): построить для графа дерево со свойствами минимального остовного дерева и дерева кратчайших путей. Другой важной задачей является быстрое обновление минимального остовного дерева при изменении графа. В статье Sajal K. Das, Paolo Ferragina "An Erew Pram algorithm for updating minimum spanning trees" показано, как для графа с n вершинами и m ребрами выполнить обновление одного ребра за учетное время O(logn).

Проблема построения минимального остовного дерева достаточно разносторонняя, и продолжает исследоваться и сегодня. В настоящей статье представлены только базовые алгоритмы. Ознакомиться с более продвинутыми алгоритмами можно по статьям из списка используемой литературы.

Построение минимального остовного дерева

Рассмотрим общую схему работы алгоритмов построения минимального остовного дерева с использованием жадной стратегии. Итак, пусть дан связный неориентированный граф G(V;E) c n вершинами и весовая функция w: ER.

Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграф А исходного графа G, который называется промежуточным остовным лесом. Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое ребро e=(u,v) выбирается так, чтобы не нарушить этого свойства: A ∪ {e} тоже должно быть подграфом минимального. Такое ребро называется безопасным.

Вот как выглядит общий алгоритм построения минимального остовного дерева:

MST-GENERIC(G,w)
1: A ← 0
2: while (пока) A не является остовом
3:     do найти безопасное ребро (u,v) ∈ E для A
4:         AA ∪ {(u,v)}
5: return A

По определению A, он должен оставаться подграфом некоторого минимального остова после любого числа итераций. Конечно, главный вопрос состоит в том, как искать безопасное ребро на шаге 3. Понятно, что такое ребро всегда существует, если A еще не является минимальным остовом (любое ребро остова, не входящее в A). Заметим, что так как A не может содержать циклов, то на каждом шаге ребром соединяются различные компоненты связности (изначально все вершины в отдельных компонентах, в конце A – одна компонента). Таким образом цикл выполняется (n-1) раз.

Далее приводится общее правило отыскания безопасных ребер. Для этого доказана теорема, которая поможет находить безопасные ребра. Предварительно докажем маленькую лемму:

Лемма: пусть Т – минимальное остовное дерево. Тогда любое ребро е из T – безопасное.
Док-во: в Т – (n-1) ребро. На каждом шаге Generic-MST мы добавляли одно безопасное ребро. Всего выполнено (n-1) шагов, следовательно, все ребра в T – безопасные по определению.

Теорема: Пусть G(V;E) – связный неориентированный граф и на множестве Е определена весовая функция w. Пусть А – некоторый подграф G, являющийся в то же время подграфом некоторого минимального остовного дерева T. Рассмотрим компоненту связности К из А. Рассмотрим множество E(K) ребер графа G, только один конец которых лежит в К. Тогда ребро минимального веса из E(K) будет безопасным.
Док-во: Пусть e=(u,v) – минимальное по весу ребро из E(K). Пусть минимальный остов T не содержит e (в противном случае доказываемое утверждение очевидно по приведенной выше лемме). Т.к. T связен, в нем существует некоторый (единственный) ациклический путь p из u в v, и e замыкает его в цикл. Поскольку один из концов e лежит в K, а другой в V \ K, в пути p существует хотя бы одно ребро e'=(x,y), которое обладает тем же свойством. Это ребро не лежит в A, т.к. в A пока что нет ребер между K и V \ K. Удалим из T ребро e' и добавим e. Так как w(e') < w(e), мы получим остовное дерево T', суммарный вес которого меньше суммарного веса T. Таким образом, T не является минимальным остовом. Противоречие. Следовательно, T содержит e.

В связи с приведенной теоремой введем следующее

Определение. Безопасным ребром e относительно некоторой компоненты связности К из А назовем ребро с минимальным весом, ровно один конец которого лежит в К.

Алгоритм Борувки

Итак, пусть дан связный неориентированный граф G(V;E) и на нем задана весовая функция . Пусть A – промежуточный остовный лес для графа V. На первом шаге A состоит из всех вершин G и пустого множества ребер. В начале очередной фазы алгоритма Борувки, для каждой компоненты связности промежуточного остовного леса выбирается лидер («leader» node, Erickson [7]) или корень - вершина, сопоставляемая каждой компоненте. Сделать это можно в простейшем случае с помощью обхода A в глубину: вершина, с которой начинается обход очередной компоненты, и будет ее лидером. В алгоритме за это отвечает процедура CHOOSE-LEADERS. Лидер для вершины v хранится в переменной leader(v).

После того, как лидеры выбраны, для каждой компоненты связности находится безопасное для нее ребро, по существу методом грубой силы. Это работа процедуры FIND-SAFE_EDGES. Безопасное ребро для лидера v' хранится в переменной safe(v'). Как только все такие ребра отобраны, они добавляются к A. Процесс продолжается до тех пор, пока в A присутствует больше одной компоненты связности.

MST-BORUVKA(G,w)
1: A ← (V,0)
2: while (пока) в A больше одной компоненты связности
3:     do CHOOSE-LEADERS(A)
4:        FIND-SAFE-EDGES(G)
5:        foreach (для каждого) лидера v'
6:          добавить safe(v') в A
7: return A

Вот простой возможный вид процедуры поиска безопасных ребер:

FIND-SAFE-EDGES(G)
1: foreach (для каждого) лидера v'
2:     safe(v') ← ∞
3: foreach (для каждого) ребра (u,v) ∈ E
4:     u' ← leader(u)
5:     v' ← leader(v)
6:     if u'v' then
7:        if w(u,v) < w(safe(u')) then
8:           safe(u') ← (u,v)
9:        if w(u,v) < w(safe(v')) then
10:          safe(v') ← (u,v)

Схема работы алгоритма представлена на рисунках Б1-Б5.





Рис. Б1. Начальная фаза. Минимальный покрывающий лес состоит из всех вершин графа и пустого множества ребер.


Рис. Б2. Для каждой компоненты связности (для каждой вершины) находим безопасные ребра. Они отмечены стрелками от компоненты вдоль безопасного ребра.


Рис. Б3. Добавляем безопасные ребра к минимальному остовному лесу.


Рис. Б4. Находим безопасные ребра для каждой компоненты связности.


Рис. Б5. Добавляем найденные ребра. Минимальное остовное дерево построено.


Каждое обращение к FIND-SAFE-EDGES требует O(E) времени, т.к. внутри процедуры происходит проверка каждого ребра. Так как мы считаем граф связным, в нем максимум |E|+1 вершин. Тогда в случае, если граф представлен связным списком, требуется O(E) времени для выполнения каждой итерации основного цикла алгоритма Борувки MST-BORUVKA. Каждая итерация уменьшает количество компонент как минимум в два раза (худший случай, если все компоненты разбиваются на пары). Таким образом, если изначально количество компонент было равно V, главный цикл алгоритма выполняется O(logV). Общее время работы алгоритма получается равным O(ElogV).

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

Алгоритм Крускала объединяет вершины графа в несколько связных компонент, каждая из которых является деревом. На каждом шаге из всех ребер, соединяющих вершины из различных компонент связности, выбирается ребро с наименьшим весом. Необходимо проверить, что оно является безопасным. Безопасность ребра гарантируется ранее доказанной теоремой о безопасных ребрах. Так как ребро является самым легким из всех ребер, выходящих из данной компоненты, оно будет безопасным.

Остается понять, как реализовать выбор безопасного ребра на каждом шаге. Для этого в алгоритме Крускала все ребра графа G перебираются по возрастанию веса. Для очередного ребра проверяется, не лежат ли концы ребра в разных компонентах связности, и если это так, ребро добавляется, и компоненты объединяются.

Удобно использовать для хранения компонент структуры данных для непересекающихся множеств, как, например, списки или, что лучше, лес непересекающихся множеств со сжатием путей и объединением по рангу (один из самых быстрых известных методов). Элементами множеств являются вершины графа, каждое множество содержит вершины одной связной компоненты. Для работы с множествами используются следующие процедуры:

Make-Set(v) Создание множества из набора вершин
Find-Set(v) Возвращает множество, содержащее данную вершину
Union(u,v) Объединяет множества, содержащие данные вершины

Общая схема алгоритма выглядит так:

MST-KRUSKAL(G,w)
1: A ← 0
2: foreach (для каждой) вершины vV[G]
3:     do Make-Set(v)
4: упорядочить ребра по весам
5: for (u,v) ∈ E (в порядке возрастания веса)
6:     do if Find-Set(u)Find-Set(v) then
7:         AA ∪ {(u,v)}
8:         Union(u,v)
9: return A

На рисунках К1-К8 представлена работа алгоритма.



Рис. К1. Начальная фаза. Минимальный покрывающий лес пуст.


Рис. К2. Перебираем ребра в порядке возрастания веса: первое ребро с весом 2. Добавляем его к А.


Рис. К3. Следующее безопасное ребро с весом 6. Добавляем его.


Рис. К4.


Рис. К5.


Рис. К6.


Рис. К7.


Рис. К8. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.


Подсчитаем время работы алгоритма. Будем считать, что для хранения непересекающихся множеств используется метод с объединением по рангу и сжатием путей ([1], 21.3), т.к. это самый быстрый способ из известных на сегодняшний день. Инициализация занимает время O(V), упорядочение ребер в строке 4 – O(ElogE). Далее производится O(E) операций, в совокупности занимающих время O(Eα’(E,V)), где α’ - функция, обратная к функции Аккермана (см. [1], 21.4). Поскольку α’(E,V) = o(logE), общее время работы алгоритма Крускала составляет O(ElogE) (основное время уходит на сортировку).

Алгоритм Прима

Как и алгоритм Крускала, алгоритм Прима следует общей схеме алгоритма построения минимального остовного дерева: на каждом шаге мы добавляем к строящемуся остову безопасное ребро. Алгоритм Прима относится к группе алгоритмов наращивания минимального остова: на каждом шаге существует не более одной нетривиальной (не состоящей из одной вершины) компоненты связности, и каждый к ней добавляется ребро наименьшего веса, соединяющее вершины компоненты с остальными вершинами. По теореме такое ребро является безопасным.

При реализации надо уметь на каждом шаге быстро выбирать безопасное ребро. Для этого удобно воспользоваться очередью с приоритетами (кучей). Алгоритм получает на вход граф G и его корень r – вершина, на которой будет наращиваться минимальный остов. Все вершины G, еще не попавшие в дерево, хранятся в очереди с приоритетом Ω. Приоритет вершины v определяется значением key[v], которое равно минимальному весу ребер, соединяющих v с вершинами минимального остова. Поле p[v] для вершин дерева указывает на родителя, а для вершин из очереди, указывает на ноду дерева, в которою ведет ребро с весом key[v] (одно из таких ребер, если их несколько).

Тогда алгоритм Прима выглядит следующим образом:

MST-PRIM(G,w, r)
1: Ω ← V[G]
2: foreach (для каждой) вершины u ∈ Ω
3:     do key[u] ← ∞
4: key[r] ← 0
5: p[r] = NIL
6: while (пока) Ω ≠ 0
7:     do u ← EXTRACT-MIN(Ω)
8:        foreach (для каждой) вершины v ∈ Adj(u)
9:            do if v ∈ Ω и w(u,v) < key[v] then
10:               p[v] ← u
11:               key[v] ← w(u,v)

На рисунках П1-П8 показана схема работы алгоритма Прима с корнем r.



Рис. П1. Начальная фаза. Минимальный покрывающий лес состоит из корня и пустого множества ребер.


Рис. П2. Ребро с весом 6 является минимальным ребром, соединяющим корень с остальными вершинами. Добавляем его к минимальному остову.


Рис. П3. Следующее безопасное ребро с весом 11. Добавляем его.


Рис. П4.


Рис. П5.


Рис. П6.


Рис. П7.


Рис. П8. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.


Время работы алгоритма Прима зависит от того, как реализована очередь с приоритетами Ω. Если использовать двоичную кучу, инициализацию в строках 1-4 можно выполнить за время O(V). Далее цикл выполняется |V| раз, и каждая операция EXTRACT-MIN занимает время O(VlogV). Цикл for в строках 8-11 выполняется в общей сложности O(E), поскольку сумма степеней вершин графа равна 2|E|. Проверку принадлежности в строке 9 можно выполнить за время O(1), если хранить состояние очереди еще и как битовый вектор размера |V|. Присваивание в строке 11 подразумевает выполнение операции уменьшения ключа (DECREASE-KEY), которая для двоичной кучи может быть выполнена за время O(logV). Таким образом всего получаем O(VlogV+ElogV)=O(ElogV).

Лучшую оценку можно получить, если использовать фибоначчиевы кучи. С помощью фибоначчиевых куч можно выполнить операцию EXTRACT-MIN за учетное время O(logV), а операцию DECREASE-KEY – за учетное время O(1). В этом случае суммарное время работы алгоритма Прима составит O(E+VlogV).

Список используемой литературы

  1. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. — М.: Вильямс, 2005. — 1296 с.
  2. R. L. Graham and P. Hell. On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1): 43-57, 1985.
  3. S. Chung, A. Condon. Parallel implementation of Boruvka’s minimum spanning tree algorithm. In Proc. 10th Int’l Parallel Processing Symp. (IPPS’96), pages 302–315, April 1996.
  4. B. Chazelle. A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity. Journal of the ACM, 47 (2000), 1028-1047.
  5. David R. Karger, Philip N. Klein, and Robert E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2): 321-328, March 1995.
  6. V. King. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263–270. 1997.
  7. Jeff Erickson. Minimum spanning trees. Lecture notes: Fall 2002 — CS 373: Combinatorial Algorithms.

Визуализаторы

  1. Рыбаков Глеб. Построение минимального остовного дерева (алгоритмы Крускала, Прима, Борувки)

Рыбаков Глеб


Green[ek] / 2008-05-06 07:46:00

Спасибо за статью. Но больше даже за рисунки! Такая зубодробительная теория без рисунков почти не воспринимается мною(

Кирилл / 2008-05-14 15:34:44

Спасибо большое за статью! :)

DarkMessiah / 2008-05-24 20:17:32

Спасибо) Эта статья очень помогла

Иван / 2008-09-23 22:46:49

Большое спасибо! Очень подробная и понятная статья.

Dobermann86 / 2009-02-23 12:28:07

Огромное спасибо

Александр / 2009-05-09 20:43:32

Спасибо! Хорошая статья

antiPrima / 2009-10-26 18:02:06

Отличная статья. Отдельное спасибо за рисунки)

Osik / 2009-11-11 14:13:58

Большое Спасибо за статью!

Юрий Гришин / 2009-12-14 13:18:53

Большое спасибо за материал, ресурс целиком добавляю в избранное.

Рады оказаться полезными.

hellga-rain / 2010-01-08 00:56:03

Огромное спасибо за статью!!!

Елена / 2011-05-13 22:05:50

Наконец-то поняла, как реализовать алгоритм Прима. Благодарю!!

Евгений / 2011-08-29 17:02:26

"Рис.2-б" - забыли отметить правое ребро. С ребром веса "-3" и получается нулевой суммарный вес.

Спасибо за статью. Очень грамотно написано.

Анна / 2013-04-24 13:07:44

очень хорошая разъяснительная работа, спасибо

Константин / 2014-06-26 14:51:18

Спасибо Вам!

И таким как Вы, которые выкладывают статьи в Интернет не только ради повышения цитируемости сайта, но и чтоб поделиться с другими полезной информацией.

Лера / 2014-09-03 04:44:40

Отличные иллюстрации! Моментально все понятно)

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий