Курсовая работа на тему: Алгоритм Краскала. Описание алгоритма Краскала. Псевдокод алгоритма

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оглавление

- Введение

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

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

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

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

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

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

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

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

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

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

- Оценка сложности Заключение

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

Список литературы

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/. - Загл. с экрана.