Алгоритмы Краскала и Прима
Реализация алгоритмов Краскала и Прима для построения минимального остовного дерева взвешенного связного неориентированного графа. Анализ трудоемкости алгоритмов, их псевдокоды и тестирование. Применение алгоритма Краскала на практике в работе авиалиний.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 25.12.2012 |
| Размер файла | 142,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
1
Содержание
- Введение
- 1 Алгоритм Краскала
- 1.1 Описание алгоритма Краскала
- 1.2 Псевдокод алгоритма
- 1.3 Блок-схема алгоритма
- 1.4 Сложность алгоритма
- 2. Алгоритм Прима
- 2.1 Описание алгоритма Прима
- 2.2 Псевдокод алгоритма
- 2.3 Блок-схема алгоритма
- 2.4 Код программы
- 2.5 Оценка сложности
- Заключение
- Список использованных источников
Введение
Объектом исследования курсовой работы стала реализация алгоритма Краскалы.
Целями работы являлись:
1) ознакомление с алгоритмом Краскалы, его историей;
2) реализация алгоритма, для построения минимального остовного дерева;
3) анализ трудоёмкости алгоритма;
4) тестирование алгоритма.
Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер максимально возможная. Если исходный граф несвязен, то описываемую ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент.
Алгоритм Краскала (или алгоритм Крускала) - алгоритм построения минимального отовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джзефом Крускалом в 1956 году.
Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.
Полный граф задается списком ребер. Перед работой список ребер сортируется по возрастанию длины. На каждом шаге просматривается список ребер, начиная с ребра, следующего за вошедшим в решение на предыдущем шаге, и к строящемуся поддереву присоединяют то ребро, которое не образует цикла с ребрами, уже включенными в решение.
Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: есть n городов, через которые можно проложить маршрут так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Требуется найти такой маршрут, чтобы стоимость проезда была максимальной.
На практике алгоритм Краскалы применятся в работе авиалиний при нахождении наименьшего воздушного пути из одного пункта назначения в другой.
Алгоритм Прима - алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.
Построение начинается с дерева, включающего в себя одну (произвольную) вершину. В течение работы алгоритма дерево разрастается, пока не охватит все вершины исходного графа. На каждом шаге алгоритма к текущему дереву присоединяется самое лёгкое из рёбер, соединяющих вершину из построенного дерева и вершину не из дерева.
1 Алгоритм Краскала
1.1 Описание алгоритма Краскала
Формулировка.
Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.
Алгоритм состоит из следующей последовательности действий:
1. Создается список ребер E, содержащий длину ребра, номер исходной вершины ребра (i), номер конечной вершины ребра (j), признак включения данного ребра в дерево.
2. Данный список упорядочивается в порядке возрастания длин ребер.
3. Просматривается список E и выбирается из него ребро с максимальной длиной, еще не включенное в результирующее дерево и не образующее цикла с уже построенными ребрами.
4. Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.
1.2 Псевдокод алгоритма
Отсортировать ребра в порядке возрастания весов
инициализировать структуру разбиений
edgeCount=l
while edgeCount<=E and includedCount<=М-l do
parentl=FindRoot (edge [edgeCount]. start)
parent2=FindRoot (edge [edgeCount]. end)
if parentl/=parent2 then
добавить edge [edgeCount] в остовное дерево
includedCount=includedCount=l
Union (parent1,parent2)
end if
edgeCount=edgeCount+l
end while.
E - число ребер в графе;
V - число вершин в графе
edgeCount - переменная;
includedCount - переменная;
Parent - массив, в котором под каждый элемент множества, с которым мы собираемся работать, отведена одна ячейка;
FindRoot (x) - (x элемент, для которого мы хотим найти корень части, его содержащей) процедура, начинающая с ячейки Parent [x], в которой хранится номер непосредственного предка элемента x;
Union - функция, выполняющая объединение двух частей в одну.
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 Для найденного ребра, вершину принадлежащую множеству оставшихся:
· Вычеркиваем из множества оставшихся.
· Добавляем к множеству остовных.
выбрать начальный узел
сформировать начальную кайму, состоящую из вершин,
соседних с начальным узлом
while в графе есть вершины, не попавшие в дерево do
выбрать ребро из дерева в кайму с наименьшим весом
добавить конец ребра к дереву
изменить кайму, для чего
добавить в кайму вершины, соседние с новой
обновить список ребер из дерева в кайму так,
чтобы он состоял из ребер наименьшего веса
end while
2.2 Псевдокод алгоритма
MST_PRIM (G, w, r)
1 for (Для) каждой вершины u є V [G]
2 do key [u] " - INFINITY
3 prev [u] " - NIL
4 key [r] " - 0
5 Q " - V [G]
6 while Q не пустая
7 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
11 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.
4. [Электронный ресурс]. - Режим доступа: http://www.lotos-khv. narod.ru/. - Загл. с экрана.
Размещено на Allbest.ru
Подобные документы
Разработка программной реализации решения задачи о минимальном покрывающем дереве графа (построение минимального остова), используя алгоритмы Прима и Крускала. Подсчет времени работы алгоритмов. Их программная реализация на практике с помощью Delphi 7.
курсовая работа [538,1 K], добавлен 29.08.2010Способы построения остовного дерева (алгоритма поиска в глубину и поиска в ширину). Вид неориентированного графа. Понятие и алгоритмы нахождения минимальных остовных деревьев. Последовательность построения дерева графов по алгоритмам Крускала и Прима.
презентация [22,8 K], добавлен 16.09.2013Граф - совокупность точек и линий, в которой каждая линия соединяет две точки. Представление графов в ЭВМ. Составление алгоритм Краскала с использованием графов с оперделением оптимального пути прокладки телефонного кабеля в каждый из 8 городов.
курсовая работа [241,5 K], добавлен 23.12.2009Создание программы, выполняющей трассировку проводного монтажа алгоритмом Краскала. Конфигурация программы для работы под управлением операционных систем семейства Microsoft Windows. Исследование алгоритмических методов трассировки печатных соединений.
курсовая работа [663,0 K], добавлен 24.03.2014Применения языка логического программирования Пролог и языка программирования Haskell для реализации алгоритма поиска оптимального каркаса графа. Алгоритм Прима, преимущество перед другими алгоритмами нахождения оптимального каркаса, близких к полным.
курсовая работа [230,2 K], добавлен 13.06.2012Основные особенности эволюционных алгоритмов. Описание алгоритмов селекции, мутации, скрещивания, применяемых для реализации генетических алгоритмов. Вычисление функции приспособленности. Программная реализация. Тестирование и руководство пользователя.
курсовая работа [1,3 M], добавлен 11.03.2014Использование понятий из теории графов при разработке сетей и алгоритмов маршрутизации. Построение матрицы смежности и взвешенного ориентировочного графа. Результаты работы алгоритмов Дейкстры и Беллмана-Форда. Протоколы обмена маршрутной информацией.
курсовая работа [334,1 K], добавлен 20.01.2013Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.
контрольная работа [21,0 K], добавлен 16.12.2012Блок-схема алгоритма Флойда. Разработка его псевдокода в программе Microsoft Visual Studio. Программа реализации алгоритмов Беллмана-Форда. Анализ трудоемкости роста функции. Протокол тестирования правильности работы программы по алгоритму Флойда.
курсовая работа [653,5 K], добавлен 18.02.2013Общая характеристика и функциональные возможности системы "Компьютерное тестирование". Связи между информационными объектами. Проектирование алгоритмов обработки данных. Реализация алгоритмов обработки информации, разработка соответствующих макросов.
контрольная работа [542,8 K], добавлен 19.10.2010
