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

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

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

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

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

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

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

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

Виконала:

Перевірив:

Житомир 2010

Завдання

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

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

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

. Обробка

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

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

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

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

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

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

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

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

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

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

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

#include <iostream.h>

#define m 10main (void){();count,i,j,l=0,s=0,g=0,z;h=0;M[m][m];a[m][m];b[m][m];* file;((file = fopen("matr.txt", "rt"))== NULL){(stderr, "Cannot open input file.\n");1; }<<"Matrytsay sumizhnosti: "<<endl;(file,"%d",&count);<<"Rozmir matrusti: "<<count<<"x"<<count;(i=0;i<count;i++){<<endl;<<"\t\t\t";(j=0;j<count;j++)

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

}

}k=0;(i=0;i<count;i++)(j=0;j<count;j++)(M[i][j]!=M[j][i])=1;(k!=1)<<"\nGraf ne orientovanuy." ;<<"\nGraf orientovanuy.";

//----------------------(k==1){(i=0;i<count;i++)(j=0;j<count;j++)(M[i][j]==1)++;(i=0;i<count;i++)(j=0;j<l;j++)[i][j]=0;<<endl<<endl;=0;(i=0;i<count;i++)(j=0;j<count;j++)(M[i][j]==1){++;(i==j)[i][j]=2;{[i][l-1]=-1;[j][l-1]=1;

}

}<<"Matrica incudentnosti: \n";(i=0;i<count;i++){<<endl;(j=0;j<l;j++)<<a[i][j]<<"\t";

}

}(k!=1){(i=0;i<1;i++)(j=0;j<count;j++)(M[i][j]==1)++;(i=1;i<count;i++)(j=i+1;j<count;j++)(M[i][j]==1)++;=g+s;<<"\ns="<<s;(i=0;i<count;i++)(j=0;j<s;j++)[i][j]=0;<<endl<<endl;=s;=0;(i=0;i<count;i++)(j=i;j<count;j++)(M[i][j]==1){++;[i][s-1]=1;[j][s-1]=1;

}<<"Matrica incudentnosti";(i=0;i<count;i++){<<endl;(j=0;j<z;j++)<<b[i][j]<<"\t";

}

}

}<<endl;

}();0;}

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

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

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

#include<iostream.h>struct list

{number;list *next;

}list;Depth(int v);Width(int v,int n);* AddElem(list *last, int i,int j);**V;* NEW;main()

{();*file;i,j,n,M[10][10],a,v,count=0 ;((file=fopen("input.txt","rb")) == NULL)

{<<"\n\t\t\t\tError open!!!";();(1); }(file,"%d",&n);(i=0;i<n;i++)

*NEW=1;*end,*pel;

/* vydilenya pamyati dlya vkazivnykiv na spysky */= (list**)malloc(n * sizeof (list*));(i=0; i<n;i++)[i] = (list*)malloc(sizeof (list));(i=0;i<n;i++) // obnulennja pokazh4ukiv v kinci spusky[i]=NULL;(i=0;i<n;i++) //formuv spuskiv symizh

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

{(file,"%d",&a);[i][j]=a;(a==1)

{=AddElem(end,i,j);

}

}

{=i;=V[v];(pel!=NULL)

{(NEW[v])

{++;(v);("\n\n");

}=pel->next;=pel->number-1;

}

}<<"Kilkist komponent zviaznosti:"<<count;(count>1)<<"\nGraf ne zvyaznyy\n";<<"\nGraf zvyaznyy\n";<<"\n-------------------------------\n";(i=0;i<n;i++)[i]=1;<<"\nWidth search:";=0;(i=0;i<n;i++)

{=i;=V[v];(pel!=NULL)

{(NEW[v])

{++;(v,n);<<"\n\n";

}=pel->next;=pel->number-1;

}

}<<"Kilkist komponent zvyaznosti:"<<count;(count>1)<<"\nGraf ne zvyaznyy\n";<<"\nGraf zvyaznyy\n";<<"\n-------------------------------\n\n";<<"Spuski sumiznosti:"<<endl;(i=0; i<n; i++){<<i+1<<": ";(j=0; j<n; j++){(M[i][j]==1){<<j+1<<" ";}

}<<endl;

}();

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

{*pel;=(list*)malloc(sizeof(list));>number=j+1;>next=NULL;(V[i]==NULL)[i]=pel;>next=pel;pel;

}Depth(int v)

{u;*pel=V[v];<<v+1<<" ";[v]=0;=pel->number;(pel!=NULL)

{(NEW[u-1])(u-1);=pel->next;=pel->number;

}

{beg,end,*q,i,p,u;*pel;=(int*)malloc(n * sizeof(int));(i=0;i<n;i++)[i]=0;=end=0;[end]=v;++;[v]=0;(beg!=end)

{=q[beg];(i=0;i<end;i++)[i]=q[i+1];-;<<p+1<<" ";=V[p];=pel->number;(pel!=NULL)

{(NEW[u-1])

{[end]=u-1;++;[u-1]=0;

}=pel->next;=pel->number;

}}}

Висновок

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