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

скачать (11.3 kb.)

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

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

ФІКТ, Кафедра ПЗОТ, група ПІ-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: "<

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

}

}k=0;(i=0;i

//----------------------(k==1){(i=0;i

}

}<<"Matrica incudentnosti: \n";(i=0;i

}

}(k!=1){(i=0;i<1;i++)(j=0;j

}<<"Matrica incudentnosti";(i=0;i

}

}

//--------------------------------------------------------------------<<"\n\nSpuski sumiznosti:"<

}<

}();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

*NEW=1;*end,*pel;

/* vydilenya pamyati dlya vkazivnykiv na spysky */= (list**)malloc(n * sizeof (list*));(i=0; i

{=NULL;(j=0;j

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

{=AddElem(end,i,j);

}

}

}<<"Depth search:";(i=0;i

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

{(NEW[v])

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

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

}

}<<"Kilkist komponent zviaznosti:"<1)<<"\nGraf ne zvyaznyy\n";<<"\nGraf zvyaznyy\n";<<"\n-------------------------------\n";(i=0;i

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

{(NEW[v])

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

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

}

}<<"Kilkist komponent zvyaznosti:"<1)<<"\nGraf ne zvyaznyy\n";<<"\nGraf zvyaznyy\n";<<"\n-------------------------------\n\n";<<"Spuski sumiznosti:"<

}<

}();

}* 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

{=q[beg];(i=0;inumber;(pel!=NULL)

{(NEW[u-1])

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

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

}}}

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


Рефераты Практические задания Лекции
Учебный контент

© ref.rushkolnik.ru
При копировании укажите ссылку.
обратиться к администрации