МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / ЗВІТ з лабораторної роботи № 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 Результат виконання програми Висновок: На даній лабораторній роботі я навчився реалізовувати множення матриць методом Винограда.