5. графи определение и основни понятия

Фиг. 30. Вътрешно представяне на граф чрез матрица на съседство

Елементите на матрицата показват дали съществуват ребра между отделните върхове или не съществуват. Например елементът, който се намира на i-ия ред и на j-ия стълб, има стойност 1 или 0 в зависимост от това, дали съществува реброто i,j или не. При тегловен граф стойността на елемент, представящ дадено ребро, е самото тегло, а не 1. Матрицата на съседство, представяща неориентиран граф, е симетрична, защото, ако съществува реброто i,j, съществува и реброто j,i . Елементите от главния диагонал са нулеви, ако графът не съдържа бримки.

Матрицата на съседство предлага определена прегледност. В i-ия ред, ненулеви са всички елементи, които се намират в стълбове, съответстващи на върхове, с които i-ият връх е свързан с изходящи ребра. В j-ия стълб, ненулеви са всички елементи, с които j-ият връх е свързан с входящи ребра Или броят на ненулевите елементи в i-ия ред дава изходящата степен на i-ия връх, а броят на ненулевите елементи в j-ия стълб дава входящата степен на j-ия връх.

Матрицата на съседство е много подходящ начин за представяне на граф от гледна точка на втория крирерий. От гледна точка на първия критерий (необходима памет), обаче, тя не е особено подходяща, защото граф с n върха изисква матрица с n² елемента, при това често преобладаващата част от тях са с нулеви стойности.

Програма 5.1. Програма за създаване и визуализация на матрицата на съседство на граф, представен външно в текстов файл

#include

#include

#include

#include

unsigned BrV; //Брой върхове в графа

ifstream fin; //Глобален входен поток за четене от текстовия файл

ofstream fout; //Глобален изходен поток за четене от текстов файл

//Клас граф

class clasGraph{

int **A; //Указател за създаване на матрицата на съседство

public:

clasGraph(); //Конструктор

~clasGraph(); //Деструктор

void make_graf(); //Запълва матрицата на съседство

void display_graf(ostream &);//Визуализира матрицата на съседство

};

//Конструктор за създаване и инициализация на матрицата на съседство

clasGraph::clasGraph()

