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

Содержание

Введение

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

1.1 Описание алгоритма Краскала

1.2 Псевдокод алгоритма

1.3 Блок-схема алгоритма

1.4 Сложность алгоритма

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

2.1 Описание алгоритма Прима

2.2 Псевдокод алгоритма

2.3 Блок-схема алгоритма

2.4 Код программы

2.5 Оценка сложности

Заключение

Список использованных источников

Введение

Объектом исследования курсовой работы стала реализация алгоритма Краскалы.

Целями работы являлись:

) ознакомление с алгоритмом Краскалы, его историей;

) реализация алгоритма, для построения минимального остовного дерева;

) анализ трудоёмкости алгоритма;

) тестирование алгоритма.

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

Алгоритм Краскала (или алгоритм Крускала) - алгоритм построения минимального отовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джзефом Крускалом в 1956 году.

Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.

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

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

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

Алгоритм Прима - алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.

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

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

1.1 Описание алгоритма Краскала

Формулировка.

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

Алгоритм состоит из следующей последовательности действий:

.        Создается список ребер E, содержащий длину ребра, номер исходной вершины ребра (i), номер конечной вершины ребра (j), признак включения данного ребра в дерево.

2.      Данный список упорядочивается в порядке возрастания длин ребер.

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

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

1.2 Псевдокод алгоритма

Отсортировать ребра в порядке возрастания весов

инициализировать структуру разбиений

edgeCount=l

while edgeCount<=E and includedCount<=М-l do

parentl=FindRoot (edge [edgeCount]. start)=FindRoot (edge [edgeCount]. end)parentl/=parent2 then

добавить edge [edgeCount] в остовное дерево=includedCount=l(parent1,parent2)if=edgeCount+lwhile. - число ребер в графе;

V - число вершин в графе

edgeCount - переменная;

includedCount - переменная;- массив, в котором под каждый элемент множества, с которым мы собираемся работать, отведена одна ячейка;

FindRoot (x) - (x элемент, для которого мы хотим найти корень части, его содержащей) процедура, начинающая с ячейки Parent [x], в которой хранится номер непосредственного предка элемента x;- функция, выполняющая объединение двух частей в одну.

1.3 Блок-схема алгоритма

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

алгоритм краскал прим псевдокод

Рисунок 1 - Общая схема

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

Рисунок 2 - Блок-схема алгоритма сортировки вставками

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

Рисунок 3 - Блок-схема алгоритма Краскала

1.4 Сложность алгоритма

Сложность этого алгоритма совпадает со сложностью используемого алгоритма сортировки, поскольку число операций в цикле while линейно по числу ребер. Поэтому сложность алгоритма Крускала поиска МОД равна O (E\og Е).

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

2.1 Описание алгоритма Прима

Описание.

Сам алгоритм имеет очень простой вид. Искомый минимальный остов строится постепенно, добавлением в него рёбер по одному. Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно). Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов. После этого остов содержит уже две вершины, и теперь ищется и добавляется ребро минимального веса, имеющее один конец в одной из двух выбранных вершин, а другой - наоборот, во всех остальных, кроме этих двух. И так далее, т.е. всякий раз ищется минимальное по весу ребро, один конец которого - уже взятая в остов вершина, а другой конец - ещё не взятая, и это ребро добавляется в остов (если таких рёбер несколько, можно взять любое). Этот процесс повторяется до тех пор, пока остов не станет содержать все вершины (или, что то же самое, n-1 ребро). В итоге будет построен остов, являющийся минимальным. Если граф был изначально не связен, то остов найден не будет (количество выбранных рёбер останется меньше n-1).

Вход: Связный неориентированный граф G (V,E)

Выход: Множество T рёбер минимального остовного дерева

Алгоритм.

·        Множество остовных вершин - исходная вершины

·        Множество оставшихся - все вершины за исключением исходной

·        Пока множество оставшихся не пусто:

o   Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес

o   Для найденного ребра, вершину принадлежащую множеству оставшихся:

·        Вычеркиваем из множества оставшихся.

·        Добавляем к множеству остовных.

сформировать начальную кайму, состоящую из вершин,

соседних с начальным узломв графе есть вершины, не попавшие в дерево do

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

добавить конец ребра к дереву

изменить кайму, для чего

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

обновить список ребер из дерева в кайму так,

чтобы он состоял из ребер наименьшего веса

end while

2.2 Псевдокод алгоритма

MST_PRIM (G, w, r)

for (Для) каждой вершины u є V [G]

2 do key [u] " - INFINITY

prev [u] " - NIL

key [r] " - 0

Q " - V [G]

while Q не пустая

do u " - Extract_Min (Q)

8 for (Для) каждой вершины v є Adj [u]

9 do if v є Q и w (u,v) < key [v]

10 then prev [v] " - u

key [v] " - w (u, v)

2.3 Блок-схема алгоритма

2.4 Код программы

2.5 Оценка сложности

Время работы алгоритма Прима зависит от выбранной реализации очереди с приоритетами Q. Если реализовать ее как бинарную пирамиду, то для выполнения инициализации в строках 1-5 потребуется времени О (V). Тело цикла while выполняется |V| раз, а поскольку каждая операция Extract_Min занимает время О (lg V), общее время всех вызовов процедур Extract__Min составляет О (V*lg V). Цикл for в строках 8-11 выполняется всего О (Е) раз, поскольку сумма длин всех списков смежности равна 2|Е|. Внутри цикла for проверка на принадлежность Q в строке 9 может быть реализована за постоянное время, если воспользоваться для каждой вершины битом, указывающим, находится ли она в Q, и обновлять этот бит при удалении вершины из Q. Присвоение в строке 11 неявно включает операцию Decrease_Key над пирамидой. Время выполнения этой операции - О (lg V). Таким образом, общее время работы алгоритма Прима составляет o (V * lg V + Е * lg V) = o (Е * lg V), что асимптотически совпадает со временем работы алгоритма Крускала.

Заключение

В курсовом проекте был изучен алгоритм Краскала. Рассмотрены блок-схема, псевдокод данного алгоритма. Разработана программа, реализующая алгоритм Краскала, поиск минимального остовного дерева. Изучен алгоритм Прима.

Список использованных источников

1.       Свободная энциклопедия ВикипедиЯ [Электронный ресурс]. - Режим доступа: http://ru. wikipedia.org/. - Загл. с экрана.

2.      Алгоритмы, методы, исходники [Электронный ресурс]. - Режим доступа: http://algolist. manual.ru/. - Загл. с экрана.

3.       Макконелл Дж. Основы современных алгоритмов: 2-е дополненное издание М.: Техносфера, 2004. - 368с. ISBN 5-94836-005-9.

.         [Электронный ресурс]. - Режим доступа: http://www.lotos-khv. narod.ru/. - Загл. с экрана.