Отчет о лабораторной работе №5

Пензенский государственный университет

Кафедра "Информационно-вычислительные системы"

Отчет о лабораторной работе №5

по дисциплине «Теория алгоритмов»

Выполнили: ст-ты гр.20КП01

Поляков С.А. Козылов Ю.И.

Проверил: доцент каф. ИВС

Дрождин В.В.

1 Формулировка задачи

В ориентированном графе общего вида G с вершинами vi Î V (|V| ≤ 100) и дугами ek Î E (|E| ≤ 200) определите количество компонентов связности. Опре-деление: граф общего вида – это дерево, сеть, граф с циклами и граф с несколь-кими компонентами связности.

2 Техническое задание

2.1 Требования к программе

Граф вводится вручную с клавиатуры.

По результатам анализа графа Gпрограмма должна определить множество вершин, достижимых из корня за количество шагов, не превышающих k.

2.2 Порядок контроля и приёмки

Для контроля правильности работы программы необходимоввести данные и запустить программу на выполнение. По результатам анализа графа программа выдает сообщение с множеством вершин достижимых из корня за количество шагов, не превышающих k.Если результат совпадет с тестовыми данными, то это означает, что программа работает корректно.

3 Описание программы

3.1 Общие сведения

Программа разработана в средеMicrosoftVisualStudio 2019.Текст программы приведен в приложении А.

3.2 Функциональное назначение

Программа предназначена для анализа графа и принятия решения: вывода вершин достижимых из корня за количество шагов, не превышающих

Рисунок 1. Блок схема.

4 Программа и методика испытаний

При проверке работы программы получены результаты, приведенные в приложении Б, в которых заданные исходные данные и результатысовпадают. Таким образом, можно сделать вывод, что программа работает корректно.

5 Описание применения

После запуска программы на выполнениесистема запрашивает количество вершин, рёбер, а также запрашивает ввести вершины рёбер(см. Приложение Б).

Заключение

В ходе выполнения лабораторной работыразработано техническое задание на решение задачи, разработан алгоритм решения задачи,осуществляющий чтение описания неориентированного графаи его анализ, составлена и отлажена программа, и оформлена программная документация. Проведенные испытания показали, что программа работает корректно.

ТЕКСТ ПРОГРАММЫ

Приложение А

(обязательное)

#include <iostream>

using namespace std;

intmain()

{

int v, e;

cout<< "Введите количество вершин графа" <<endl;

cin>> v;

cout<< "Введите количество рёбер графа" <<endl;

cin>> e;

int m[v][v];

int z[v+1];

for (inti=0; i<v; i++)

{

for (int j=0; j<v; j++)

m[i][j]=0;

z[i]=0;

}

for (inti=0; i<e; i++)

{

int a, b;

cout<< "Введите первую вершину ребра " << i+1 <<endl;

cin>> a;

cout<< "Введите вторую вершину ребра " << i+1 <<endl;

cin>> b;

m[a-1][b-1]=1;

m[b-1][a-1]=1;

}

z[0]=1;

bool f = true;

int k = 0;

while (f)

{

for (inti=0; i<v; i++)

if (m[k][i]==1&&z[i]==0)

z[i]=1;

z[k]=2;

f = false;

for (inti=0; i<v; i++)

if (z[i]==1)

{

k=i;

f = true;

break;

}

for (inti=0; i<v; i++)

if (z[i] == 0)

{

cout<< "Граф не связанный" <<endl;

return 0;

}

z[0]=0;

z[1]=0;

k=0;

int s[v];

for (inti=0; i<v; i++)

{

s[i]=0;

for (int j=0; j<v; j++)

s[i] += m[i][j];

}

while (k>=0)

{

for (inti=z[k+1]+1;i<=v;i++)

{

if (i==v)

k--;

else if (i!=z[k]&&m[i][z[k]]==1&&s[i]>2)

{

f = true;

for (int j=0;j<k;j++)

if (z[j]==i)

{

f=false;

if (k-j>1&&z[j+1]<z[k])

{

for (int l=j; l<=k; l++)

cout<< z[l]+1 << " ";

cout<< z[j]+1 <<endl;

}

if (f)

{

z[++k]=i;

z[k+1]=-1;

break;

}

РЕЗУЛЬТАТЫ ИСПЫТАНИЙ

Приложение Б

(обязательное)

Рисунок