{

int i,j;

if (!(A=new int*[BrV])) exit(1);

for (i=0; i

for (i=0; i

for (j=0; j

}

//Деструктор, който изтрива матрицата на съседство

clasGraph::~clasGraph()

{

for (int i=0; i

delete []A; cout<<"\nМатрицата на съседство е изтрита.\n";

}

//Член-функция за запълване на матрицата на съседство

void clasGraph::make_graf()

{

char kod_or,kod_teg; int i,j,teg;

cout<<"Графът ориентиран ли е /D,d,Д,д/? "; cin>>kod_or;

cout<<"Графът тегловен ли е /D,d,Д,д/? "; cin>>kod_teg;

for (;;) {

fin>>i>>j;if (fin.fail()) break;

if (kod_teg=='D'||kod_teg=='d'||kod_teg=='Д'||kod_teg=='д') fin>>teg;

else teg=1;

A[i][j]=teg;

if (kod_or!='D'&&kod_or!='d'&&kod_or!='Д'&&kod_or!='д') A[j][i]=teg;

}

fin.close();

}

//Член-функция за извеждане на матрицата на съседство на екрана или в //текстов файл

void clasGraph::display_graf(ostream &p=cout)

{

if (p!=cout) fout.open("DopInf",ios::out);

int i,j;

p<<"\n MATРИЦА НА СЪСЕДСТВО\n";

p<<" ";

for (i=0;i

for (i=0;i

p<

for (j=0;j

p<

}

if (p!=cout){

fout.close();

cout<<"\nОтрорете текст. файл DopInf.\n";

}

}

//Главна функция

void main()

{

char ime_vh_fl[21];

cout<<"\nИме на входния файл: "; cin>>ime_vh_fl;

fin.open(ime_vh_fl,ios::in);

if (fin.bad()) {cout<<"Няма такъв файл.\n";getch();return;}

fin>>BrV; //Въвежда от текстовия файл броя на върховете на графа

clasGraph Graph; //Създава обекта Graph

Graph.make_graf(); //Запълва матрицата на съседство

Graph.display_graf(); //Извежда матрицата на съседство на екрана

Graph.display_graf(fout);//Извежда матрицата на съседство в текстов //файл

getch();

}
Главната функция прочита броя на върховете BrV от текстовия файл.

Конструкторът на класа създава матрицата на съседство като двумерен динамичен масив с BrV реда и BrV стълба и инициализира всички елементи със стойност 0.

Член-функцията make_graf(), след два уточняващи въпроса (дали графът е ориентиран и дали е тегловен), прочита данните от файла външно представяне на графа и заменя част от нулите в матрицата с 1 или с теглата на съответните ребра.

Член-функцията display_graf(ostream &p=cout) извежда матрицата:

• 
  на екрана, когато фиктивният аргумент р не e заместен с действителен аргумент;
  
• 
  в текстов файл с име “DopInf”, когато фиктивният аргумент р е заместен с изходния поток fout.
  

Деструкторът изтрива матрицата непосредствено преди излизане от програмата.

Самата програма не се нуждае от по-подробно описание, защото е проста и достатъчно наситена с пояснителни текстове.

5.2.2.2.Вътрешно представяне чрез масив от списъци на съседство

На следващата фигура се показани списъците на съседство, представящи графите от фиг.27.а) и фиг.27.г) по два начина, отляво – както вече сме го предстсвяли в в гл. 3 и отдясно – както го визуализира член-функцията void display_graf(ostream &) от следващата програма.

П
ървоначално се създава масив от указатели към списъци, които се инициализират като празни. След това започва добавянето на възли в списъците. Всеки възел представя едно ребро, например възелът 7 в 0-вия списък представя реброто 0,7, а възелът 2 от същия списък – реброто 0,2. Списъците не са подредени, поради което всеки нов възел може да се представи на произволно място в съответния списък. С цел да се постигне по-голямо бързодействие на програмата, всеки нов възел се разполага в челото на съответния списък. Всяко ребро се описва само с номера на върха, до който то води или с номера на върха и теглото на реброто, когато графът е тегловен. Например i-ия списък има толкова елемента, колкото са ребрата, излизащи от i-ия връх.

Масив от списъци на съседство за графа от фиг.27.а)
М
асив от списъци на съседство за графа от фиг.27 г)

Фиг. 31. Вътрешно представяне на граф чрез масив от списъци на съседство.

При компютърната визуализация, числото в първата колона е индекс на елемент от масива от списъци и същевременно номер на върха, чиито съседи представя този списък-елемент на масива. Знакът -> е указател към ребро. Числото след знака -> е номер на върха-съсед.

Например редът 0 -> 7 -> 2 ->

съдържа информацията: върхът 0 има за съседи върховете 7 и 2.

А редът 5 -> 4 32 -> 3 10 ->

съдържа информацията: върхът 5 има за съседи върховете 4 и 3, като теглото на 5, 4 е 32, а на 5, 3 е 10.

Този начин за вътрешно представяне на граф е по-добър от гледна точка на първия критерий. Всеки списък на съседство съдържа точно толкова елемента, колкото е броят на изходящите от върха ребра.

По отношение на втория критерий има малък проблем, по-трудно се намират входящите съседи на върховете. Това обаче не е чак толкова голям проблем, защото, ако в програмата често се ползват входящите съседи, може да се създаде и масив от списъци на входящите съседи.

Програма 5.2. Програма за създаване и визуализация на масив от списъци на съседство на граф, представен външно в текстов файл

#include

#include

#include

#include

unsigned BrV; //Брой на върховете в графа

//Структура ребро.

struct rebro{int nom, teg; rebro *next;};

ifstream fin; //Глобален входен поток за четене от текстовия файл

ofstream fout; //Глобален изходен поток за четене от текст. файл

//Структура връх от графа

struct vrah { rebro *first; };

//Клас граф

class clasGraph {

vrah *a;//Указател, необходим за съсдаване на масива от списъци на съседство

public:

clasGraph(); //Конструктор за създаване и инициализация на масива от списъци

~clasGraph();//Деструктор за изтриване на граф

void make_graf();

void display_graf(ostream &);

};

// Конструктор за създаване и инициализация на масива от списъци на съседство

clasGraph::clasGraph()

{

a=new vrah[BrV];

for (int i=0;i

}

//Деструктор за изтриване на масива от списъци на съседство

clasGraph::~clasGraph()

{

rebro* p;

for (int i=0;i

while (a[i].first){

p=a[i].first;

a[i].first=p->next;

delete p;

}

}

delete []a; cout<<"Масивът от списъци е изтрит."<

}

char kod_teg;

//Член-функция за създаване списъците на съседство-елементи на масива

void clasGraph::make_graf()

{

rebro *p; char kod_or; unsigned i,j,teglo;

cout<<"Графът ориентиран ли е /D,d,Д,д/? "; cin>>kod_or;

if (kod_or=='D'||kod_or=='d'||kod_or=='Д'||kod_or=='д') kod_or=1;

else kod_or=0;

cout<<"Графът тегловен ли е /D,d,Д,д/? "; cin>>kod_teg;

if (kod_teg=='D'||kod_teg=='d'||kod_teg=='Д'||kod_teg=='д') kod_teg=1;

else kod_teg=0;

for (;;) {

fin>>i>>j; if (fin.fail()) break;

if (kod_teg) fin>>teglo;

else teglo=1;

p=new rebro; p->nom=j; p->teg=teglo; p->next=a[i].first; a[i].first=p;

if (!kod_or) {

p=new rebro; p->nom=i; p->teg=teglo; p->next=a[j].first; a[j].first=p;

}

}

fin.close ();

}

//Член-функция за визуализaция на масива от списъци на съседство

void clasGraph::display_graf(ostream &pp=cout)

{

if (pp!=cout) fout.open("DopInf",ios::out);

int i; rebro *p;

pp<<"\nМАСИВ ОТ СПИСЪЦИ НА СЪСЕДСТВО:\n";

for (i=0;i

pp< ";

p=a[i].first;

while (p!=0){

pp<nom; if (kod_teg) pp<teg; pp<<" -> ";

p=p->next;

} pp<

}

if (pp!=cout){

fout.close();

cout<<"\nОтрорете текст. файл DopInf.\n";

}

}

//Главна функция

void main()

{

char ime_vh_fl[21];

cout<<"\nИме на входния файл: "; cin>>ime_vh_fl;

fin.open(ime_vh_fl,ios::in);

if (fin.bad()) {cout<<"Няма такъв файл.\n";getch();return;}

fin>>BrV; //Въвеждаме от текстовия файл броя на върховете на графа

clasGraph Graph; //Създаваме обекта Graph

Graph.make_graf(); //Създаваме списъците на съседство

Graph.display_graf(fout); //Извеждаме на екрана масива от списъци на съседство

getch();

}

Главната програма прочита броя на върховете BrV от текстовия файл.

Конструкторът на класа създава динамичен масив от указатели с BrV елемента и инициализира всички указатели със стойност 0.

Член-функцията make_graf(), след два уточняващи въпроса дали графът е ориентиран и дали е тегловен, прочита данните от файла за външно представяне на графа и добавя към списъците на съседство елементи, съответстващи на изходящите съседни ребра.

Член-функцията display_graf(ostream &pp=cout) извежда масива от списъци:

• 
  на екрана, когато фиктивният аргумент р не e заместен с действителен аргумент;
  
• 
  в текстов файл с име “DopInf”, когато фиктивният аргумент р е заместен с изходния поток fout.
  

Деструкторът изтрива масива от списъци на съседство непосредствено преди излизане от програмата.

Самата програма не се нуждае от по-подробно описание, защото е проста и достатъчно наситена с пояснения.