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

Завдання

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

І. Подати на вхід.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++)