Способи зберігання графів. Пошук в графі
СОДЕРЖАНИЕ: Програмна робота з графами: операції їх зчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість. Основи пошуку в графі в різних напрямках. Розбиття множини вершин на класи еквівалентності за відношенням звязності графу.Міністерство освіти і науки України
Житомирський державний технологічний університет
ФІКТ, Кафедра ПЗОТ, група ПІ-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; }
coutMatrytsay sumizhnosti: endl;
fscanf(file,%d,count);
coutRozmir matrusti: countxcount;
for(i=0;icount;i++){
coutendl;
cout\t\t\t;
for(j=0;jcount;j++)
{
fscanf(file,%d,M[i][j]);
coutM[i][j] ;
}
}
int k=0;
for(i=0;icount;i++)
for(j=0;jcount;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;icount;i++)
for(j=0;jcount;j++)
if(M[i][j]==1)
l++;
for(i=0;icount;i++)
for(j=0;jl;j++)
a[i][j]=0;
coutendlendl;
l=0;
for(i=0;icount;i++)
for(j=0;jcount;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;
}
}
coutMatrica incudentnosti: \n;
for(i=0;icount;i++){
coutendl;
for(j=0;jl;j++)
couta[i][j]\t;
}
}
if (k!=1){
for(i=0;i1;i++)
for(j=0;jcount;j++)
if(M[i][j]==1)
s++;
for(i=1;icount;i++)
for(j=i+1;jcount;j++)
if(M[i][j]==1)
g++;
s=g+s;
cout\ns=s;
for(i=0;icount;i++)
for(j=0;js;j++)
b[i][j]=0;
coutendlendl;
z=s;
s=0;
for(i=0;icount;i++)
for(j=i;jcount;j++)
if(M[i][j]==1){
s++;
b[i][s-1]=1;
b[j][s-1]=1;
}
coutMatrica incudentnosti;
for(i=0;icount;i++){
coutendl;
for(j=0;jz;j++)
coutb[i][j]\t;
}
}
//--------------------------------------------------------------------
cout\n\nSpuski sumiznosti:endl;
for(i=0; icount; i++){
couti+1: ;
for(j=0; jcount; j++){
if(M[i][j]==1){
coutj+1 ;}
}
coutendl;
}
getch();
return 0;}
2. Складемо програму для виконання пошуку в графі, визначення його зв’язності та розбиття. Лістинг програми з відповідними коментарями наведено нижче.
Код програми:
#includestdio.h
#includeconio.h
#includestdlib.h
#includestring.h
#includeiostream.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;in;i++)
*NEW=1;
list *end,*pel;
/* vydilenya pamyati dlya vkazivnykiv na spysky */
V= (list**)malloc(n * sizeof (list*));
for(i=0; in;i++)
V[i] = (list*)malloc(sizeof (list));
for(i=0;in;i++) // obnulennja pokazh4ukiv v kinci spusky
V[i]=NULL;
for(i=0;in;i++) //formuv spuskiv symizh
{
end=NULL;
for(j=0;jn;j++)
{
fscanf(file,%d,a);
M[i][j]=a;
if(a==1)
{
end=AddElem(end,i,j);
}
}
}
coutDepth search:;
for(i=0;in;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;
}
}
coutKilkist komponent zviaznosti:count;
if(count1)
cout\nGraf ne zvyaznyy\n;
else
cout\nGraf zvyaznyy\n;
cout\n-------------------------------\n;
for(i=0;in;i++)
NEW[i]=1;
cout\nWidth search:;
count=0;
for(i=0;in;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;
}
}
coutKilkist komponent zvyaznosti:count;
if(count1)
cout\nGraf ne zvyaznyy\n;
else
cout\nGraf zvyaznyy\n;
cout\n-------------------------------\n\n;
coutSpuski sumiznosti:endl;
for(i=0; in; i++){
couti+1: ;
for(j=0; jn; j++){
if(M[i][j]==1){
coutj+1 ;}
}
coutendl;
}
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];
coutv+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;in;i++)
q[i]=0;
beg=end=0;
q[end]=v;
end++;
NEW[v]=0;
while(beg!=end)
{
p=q[beg];
for(i=0;iend;i++)
q[i]=q[i+1];
end--;
coutp+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;
}}}
Висновок
Виконуючи дану лабораторну роботу я навчилась програмній роботі з графами, а саме операціям їх зчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість. Крім того, було освоєно основи пошуку в графі в двох напрямках: (в глибину і в ширину), а також визначено зв’язність графу, виконано розбиття множини вершин на класи еквівалентності за відношенням «зв’язність».