Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна робота 6 Дискретна математика
Інформація про навчальний заклад
ВУЗ:
Вінницькій національний технічний університет
Інститут:
О
Факультет:
СІ
Кафедра:
КН
Інформація про роботу
Рік:
2016
Тип роботи:
Лабораторна робота
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Вінницький національний технічний університет
Кафедра КН
Лабораторна робота №6
з дисципліни: «Дискретна математика»
На тему:
« Побудова стовбура графа»
Виконали:
ст. гр. 2КН – 15б
Ільченко О. В.
Ваховський В. М.
Перевірила:
Ваховська Л. М.
Вінниця 2016
Мета роботи: набути навичок побудови стовбура графа.
Завдання: розробити схему алгоритму побудови стовбура графа та розробити програму, яка реалізує даний алгоритм. Продемонструвати роботу програми на прикладі.
Завдання для виконання
Варіант 3
/
Варіант 7
/
Схема алгоритму
/
Рисунок 1 – Блок-схема алгоритму Прима
Результати роботи:
Варіант 7
/
/
Рисунок 2 – Результат роботи програми для алгоритму Прима
Варіант 3
/
/
Рисунок 3 – Результат роботи програми для алгоритму Прима
Висновок
Під час виконання лабораторної роботи було розроблено алгоритм Прима. Було розроблено програму для знаходження мінімальної ваги остову. Продемонстровано результати роботи програми.
Додаток 1. Інструкція користувача
Для запуску програми для знаходження мінімальної ваги остову необхідно запустити файл Source.exe.
Ввести матрицю де -1 означає вiдсутнiсть ребра, в iншому випадку його вагу.
Програма виведе найкоротший шлях та загальну вагу.
Додаток 2. Лістинги програми
#include <iostream>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <vector>
#pragma warning ( disable : 4996 )
using namespace std;
const int SIZE = 14;
const int INF = 1e9;
int a[SIZE][SIZE];
vector <int> pred(SIZE, -1), dist(SIZE, INF), used(SIZE, 0);
void skeleton();
void prima_algorithm();
void out_dist_array();
void out_min_skeleton(int cur);
int main()
{
setlocale(LC_ALL, "Russian");
freopen("Text.txt", "r", stdin);
cout << "Введiть матрицю розмiру " << SIZE << "x" << SIZE << ",\nде -1 означає вiдсутнiсть ребра, в iншому випадку його вагу:\n";
for (int i = 0; i < SIZE; i++)
{
for (int j = 0; j < SIZE; j++)
{
cin >> a[i][j];
cout << setw(3) << a[i][j] << " ";
if (a[i][j] == -1)
a[i][j] = INF;
}
cout << endl;
}
skeleton();
prima_algorithm();
}
void skeleton()
{
cout << "\nОстов\n\n";
bool used[SIZE] = { 0 };
for (int i = 0; i < SIZE; i++)
{
used[i] = true;
for (int j = i + 1; j < SIZE; j++)
{
if (a[i][j] != INF && !used[j])
{
used[j] = 1;
cout << "X" << i + 1 << " - X" << j + 1 << "\n";
}
}
}
}
void prima_algorithm()
{
cout << "\nЗнаходження мінімального остова. Алгоритм Пріма\n\n";
for (int i = 1; i <= SIZE; i++)
cout << setw(3) << i << "|";
dist[0] = 0;
cout << endl;
while (true)
{
out_dist_array();
int cur = -1, curd = INF;
for (int j = 0; j < SIZE; j++)
if (dist[j] < curd && !used[j])
{
cur = j;
curd = dist[j];
}
if (cur == -1)
break;
for (int j = 0; j < SIZE; j++)
if (dist[j] > a[cur][j] && !used[j])
{
dist[j] = a[cur][j];
pred[j] = cur;
}
used[cur] = true;
}
int price = 0;
for (int i = 0; i < SIZE; i++)
price += dist[i];
cout << "Мiнiмальна вага остову: " << price << endl;
for (int i = 0; i < SIZE; i++)
out_min_skeleton(i);
}
void out_dist_array()
{
for (int i = 0; i < SIZE; i++)
if (dist[i] == INF)
cout << "INF|";
else if (used[i])
cout << setw(3) << " |";
else
cout << setw(3) << dist[i] << "|";
cout << endl;
}
void out_min_skeleton(int cur)
{
if (pred[cur] == -1)
return;
cout << "X" << pred[cur] + 1 << " - " << "X" << cur + 1 << endl;
}
03.10.2018 00:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора