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

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

1

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



Реферат

Отчет 25 с., 19 рис., 4 источников.

АЛГОРИТМ, ГРАФ, РЕБРО, ВЕРШИНА, ОСТОВНОЕ ДЕРЕВО, ПСЕВДОКОД, БЛОКСХЕМА, РЕАЛИЗАЦИЯ.

Объект исследования: алгоритм Краскала

Цель работы: закрепление знаний и умений, полученных в процессе теоретического обучения.

Метод работы: закрепление теоретических знаний с помощью разработки программы, реализующий данный алгоритм.



Содержание

Введение

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

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

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

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

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

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

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 представлена общая схема алгоритма.

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

1

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

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

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

1

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

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

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

1

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

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

Сложность этого алгоритма совпадает со сложностью используемоего алгоритма сортировки, поскольку число операций в цикле 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 Блок-схема алгоритма

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

1

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

1

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

1

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

1

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

1

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

1

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

#include <iostream>

#include <vector>

#include <iomanip>

#define forn(i,n) for(int i=0;i<n;i++)

using namespace std;

int n,m;

vector <pair<int,int>> g[500];//кроме вершин список смежности хранит и вес ребра

vector <bool> used(500,0);//вектор использованных вершин

int inf=10000000;

vector <int> d(500,inf);//вектор расстояний

int main()

{

freopen("input.txt","rt",stdin);

freopen("output.txt","wt",stdout);

cin>>n>>m;

int x,y,l;

pair <int,int> temp;

forn(i,m){

cin>>x>>y>>l;

x--;

y--;

temp.first=y;

temp.second=l;

g[x].push_back(temp);

temp.first=x;

g[y].push_back(temp);

}

vector <pair<int,int>> path(500);

d[0]=0;

while(true){

int v=-1;

int dist=inf;

forn(u,n)

if(!used[u] && dist>=d[u])

{

v=u;

dist=d[u];

}

if (v==-1) break;

used[v]=true;

forn(u,g[v].size())

if(!used[g[v][u].first]) {

if (d[g[v][u].first]>g[v][u].second) path[g[v][u].first]=make_pair(v,g[v][u].first);

d[g[v][u].first]=min(d[g[v][u].first],g[v][u].second);

}

}

long long sum=0;

forn(i,n) sum+=d[i];

cout<<sum<<endl;

forn(i,n-1)

cout<<path[i+1].first+1<<" "<<path[i+1].second+1<<endl;

return 0;

}

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. Решетов Ю.А. Алгоритмы, методы, исходники, 2012.

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

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

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

...