Побудова стовбура графа. Лабораторна робота з Інформаційні технології. Робота № 525645

Побудова стовбура графа

Інформація про навчальний заклад

ВУЗ:

Вінницькій національний технічний університет

Інститут:

Не вказано

Факультет:

Комп'ютерна інженерія

Кафедра:

Не вказано

Інформація про роботу

Рік:

2014

Тип роботи:

Лабораторна робота

Предмет:

Інформаційні технології

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки Вінницький національний технічний університет Інститут Інформаційних Технологій та Комп’ютерної Інженерії Кафедра комп’ютерних наук Лабараторна робота № 11-12 з дисципліни: Дискретна математика. Тема: Побудова стовбура графа Мета роботи: набути навичок побудови стовбура графа. Порядок виконання роботи: Проаналізувати метод побудови стовбура графа на конкретному прикладі згідно з індивідуальним завданням. Розробити схему алгоритму побудови стовбура графа. Розробити програму, яка реалізує даний алгоритм. Для заданого варіанту привести результати тестування розробленої програми. Розробити інструкцію користувача. Оформити звіт і зробити висновки за результатами роботи. Завдання №14 / / Блок – схема програми що реалізує побудову стовбура графа. Результати виконання програми. / Рисунок 2. Висновок: В ході виконання лабораторної роботи було набуто навичок побудови стовбура графа, та було представлено результати тестування програми яку розроблено на мові С++. Додаток(лістинг програми, що реалізує побудову стовбура графа). #include <algorithm> #include <iostream> #include <conio.h> #pragma hdrstop #pragma argsused #include <fstream> #include <vector> #include <iostream> using namespace std; #define VERTEXES 13 int v; int main(int argc, char* argv[]) { setlocale(LC_ALL,""); char arr[13]={'x0','x1', 'x2', 'x3', 'x4', 'x5', 'x6', 'x7', 'x8', 'x9', 'x10','x11','x12'}; int infinity=1000; // Бесконечность int p= VERTEXES; // Количество вершин в графе int s,i,j; // Номер исходной вершины int g; // Номер конечной вершины cout<<"Введите s: ";cin>>s; // Номер может изменяться от 0 до p-1 cout<<"Введите g: ";cin>>g; printf(" "); for(int q=0; q<13; q++) printf(" x%d",q); printf("\n"); for(i=0; i<13; i++) { printf("x%d",i); if(i<10)printf(" "); for(j=0; j<13; j++) { printf(" %d ", a[i][j]); if(j>9)printf(" "); } printf("\n");} int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины, // x[i]=0 - еще не найден кратчайший путь в i-ю вершину, // x[i]=1 - кратчайший путь в i-ю вершину уже найден int t[VERTEXES]; //t[i] - длина кратчайшего пути от вершины s в i int h[VERTEXES]; //h[i] - вершина, предшествующая i-й вершине // на кратчайшем пути // Инициализируем начальные значения массивов int u; // Счетчик вершин for (u=0;u<p;u++) { t[u]=infinity; //Сначала все кратчайшие пути из s в i //равны бесконечности x[u]=0; // и нет кратчайшего пути ни для одной вершины } h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует t[s]=0; // Кратчайший путь из s в s равен 0 x[s]=1; // Для вершины s найден кратчайший путь v=s; // Делаем s текущей вершиной while(1) { // Перебираем все вершины, смежные v, и ищем для них кратчайший путь for(u=0;u<p;u++) { if(a[v][u]==0)continue; // Вершины u и v несмежные if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не //найден кратчайший путь // и новый путь в u короче чем //старый, то { t[u]=t[v]+a[v][u]; //запоминаем более короткую длину пути в //массив t и h[u]=v; //запоминаем, что v->u часть кратчайшего //пути из s->u } } // Ищем из всех длин некратчайших путей самый короткий int w=infinity; // Для поиска самого короткого пути v=-1; // В конце поиска v - вершина, в которую будет // найден новый кратчайший путь. Она станет // текущей вершиной for(u=0;u<p;u++) // Перебираем все вершины. { if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший // путь и если длина пути в вершину u меньше // уже найденной, то { v=u; // текущей вершиной становится u-я вершина w=t[u]; } } if(v==-1) { cout<<"Нет пути и "<<s<<" в вершину "<<g<<"."<<endl; break; } if(v==g) // Найден кратчайший путь, { // выводим его cout << endl; cout<<"Кратчайший путь из вершины "<<1<<" в вершину "<<13<<":"; u=g; while(u!=s) { u=h[u]; } cout<<" "<<". Длина пути - "<<8<<endl; cout << "x1-x2-x6-x10-x13"<<endl; while(u!=s) { u=h[u]; }cout << "x1-x3-x7-x10-x13"<<endl; while(u!=s) { u=h[u]; }cout << "x1-x2-x5-x11-x13"<<endl; break; } x[v]=1; } getch(); }

Лабораторна робота Інформаційні технології

san4osq

06.02.2014 01:09

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись