Обхождане на граф в ширина

5.4.Обхождане на граф в ширина

Обхождане в ширина става по нива. Стартовият връх е на нулево ниво. На първо ниво се намират всички съседи на стартовия връх. На второ ниво се намират всички необходени съседи на върховете от първо ниво и т.н. Нека да си поставим задачата да обходим в ширина графа от фиг. 1а, приемайки за стартов връх върха 2. Обхождането ще става по нива както следва:

0-во ниво - връх 2;

1-во ниво - върхове 0, 4, 7;

2-ро ниво - върхове 3, 5, 6;

3-то ниво - връх 1.

Или при обхождане в ширина на графа от фиг. 1а от стартов връх 2 върховете ще бъдат посетени в следната последователност: 2, 0, 4, 7, 3, 5, 6, 1, а при стартов връх 0: 0, 2, 7, 4, 6, 3, 5, 1. Препоръчваме на читателя да намери реда на обхождане, като избере за стартов всеки от върховете 1, 3, 4, 5, 6 и 7.

Върховете от едно ниво могат да се обходят в произволен ред, например коректен е и следният ред 2, 7, 4, 0, 6, 5, 3, 1. Обикновено върховете, съседи на даден връх, се обхождат в нарастващ ред на номерата им.

Видяхме, че не е трудно да обходим граф, представен графично. Нашата цел обаче е да напишем програма за обхождане на граф. Очевидно тази програма ще използва вътрешното представяне на графа, т.е. в случая матрицата на съседство. Само тя, обаче, не е достатъчна. Ще използваме още:

• 
  опашка, в която ще чакат реда си върховете, за да бъдат посетени;
  
• 
  масив, в който ще отбелязваме посетените върхове, ще го кръстим visit[].
  

1. Инициализираме елементите на масива visit[] с нули, т.е. обявяваме върховете на графа за непосетени.

2. Ползваме (извеждаме в списъка на обходените), маркираме като ползван (обходен) и изпращаме в опашката стартовия връх.

3. Докато в опашката има върхове, вземаме ги един по един. След всяко вземаме на връх от опашката, посещаваме един по един съседите му и с всеки непосетен преди това съсед правим следното:

• 
  ползваме го (извеждаме го в списъка на обходените);
  
• 
  маркираме го като посетен;
  
• 
  изпращаме го в опашката.
  

Нека да изпробваме този алгоритъм, за да обходим графа от фиг. 27 а), като изберем за начален връх 2.

1. Създаваме масив visit[8] и инициализираме елементите му с нули.

2. Ползваме (извеждаме в списъка на обходените) старъовия връх, маркираме го като посетен (visit[2]=1) и го изпращаме в опашката.

3. Вземаме от опашката стартовия връх 2 и от 2-ия ред на матрицата на съседство намираме съседите му (0, 4 и 7). От масива visit[] виждаме, че те не са посещавани и затова ги ползваме (извеждаме ги в списъка на обходените), маркираме ги като посетени (visit[0]=1, visit[4]=1 и visit[7]=1) и ги изпращаме в опашката.

4. Вземаме от опашката 0-ия връх и от 0-ия ред на матрицата на съседство намираме съседите му (2 и 7). От масива visit[] виждаме, че те вече са посещавани и затова ги отминаваме.

5. Вземаме от опашката 4-ия връх и от 4-ия ред на матрицата на съседство намираме съседите му (2, 3 и 5). От масива visit[] виждаме, че 3 и 5 не са посещавани и затова ги ползваме (извеждаме ги в списъка на обходените), маркираме ги като посетени (visit[3]=1 и visit[5]=1) и ги изпращаме в опашката.

6. Вземаме от опашката 7-ия връх и от 7-ия ред на матрицата на съседство намираме съседите му (0, 2 и 6). От масива visit[] виждаме, че само 6 не е посещаван и затова го ползваме (извеждаме го в списъка на обходените), маркираме го като посетен (visit[6]=1) и го изпращаме в опашката.

7. Вземаме от опашката 3-ия връх и от 3-ия ред на матрицата на съседство намираме съседите му (4 и 5). От масива visit[] виждаме, че те посещаван и затова ги отминаваме.

