Способи зберігання графів. Пошук в графі
Міністерство освіти і науки України
Житомирський державний технологічний університет
ФІКТ, Кафедра ПЗОТ, група ПІ-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<<"\t\t\t";
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<<"\n\nSpuski 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<<"\n\t\t\t\tError 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("\n\n");
}
pel=pel->next;
v=pel->number-1;
}
}
cout<<"Kilkist komponent zviaznosti:"<<count;
if(count>1)
cout<<"\nGraf ne zvyaznyy\n";
else
cout<<"\nGraf zvyaznyy\n";
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<<"\n\n";
}
pel=pel->next;
v=pel->number-1;
}
}
cout<<"Kilkist komponent zvyaznosti:"<<count;
if(count>1)
cout<<"\nGraf ne zvyaznyy\n";
else
cout<<"\nGraf zvyaznyy\n";
cout<<"\n-------------------------------\n\n";
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;
}}}
Висновок
Виконуючи дану лабораторну роботу я навчилась програмній роботі з графами, а саме операціям їх зчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість. Крім того, було освоєно основи пошуку в графі в двох напрямках: (в глибину і в ширину), а також визначено зв’язність графу, виконано розбиття множини вершин на класи еквівалентності за відношенням «зв’язність».