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

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

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

ФІКТ, Кафедра ПЗОТ, група ПІ-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;

}}}

Висновок

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