Міністерство освіти і наукиУкраїни
Житомирський державнийтехнологічний університет
ФІКТ, Кафедра ПЗОТ, група ПІ-39
Лабораторна робота
з дисципліни «Дискретнаматематика»
на тему: «Способи зберігання графів.Пошук в графі»
Виконала:
Перевірив:
Житомир 2010
Завдання
зберіганняграф програмний пошук
І. Подати на вхід.txtфайл з матрицею суміжності.
1. Зчитування зфайлу.
2. Обробка
А) Перевірка на:
– орієнтованості;
– симетричність;
Б) Формуванняматриці інциденцій.
ІІ. Забезпечитипошук в глибину і в ширину графа.
— Визначитизв’язність графу.
— Визначитирозбиття вершин на класи еквівалентності за відношенням «зв’язність».
— На вхід податиматрицю суміжності графу.
Порядоквиконання роботи
1. Складемопрограму для виконання зчитування та обробки графів. Лістинг програми звідповідними коментарями наведено нижче.
Код програми:
#include
#include
#include
#include
#define m 10
int main (void){
clrscr();
intcount,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
fscanf(file,“%d»,&count);
cout
for(i=0;i
cout
cout
for(j=0;j
{
fscanf(file,"%d",&M[i][j]);
cout
}
}
int k=0;
for(i=0;i
for(j=0;j
if(M[i][j]!=M[j][i])
k=1;
if(k!=1)
cout
else
cout
//----------------------
if (k==1){
for(i=0;i
for(j=0;j
if(M[i][j]==1)
l++;
for(i=0;i
for(j=0;j
a[i][j]=0;
cout
l=0;
for(i=0;i
for(j=0;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
for(i=0;i
cout
for(j=0;j
cout
}
}
if (k!=1){
for(i=0;i
for(j=0;j
if(M[i][j]==1)
s++;
for(i=1;i
for(j=i+1;j
if(M[i][j]==1)
g++;
s=g+s;
cout
for(i=0;i
for(j=0;j
b[i][j]=0;
cout
z=s;
s=0;
for(i=0;i
for(j=i;j
if(M[i][j]==1){
s++;
b[i][s-1]=1;
b[j][s-1]=1;
}
cout
for(i=0;i
cout
for(j=0;j
cout
}
}
//--------------------------------------------------------------------
cout
for(i=0;i
cout
for(j=0;j
if(M[i][j]==1){
cout
}
cout
}
getch();
return 0;}
2. Складемопрограму для виконання пошуку в графі, визначення його зв’язності та розбиття.Лістинг програми з відповідними коментарями наведено нижче.
Код програми:
#include
#include
#include
#include
#include
typedef structlist
{
int number;
struct list*next;
}list;
void Depth(intv);
void Width(intv,int n);
list*AddElem(list *last, int i,int j);
list **V;
int* NEW;
void main()
{
clrscr();
FILE *file;
inti,j,n,M[10][10],a,v,count=0 ;
if((file=fopen(«input.txt»,«rb»))== NULL)
{
cout
getch();
exit(1); }
fscanf(file,"%d",&n);
for(i=0;i
*NEW=1;
list *end,*pel;
/* vydilenyapamyati dlya vkazivnykiv na spysky */
V= (list**)malloc(n* sizeof (list*));
for(i=0;i
V[i] = (list*)malloc(sizeof(list));
for(i=0;i
V[i]=NULL;
for(i=0;i
{
end=NULL;
for(j=0;j
{
fscanf(file,"%d",&a);
M[i][j]=a;
if(a==1)
{
end=AddElem(end,i,j);
}
}
}
cout
for(i=0;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
if(count>1)
cout
else
cout
cout
for(i=0;i
NEW[i]=1;
cout
count=0;
for(i=0;i
{
v=i;
pel=V[v];
while(pel!=NULL)
{
if(NEW[v])
{
count++;
Width(v,n);
cout
}
pel=pel->next;
v=pel->number-1;
}
}
cout
if(count>1)
cout
else
cout
cout
cout
for(i=0; i
cout
for(j=0; j
if(M[i][j]==1){
cout
}
cout
}
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
NEW[v]=0;
u=pel->number;
while(pel!=NULL)
{
if(NEW[u-1])
Depth(u-1);
pel=pel->next;
u=pel->number;
}
}
void Width(intv,int n)
{
intbeg,end,*q,i,p,u;
list *pel;
q=(int*)malloc(n* sizeof(int));
for(i=0;i
q[i]=0;
beg=end=0;
q[end]=v;
end++;
NEW[v]=0;
while(beg!=end)
{
p=q[beg];
for(i=0;i
q[i]=q[i+1];
end--;
cout
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;
}}}
Висновок
Виконуючи данулабораторну роботу я навчилась програмній роботі з графами, а саме операціям їхзчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість.Крім того, було освоєно основи пошуку в графі в двох напрямках: (в глибину і вширину), а також визначено зв’язність графу, виконано розбиття множини вершинна класи еквівалентності за відношенням «зв’язність».