Лабораторная работа: Способи зберігання графів. Пошук в графі
Название: Способи зберігання графів. Пошук в графі Раздел: Рефераты по информатике, программированию Тип: лабораторная работа |
Міністерство освіти і науки України Житомирський державний технологічний університет ФІКТ, Кафедра ПЗОТ, група ПІ-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; }}} Висновок Виконуючи дану лабораторну роботу я навчилась програмній роботі з графами, а саме операціям їх зчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість. Крім того, було освоєно основи пошуку в графі в двох напрямках: (в глибину і в ширину), а також визначено зв’язність графу, виконано розбиття множини вершин на класи еквівалентності за відношенням «зв’язність». |