Способи зберігання графів. Пошук в графі
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Міністерство освіти і науки України
Житомирський державний технологічний університет
ФІКТ, Кафедра ПЗОТ, група ПІ-39
Лабораторна робота
з дисципліни Дискретна математика
на тему: Способи зберігання графів. Пошук в графі
Виконала:
Перевірив:
Житомир 2010
Завдання
зберігання граф програмний пошук
І. Подати на вхід.txt файл з матрицею суміжності.
. Зчитування з файлу.
. Обробка
А) Перевірка на:
орієнтованості;
симетричність;
Б) Формування матриці інциденцій.
ІІ. Забезпечити пошук в глибину і в ширину графа.
Визначити звязність графу.
Визначити розбиття вершин на класи еквівалентності за відношенням звязність.
На вхід подати матрицю суміжності графу.
Порядок виконання роботи
1. Складемо програму для виконання зчитування та обробки графів. Лістинг програми з відповідними коментарями наведено нижче.
Код програми:
#include
#include
#include
#include
#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";
}
}
//--------------------------------------------------------------------<<"\n\nSpuski sumiznosti:"<<endl;(i=0; i<count; i++){<<i+1<<": ";(j=0; j<count; j++){(M[i][j]==1){<<j+1<<" ";}
}<<endl;
}();0;}
2. Складемо програму для виконання пошуку в графі, визначення його звязності та розбиття. Лістинг програми з відповідними коментарями наведено нижче.
Код програми:
#include
#include
#include
#include
#includestruct 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);
}
}
}<<"Depth search:";(i=0;i<n;i++)
{=i;=V[v];(pel!=NULL)
{(NEW[v])
{++;(v);("\n\n");
}=pel->next;=pel->number-1;
}
}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;
}
}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];number;(pel!=NULL)
{(NEW[u-1])(u-1);=pel->next;=pel->number;
}
}Width(int v,int n)
{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;inumber;(pel!=NULL)
{(NEW[u-1])
{[end]=u-1;++;[u-1]=0;
}=pel->next;=pel->number;
}}}
Висновок
Виконуючи дану лабораторну роботу я навчилась програмній роботі з графами, а саме операціям їх зчитування, збереження та обробки у вигляді перевірки на симетричність та орієнтованість. Крім того, було освоєно основи пошуку в графі в двох напрямках: (в глибину і в ширину), а також визначено звязність графу, виконано розбиття множини вершин на класи еквівалентності за відношенням звязність.