Материал: курсовой проект алгоритм прима

2.2Разработка псевдокода

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

На рисунке 2 представлен псевдокод алгоритма Прима. На входе матрица смежности cost[i][j] размером n/n.

Рисунок 2 – Псевдокод реализации алгоритма Прима через матрицу смежностей

На выходе мы имеем минимальное остовное дерево N и суммарный вес каркаса mincost.

Алгоритм Крускала. На рисунке 3 представлен псевдокод алгоритма Крускала. На входе матрица смежности cost[i][j] размером n/n.

Рисунок 3 – Псевдокод реализации алгоритма Крускала через матрицу смежностей

На выходе мы имеем минимальное остовное дерево.

2.3 Визуализация алгоритма

Проиллюстрируем алгоритм Прима графе. На рисунке 1 представлен исходный звешенный связный неориентированный граф. Выберем вершину A в качестве начальной. Среди ребер, инцидентных вершине A, выбираем ребро A,D наименьшего веса и включаем его в остовное дерево T. Вершина D инцидентна ребрам (D,B), (D,E), (D,F). В остов включаем ребро (D,F). Ребро (A,B), имеет меньший вес чем ребро (F,E), с силу данного обстоятельства, нам необходимо вернуться в вершину A и включить в дерево ребро (A,B).Далее проходим по незадействованным вершинам и включаем в остов ребра (B,E), (E,C), (E,G). В результате мы получаем минимальное остовное дерево – рисунок 5.

Рисунок 4 – Исходный  взвешенный связный неориентированный граф.

Рисунок 5 – Минимально остовное дерево исходного графа.

3. Анализ трудоемкости

Анализ алгоритма Прима

Время выполнения программы, имеет порядок O(n).

Асимптотика алгоритма зависит от способа хранения графа и способа хранения вершин, не входящих в дерево. Если приоритетная очередь Q реализована как обычный массив d, то Extract.Min(Q) выполняется за O(n), а стоимость операции d[u] ← w(v, u) составляет O(1). Если Q  представляет собой бинарную пирамиду, то стоимость Extract.Min(Q) снижается до O(logn), а стоимость d[u] ← w(v, u) возрастает до O(logn). При использовании фибоначчиевых пирамид операция Extract.Min(Q)  выполняется за O(logn),аd[u] ← w(v, u) за O(1). Что наглядно продемонстрированно в таблице 1.

Таблица 1 зависимость асимптотики от способа реализации алгоритма

4.Тестирование программ реализации алгоритмов

4.1 Тестирование правильности

В таблице 2 приведён протокол тестирования правильности работы программы, по алгоритму Прима. В входных данных вводится матрица смежности, в выходных данных ожидается получить суммарный вес контура и минимальное остовное дерево.

Таблица 2 протокол тестирования правильности

В таблице 3 приведён протокол тестирования правильности работы программы по алгоритму Крускала. В входных данных вводится матрица смежности, в выходных данных ожидается получить минимальное остовное дерево.

Таблица 3 протокол тестирования правильности

4.2 Анализ по времени

Анализ по времени проводится функцией clock() из стандартной библиотеки <time.h>. Длины ребер задаем с помощью функции rand() из той же библиотеки <time.h>, длины этих ребер будут варьироваться от 0 до 15. Ниже на рисунке 7 представлена диаграмма роста функции f(t)=N, где t – время работы программы, а N – количество вершин. Жирным выделен график роста функции алгоритма Прима, а тонким выделен график роста функции алгоритма Крускала.

Рисунок 6 – Диаграмма роста функции

Заключение

В ходе реализации алгоритма, были применены теоретические и практические знания полученные за период обучения.

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