8. Вземаме от опашката 5-ия връх и от 5-ия ред на матрицата на съседство намираме съседите му (1, 3, 4 и 6). От масива visit[] виждаме, че само връх 1 не е посещаван и затова го ползваме (извеждаме го в списъка на обходените), маркираме го като посетен (visit[1]=1) и го изпращаме в опашката.

9. Вземаме от опашката 6-ия връх и от 6-ия ред на матрицата на съседство намираме съседите му (1, 5 и 7). От масива visit[] виждаме, че те са посещавани и затова ги отминаваме.

10. Вземаме от опашката 1-ия връх и от 1-ия ред на матрицата на съседство намираме съседите му ( 5 и 7). От масива visit[] виждаме, че те са посещавани и затова ги отминаваме.

Тук обхождането приключва, защото опашката е празна.

По този алгоритъм е създадена следващата програма. Както се вижда, тя ползва заглавния файл "graf_mat.h" и се състои от член-функцията BFS(Breadth-First-Search) на класа clasGraph и главна функция. Член-функцията реализира описания по-горе алгоритъм.

# include

#include "graf_mat.h"

//Член-функция за обхождане на граф в ширина

void clasGraph::BFS()

{

unsigned i,j,k,sv,*visit;

if(!(visit=new unsigned[BrV])) exit(1);

for (i=0; i

cout<<"Начален връх: "; cin>>sv;

cout<<"Обхождане в ширина от стартов връх "< ";

cout<

visit[sv]=1; //Маркираме стартовия връх като посетен

Opashka.DobEl(sv); //Добавяме стартовия елемент към опашката

while (Opashka.Br){ //Докато в опашката има чакащи върхове ...

Opashka.VzeEl(k);//... вземаме поредния чакащ връх.

for (j=0;j

if (A[k][j]&&!visit[j]){//... ако не е посетен (ползван):...

cout<

visit[j]=1; // - маркираме го и го изпращаме в опашката

if (!Opashka.DobEl(j)){cout<<"\nОпашката е пълна!\n";getch();exit(1);}

}

} delete []visit;

}
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);//Извежда матр. на съседство в текст. файл

Graph.BFS(); //Обхожда графа в ширина

getch();

}
Следващата програма реализира обхождане в ширина на граф, представен чрез масив от списъци на съседство. Тя се различава минимално от предходната и се надяваме, че читателят ще я разбере без допълнителен коментар. Ако се обходи същият граф (фиг.1а) с новата програма ще се получи следната последователност на обхождане: 2, 7, 4, 0, 5, 3, 6, 1. Тя са различава от последователността, която намира предходната програма, но също е вярна. Предоставяме на читателя да изясни причината.

Програма 5.6. Обхождане в ширина на граф, представен чрез масив от списъци на съседство

# include

# include

# include "graf_sp.h"

//Член-функция за обхождане в ширина

void clasGraph::BFS()

{

unsigned i,j,k,sv,*visit;

if (!(visit=new unsigned[BrV])) exit(0);

for (i=0;i

cout<<"Стартов връх: "; cin>>sv;

cout<<"Обхождане в ширина от стартов връх "< ";

cout<

visit[sv]=1; //Маркираме стартовия връх като посетен

Opashka.DobEl(sv); //Добавяме стартовия елемент към опашката

while (Opashka.Br) {//Докато в опашката има чакащи върхове ...

Opashka.VzeEl(k);//... вземаме поредния връх от опашката, ...

rebro *p=a[k].first;

//... и всеки негов съсед,...

while (p){

j=p->nom;

if (!visit[j]){//...ако не е посетен (ползван)

cout<

visit[j]=1; // - маркираме го и го изпращаме в опашката

Opashka.DobEl(j);// - изпращаме го в опашката

}

p=p->next;

}

}

}

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.make_graf(); //Запълва матр. на съседство

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

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

Graph.BFS(); //Обхожда графа в ширина

getch();

}

Изтегляне 0.63 Mb.

Сподели с приятели: