Referat.me

Название: Способи зберігання графів. Пошук в графі

Вид работы: лабораторная работа

Рубрика: Информатика и программирование

Размер файла: 22.84 Kb

Скачать файл: referat.me-140298.docx

Краткое описание работы: Програмна робота з графами: операції їх зчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість. Основи пошуку в графі в різних напрямках. Розбиття множини вершин на класи еквівалентності за відношенням зв'язності графу.

Способи зберігання графів. Пошук в графі

Міністерство освіти і науки України

Житомирський державний технологічний університет

ФІКТ, Кафедра ПЗОТ, група ПІ-39

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

з дисципліни «Дискретна математика»

на тему: «Способи зберігання графів. Пошук в графі »

Виконала:

Перевірив:

Житомир2010

Завдання

зберігання граф програмний пошук

І. Подати на вхід.txt файл з матрицею суміжності.

1. Зчитування з файлу.

2. Обробка

А) Перевірка на:

– орієнтованості;

– симетричність;

Б) Формування матриці інциденцій.

ІІ. Забезпечити пошук в глибину і в ширину графа.

- Визначити зв’язність графу.

- Визначити розбиття вершин на класи еквівалентності за відношенням «зв’язність».

- На вхід подати матрицю суміжності графу.

Порядок виконання роботи

1. Складемо програму для виконання зчитування та обробки графів. Лістинг програми з відповідними коментарями наведено нижче.

Код програми:

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

#include <iostream.h>

#define m 10

int main (void){

clrscr();

int count,i,j,l=0,s=0,g=0,z;

int h=0;

int M[m][m];

int a[m][m];

int b[m][m];

FILE* file;

if ((file = fopen("matr.txt", "rt"))== NULL){

fprintf(stderr, "Cannot open input file.n");

return 1; }

cout<<"Matrytsay sumizhnosti: "<<endl;

fscanf(file,"%d",&count);

cout<<"Rozmir matrusti: "<<count<<"x"<<count;

for(i=0;i<count;i++){

cout<<endl;

cout<<"ttt";

for(j=0;j<count;j++)

{

fscanf(file,"%d",&M[i][j]);

cout<<M[i][j]<<" ";

}

}

int k=0;

for(i=0;i<count;i++)

for(j=0;j<count;j++)

if(M[i][j]!=M[j][i])

k=1;

if(k!=1)

cout<<"nGraf ne orientovanuy." ;

else

cout<<"nGraf orientovanuy.";

//----------------------

if (k==1){

for(i=0;i<count;i++)

for(j=0;j<count;j++)

if(M[i][j]==1)

l++;

for(i=0;i<count;i++)

for(j=0;j<l;j++)

a[i][j]=0;

cout<<endl<<endl;

l=0;

for(i=0;i<count;i++)

for(j=0;j<count;j++)

if(M[i][j]==1){

l++;

if(i==j)

a[i][j]=2;

else{

a[i][l-1]=-1;

a[j][l-1]=1;

}

}

cout<<"Matrica incudentnosti: n";

for(i=0;i<count;i++){

cout<<endl;

for(j=0;j<l;j++)

cout<<a[i][j]<<"t";

}

}

if (k!=1){

for(i=0;i<1;i++)

for(j=0;j<count;j++)

if(M[i][j]==1)

s++;

for(i=1;i<count;i++)

for(j=i+1;j<count;j++)

if(M[i][j]==1)

g++;

s=g+s;

cout<<"ns="<<s;

for(i=0;i<count;i++)

for(j=0;j<s;j++)

b[i][j]=0;

cout<<endl<<endl;

z=s;

s=0;

for(i=0;i<count;i++)

for(j=i;j<count;j++)

if(M[i][j]==1){

s++;

b[i][s-1]=1;

b[j][s-1]=1;

}

cout<<"Matrica incudentnosti";

for(i=0;i<count;i++){

cout<<endl;

for(j=0;j<z;j++)

cout<<b[i][j]<<"t";

}

}

//--------------------------------------------------------------------

cout<<"nnSpuski sumiznosti:"<<endl;

for(i=0; i<count; i++){

cout<<i+1<<": ";

for(j=0; j<count; j++){

if(M[i][j]==1){

cout<<j+1<<" ";}

}

cout<<endl;

}

getch();

return 0;}

2. Складемо програму для виконання пошуку в графі, визначення його зв’язності та розбиття. Лістинг програми з відповідними коментарями наведено нижче.

Код програми:

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

#include<iostream.h>

typedef struct list

{

int number;

struct list *next;

}list;

void Depth(int v);

void Width(int v,int n);

list* AddElem(list *last, int i,int j);

list **V;

int* NEW;

void main()

{

clrscr();

FILE *file;

int i,j,n,M[10][10],a,v,count=0 ;

if((file=fopen("input.txt","rb")) == NULL)

{

cout<<"nttttError open!!!";

getch();

exit(1); }

fscanf(file,"%d",&n);

for(i=0;i<n;i++)

*NEW=1;

list *end,*pel;

/* vydilenya pamyati dlya vkazivnykiv na spysky */

V= (list**)malloc(n * sizeof (list*));

for(i=0; i<n;i++)

V[i] = (list*)malloc(sizeof (list));

for(i=0;i<n;i++) // obnulennja pokazh4ukiv v kinci spusky

V[i]=NULL;

for(i=0;i<n;i++) //formuv spuskiv symizh

{

end=NULL;

for(j=0;j<n;j++)

{

fscanf(file,"%d",&a);

M[i][j]=a;

if(a==1)

{

end=AddElem(end,i,j);

}

}

}

cout<<"Depth search:";

for(i=0;i<n;i++)

{

v=i;

pel=V[v];

while(pel!=NULL)

{

if(NEW[v])

{

count++;

Depth(v);

printf("nn");

}

pel=pel->next;

v=pel->number-1;

}

}

cout<<"Kilkist komponent zviaznosti:"<<count;

if(count>1)

cout<<"nGraf ne zvyaznyyn";

else

cout<<"nGraf zvyaznyyn";

cout<<"n-------------------------------n";

for(i=0;i<n;i++)

NEW[i]=1;

cout<<"nWidth search:";

count=0;

for(i=0;i<n;i++)

{

v=i;

pel=V[v];

while(pel!=NULL)

{

if(NEW[v])

{

count++;

Width(v,n);

cout<<"nn";

}

pel=pel->next;

v=pel->number-1;

}

}

cout<<"Kilkist komponent zvyaznosti:"<<count;

if(count>1)

cout<<"nGraf ne zvyaznyyn";

else

cout<<"nGraf zvyaznyyn";

cout<<"n-------------------------------nn";

cout<<"Spuski sumiznosti:"<<endl;

for(i=0; i<n; i++){

cout<<i+1<<": ";

for(j=0; j<n; j++){

if(M[i][j]==1){

cout<<j+1<<" ";}

}

cout<<endl;

}

getch();

}

list* AddElem(list *last,int i,int j)

{

list *pel;

pel=(list*)malloc(sizeof(list));

pel->number=j+1;

pel->next=NULL;

if(V[i]==NULL)

V[i]=pel;

else

last->next=pel;

return pel;

}

void Depth(int v)

{

int u;

list *pel=V[v];

cout<<v+1<<" ";

NEW[v]=0;

u=pel->number;

while(pel!=NULL)

{

if(NEW[u-1])

Depth(u-1);

pel=pel->next;

u=pel->number;

}

}

void Width(int v,int n)

{

int beg,end,*q,i,p,u;

list *pel;

q=(int*)malloc(n * sizeof(int));

for(i=0;i<n;i++)

q[i]=0;

beg=end=0;

q[end]=v;

end++;

NEW[v]=0;

while(beg!=end)

{

p=q[beg];

for(i=0;i<end;i++)

q[i]=q[i+1];

end--;

cout<<p+1<<" ";

pel=V[p];

u=pel->number;

while(pel!=NULL)

{

if(NEW[u-1])

{

q[end]=u-1;

end++;

NEW[u-1]=0;

}

pel=pel->next;

u=pel->number;

}}}

Висновок

Виконуючи дану лабораторну роботу я навчилась програмній роботі з графами, а саме операціям їх зчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість. Крім того, було освоєно основи пошуку в графі в двох напрямках: (в глибину і в ширину), а також визначено зв’язність графу, виконано розбиття множини вершин на класи еквівалентності за відношенням «зв’язність».

Похожие работы

  • Теорія множин. Операції над множинами та їх властивості

    Теоретичні основи теорії множин. Основні операції над множинами та їх властивості. Складання програми для обчислення результуючої множини за вихідним і спрощеним виразами. Виконання операцій над множинами, застосування їх властивостей, спрощення виразів.

  • Створення програми &quot;Шаховий кінь&quot;

    Створення програми "Шаховий кінь" в системі програмування Turbo Pascal. Генерування відповідно до заданих початкових кординат маршруту руху коня. Алгоритм задачі: початок, виведення зображення та пошук. Реалізація програми та демонтрація її роботи.

  • Системний аналіз складних систем управління

    Основні положення системного аналізу, його використання. Характеристика та основні ознаки складних систем. Використання теорії графів для структурного аналізу. Графова потокова модель технологічного комплексу. Виділення внутрішніх комплексів в ТК.

  • Система автоматизації проектних робіт конструкторсько-технологічного призначення

    Спосіб настроювання бібліотеки. Пояснення до основних понять бібліотеки компонентів Symbol Pin Numbers. Створення символу шляхом редагування існуючого елемента. Створення графіки символів і корпусів за допомогою редакторів Symbol і Pattern Editor.

  • Інформація та інформаційні процеси

    Інформація та інформаційні процеси, носії інформації, властивості, форми і способи її подання, кодування повідомлень. Інформаційні процеси: пошук, зберігання, збирання, опрацювання, подання, передавання, використання, захист та сучасні засоби зберігання.

  • Вибір методів та засобів технічного діагностування складних систем озброєння

    Методика обґрунтування раціональної сукупності методів і засобів технічного діагностування складних систем озброєння, що задовольняє задані вимоги до систем технічного діагностування в цілому. Пошук дефекту при мінімальних витратах на реалізацію методів.

  • Моделі і методи прийняття рішень

    Планування цілеспрямованих дій і прийняття рішень. Характеристика методу повного перебору - універсального методу вирішення оптимізаційних задач, якщо множина допустимих рішень обмежена. Експоненційна складність евристичного пошуку. Складність алгоритмів.

  • Пошук найкоротшого шляху на орієнтованому графі

    Програмна реалізація алгоритму пошуку найкоротшого шляху між двома будь-якими вершинами графа. Загальні відомості про графи. Особливості роботи в середовищі. Опис структури програми та програмних засобів. Схема програмної реалізації алгоритму Дейкстри.

  • Довідкова система по кримінальному праву

    Створення довідкової системи по зменшенню витрат часу на здобуття інформації по кримінальному праву. Розробка алгоритму основної програми на мові програмування Turbo Pascal з підключенням модуля СRT, якій відповідає за графіку і DOS та працює з файлами.

  • База даних по приватним підприємствам регіону

    Програма "Приватка" для збереження та перегляду всієї інформації, що стосується пошуку підприємства. Розробка алгоритму та програмування на мові Turbo Pascal. Формальна та неформальна постановка задачі. Структура зберігаючих даних. Вихідний код програми.