Сравнение
Проведя сравнение времени, затрачиваемого на алгоритмы Краскала и Прима были получены следующие графики:
Количество вершин графа
Время в нс
На рисунке оранжевым цветом представлен алгоритм Краскала, серым – алгоритм Прима. По графику видно, что при увеличении размерности матрицы смежности (то есть, при увеличении количества вершин графа) время, затрачиваемое на обработку алгоритмов, увеличивается тоже. Но стоит отметить, что на алгоритм Краскала времени затрачивается больше, нежели чем на алгоритм Прима. Это связано с тем, что в программе превалируют уплотнённые графы с большим множеством рёбер, ведь именно в таких условиях алгоритм Прима быстрее.
Точно это же самое подтверждается на небольших примерах: алгоритм Краскала был пройден за 6 шагов, а алгоритм Прима за 5 шагов.
Описание программы
Сама программа включает в себя несколько функций, как:
int get_random_graph(int** graph, int size)
void Prim(int** graph, int n)
void kruskal(int n, int edgescount, int** graph)
Функция 1 необходима для заполнения графа размерности size случайными числами. Функции передаётся в качестве аргументов указатель на матрицу смежности и её размер.
Функция 2 – алгоритм Прима. Функции передаётся в качестве аргументов указатель на матрицу смежности и её размер.
Функция 3 – алгоритм Краскала. Функции передаётся в качестве аргументов указатель на матрицу смежности и её размер.
Приложение
-
#include <iostream> #include <stdlib.h> #include <conio.h> #include <time.h> #include <chrono> #include <fstream> #include <algorithm> #include <vector> #define k1 2 #define INF 1000000000 using namespace std; using namespace chrono; int get_random_graph(int** graph, int size) { int edges = 0; for (int i=0; i<size; i++) edges += (size-i); edges -= 10; for(int i = 0; i < size; i++) graph[i][i] = 0; for(int i = 0; i < size; i++) for(int j = 0; j < size; j++) if(i != j) { int weight = 1 + (rand() % 10); graph[i][j] = graph[j][i] = (weight < 10) ? (weight) : (9999); } for(int i = 0; i < size; i++) for(int j = 0; j < size; j++) if ((graph[i][j]==9999)&&(i>j)) edges--; return edges; } void Prim(int** graph, int n) { int no_edge = 0; int selected[n]; selected[0] = true; int x; int y; while (no_edge < n - 1) { int min = INF; x = 0; y = 0; for (int i = 0; i < n; i++) if (selected[i]) for (int j = 0; j < n; j++) if (!selected[j] && graph[i][j]) if (min > graph[i][j]) { min = graph[i][j]; x = i; y = j; } selected[y] = true; no_edge++; } } void kruskal(int n, int edgescount, int** graph) { std::vector<std::vector<int>>edges(edgescount, std::vector<int>(3)); for (int i = 0; i<n; i++) for (int j = 0; j <n; j++) { edges[i][0] = graph[i][j]; edges[i][1] = i; edges[i][2] = j; } sort(edges.begin(), edges.end()); std::vector<int> comp(n); for (int i = 0; i<n; i++) comp[i] = i; int smt=0; for (auto&edge:edges) { int weight = edge[0]; int start= edge[1]; int end = edge[2]; if (comp[start] != comp[end]) { smt += weight; int a = comp[start]; int b = comp[end]; for (int i = 0; i<n; ++i) if (comp[i] == b) comp[i] = a; } } } int main() { ///Переменные----------------------------------------------------------------/// chrono::nanoseconds totalTime1st; totalTime1st=totalTime1st-totalTime1st; chrono::nanoseconds totalTime2; totalTime2=totalTime2-totalTime2; int times = 1000; int stepcount = 20; int size = 10; float *krask_av = new float[stepcount+1]; float *prim_av = new float[stepcount+1]; ///Ввод----------------------------------------------------------------------/// cout << "Rekomenduetsya vvodit chislo ot 1000\n"; cout << "vvedite kolichestvo povtornih zapuskov: "; cin >> times; ///Подсчет-------------------------------------------------------------------/// for (int i=1; i<=stepcount; i++) { size += k1; cout << "mtx size = " << size << endl; int **mtx3 = new int* [size]; for (int k = 0; k < size; k++) mtx3[k] = new int [size]; int edges = get_random_graph(mtx3, size); for (int j=1; j<=times; j++) { system_clock::time_point start = chrono::system_clock::now(); kruskal(size,edges,mtx3); system_clock::time_point end = chrono::system_clock::now(); chrono::nanoseconds elapsedSeconds = end-start; totalTime1st += elapsedSeconds; start = chrono::system_clock::now(); Prim(mtx3, size); end = chrono::system_clock::now(); elapsedSeconds = end-start; totalTime2 += elapsedSeconds; } totalTime1st/=(times); krask_av[i-1]=totalTime1st.count(); totalTime1st=totalTime1st-totalTime1st; totalTime2/=(times); prim_av[i-1]=totalTime2.count(); totalTime2=totalTime2-totalTime2; for (int k = 0; k < size; k++) delete [] mtx3[k]; } ///Вывод---------------------------------------------------------------------/// cout << "\tkruskal alg\tprim alg\n"; fstream fout ("rez.txt", ios::out); for (int i=1; i<=stepcount; i++) { printf("\t %7.2f \t %7.2f\n" , krask_av[i-1], prim_av[i-1]); fout << krask_av[i-1] << "\t" << prim_av[i-1] << endl; } fout.close(); delete [] krask_av; delete [] prim_av; getch(); return 0; }
Санкт-Петербург
2020