Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
алгоритм Крускала
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2017
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
ЗВІТ
з лабораторної роботи № 8
з дисципліни: “Алгоритми та методи обчислень”
на тему: “ Множення матриць за алгоритмом Винограда ”
Львів - 2016
Мета роботи: навчитися застосовувати алгоритм Крускала для пошуку мінімального кістякового дерева
Теоретичні відомості:
Алгоритм Крускала — алгоритм побудови мінімального кістякового дерева зваженого неорієнтовного графа. Алгоритм було вперше описано Джозефом Крускалом1956 року
Візьмемо зважений зв'язний граф G=(V,E), де V — множина вершин, E — множина ребер, для кожного з яких задано вагу. Тоді ациклічна множина ребер, що поєднують усі вершини графа і чия загальна вага мінімальна, називається мінімальним каркасним (або кістяковим) деревом.
Алгоритм Крускала починається з побудови виродженого лісу, що містить V дерев, кожне з яких складається з однієї вершини. Далі виконуються операції об'єднання двох дерев, для чого використовуються найкоротші можливі ребра, поки не утвориться єдине дерево. Це дерево і буде мінімальним кістяковим деревом.
Завдання:
Застосувати алгоритм Крускала для пошуку мінімального кістякового дерева
Код програми
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
int main()
{
const int N = 7;
int flags[N] = {0};
int mass[N][N];
int n = 0;
ifstream file("matrix.txt", ios::in);
for (int i = 0; i<N; i++)
{
for (int j = 0; j<N; j++)
{
file >> mass[i][j];
}
}
for (int i = 0; i<N; i++)
{
for (int j = 0; j<N; j++)
{
cout << setw(4) << mass[i][j] << ' ';
}
cout << endl;
}
file.close();
int min = 100;
int mini, minj;
for (int i = 0; i<N; i++)
{
for (int j = 0; j<N; j++)
{
if (mass[i][j] < min)
{
min = mass[i][j];
mini = i;
minj = j;
}
}
}
cout << min << ' ' << minj << endl;
flags[mini] = min;
flags[minj] = min;
n = n + 2;
for (int j = 0; j<N; j++)
{
if (mass[mini][j] != min)
{
mass[mini][j] = 100;
}
}
for (int j = 0; j<N; j++)
{
mass[minj][j] = 100;
}
int mini2 = mini;
while (n != N)
{
int min2 = 100;
for (int i = 0; i<N; i++)
{
for (int j = 0; j<N; j++)
{
if (flags[j] != 0)
if (mass[i][j] < min2 && mass[i][j]>flags[j])
{
min2 = mass[i][j];
mini = i;
minj = j;
}
}
}
cout << min2 << ' ' << mini << endl;
n = n + 1;
for (int j = 0; j<N; j++)
{
if (mass[mini][j] != min2)
{
mass[mini][j] = 100;
}
}
flags[minj] = min2;
flags[mini] = 1;
for (int i = 0; i<N; i++)
{
for (int j = 0; j<N; j++)
{
cout << setw(4) << mass[i][j] << ' ';
}
cout << endl;
}
cout << endl;
for (int i = 0; i<N; i++)
{
for (int j = 0; j<N; j++)
{
if (mass[i][j] != 100)
cout << i + 1 << "--" << j + 1 << ' ' << "edge weight = " << mass[i][j];
}
cout << endl;
}
system("pause");
return 0;
}
Матриця суміжності(файл matrix.txt)
100
100
13
19
100
100
100
100
100
20
4
15
100
100
13
20
100
100
100
100
100
19
4
100
100
100
100
17
100
15
100
100
100
22
8
100
100
100
100
22
100
10
100
100
100
17
8
10
100
/
Рис.1 Результат виконання програми
Висновок: На даній лабораторній роботі я навчився реалізовувати множення матриць методом Винограда.
10.10.2017 22:31
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора