Нахождение минимального остовного дерева методом Крускала

Размещено на http://www.allbest.ru/

Реферат

Дисциплина

«Структуры и алгоритмы обработки данных»

на тему:

«Нахождение минимального остовного дерева методом Крускала»

Введение

Рассмотрим задачу построения минимального остовного дерева. Область применения такого рода задач весьма многочисленна: разработка сетей (например: задача о соединении n городов в единую телефонную сеть с минимальной суммарной стоимостью соединений); строительство дорог с минимальной общей стоимостью строительства; производство печатных плат и т.д.

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

В начале данной работы дано общее описание минимального остовного дерева и история подходов к ее решению. Далее описан алгоритм Крускала и разбор алгоритма на примере нахождения минимального остового дерева данного связанного графа.

1. Минимальное остовное дерево

Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном, неориентированном графе - это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

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

Свойства минимального остова:

· минимальный остов уникален, если веса всех рёбер различны. В противном случае, может существовать несколько минимальных остовов (конкретные алгоритмы обычно получают один из возможных остовов);

· минимальный остов является также и остовом с минимальным произведением весов рёбер (доказывается это легко, достаточно заменить веса всех рёбер на их логарифмы);

· минимальный остов является также и остовом с минимальным весом самого тяжелого ребра (это утверждение следует из справедливости алгоритма Крускала);

· остов максимального веса ищется аналогично остову минимального веса, достаточно поменять знаки всех рёбер на противоположные и выполнить любой из алгоритмов минимального остова.

У задачи построения минимального остовного дерева длинная и богатая история. Грэхем и Хелл в своей статье «История задачи построения минимального остовного дерева» начинают отсчет истории проблемы с работы Чекановского 1909 года. Первый и, наверное, простейший алгоритм восходит к Борувке, который в 1926 году, намного раньше, чем появились первые компьютеры, и даже раньше, чем была создана конструктивная теория графов, представил свое решение данной задачи. Немного позднее, в 1938 году Шоке, а затем Флорек, Лукасевич, Перкал, Штейнгауз и Зубжицкий в 1951 году и Соллин в начале шестидесятых снова переоткрывают алгоритм.

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

Наиболее известный подход носит название алгоритма Крускала. Он был придуман Джозефом Крускалом в 1956 году.

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

Алгоритм Крускала также называют жадный минимальный алгоритм дерева покрытия. Жадный алгоритм - это такой алгоритм, который всегда, на каждой стадии, выбирает наилучшую возможность (в нашем примере самый маленький вес). Жадные алгоритмы «близорукие» и не всегда приводят к наилучшему результату

Перед началом выполнения алгоритма Крускала, все рёбра сортируются по весу в порядке возрастания.

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

При построении постепенно возрастающих связанных компонент поочередно проверяются ребра из множества E в порядке возрастания их веса. Если очередное ребро связывает две вершины из разных компонент, тогда оно добавляется в остовное дерево. Если это ребро связывает две вершины из одной компоненты, то оно отбрасывается, так как его добавление в связанную компоненту может привести к образованию цикла. Число ребер, необходимое для остовного дерева равно n-1. Граф связан, а значит E содержит как минимум такое их количество. Когда остовное дерево будет содержать n-1 ребер, алгоритм завершается.

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

Сложность алгоритма для графа с n вершинами и m ребрами пропорциональна O (mlog m).

Построение минимальное остовное дерево начинается с графа T, состоящего только из n вершин графа G и не имеющего ребер.

1) Берем ребро с наименьшим весом 1. Ребро связывает две вершины из различных компонентов, тогда соединяем, эти две вершины 3, 4.

2) Берем следующее ребро весом 2. Ребро связывает две вершины из различных компонентов, тогда соединяем, эти две вершины 1,2.

3) Берем следующее ребро весом 3. Ребро связывает две вершины из различных компонентов, тогда соединяем, эти две вершины 2,3.

4) Берем следующее ребро весом 4. Ребро связывает две вершины из одной компоненты, тогда 2,4 отбрасываем.

5) Берем следующее ребро весом 5. Ребро связывает две вершины из одной компоненты, тогда вершину 1,3 тоже отбрасываем.

На основе выше разобранного примера мы изучили алгоритм Крускала. Определили сложность алгоритма. Узнали, что большая часть времени действия алгоритма уходит на первоначальную сортировку веса каждого ребра.

остовной дерево крускал минимальный

Размещено на Allbest.ru