5. графи определение и основни понятия
Обхождане на граф в дълбочина
Изтегляне 0.63 Mb.
|
- Навигация на страницата:
- 5.5.1.Обхождане на граф в дълбочина с използване на стек
- 5.5.2.Обхождане на граф в дълбочина с използване на рекурсия
5.5.Обхождане на граф в дълбочинаТова обхождане обаче не е обхождане по нива. Напротив, всеки следващ преход е към един от непосетените съседите на върха, а той е от друго ниво. Преходът напред към следващ връх продължава до достигане до ситуация, когато върхът, в който се намираме, няма непосетени съседи, т.е. не можем да продължим напред. Това обаче в общия случай не означава, че са обходени всички върхове. Затова правим стъпка назад към предходния връх и, ако той няма непосетен съсед, пак правим стъпка назад към неговия предходен връх. Това връщане назад продължава, докато попаднем във връх с непосетен съсед. Тогава преминаваме в непосетения съсед и продължаваме напред по този нов клон, докато отново достигнем до невъзможност да продължим напред. Отново започваме връщане назад и т.н. Обхождането е завършило, когато се окаже, че, отстъпвайки назад, сме се върнали в началния връх и той няма нито един непосетен съсед. Има два алгоритъма за обхождане в дълбочина. 5.5.1.Обхождане на граф в дълбочина с използване на стекАлгоритъмът за обхождане в дълбочина с използване на стек се различава от този за обхождане в ширина по следното:
Обхождането в дълбочина с използване на стек става по следния алгоритъм: 1. Инициализираме елементите масива visit[] с нули, т.е. обявяваме върховете на графа за непосетени. 2. Изпращаме стартовия връх в стека. 3. Докато в стека има върхове, изпълняваме следното: 4. Вземаме от стека върховия елемент (върхът, изпратен в стека последен) и, ако той се окаже непосетен:
Очевидно, операция 4 от алгоритъма е цикъл с вложен цикъл. Добавянето към стека на съседите на взетия от стека връх е вложения. Нека да изпробваме този алгоритъм, за да обходим графа от фиг. 1а, като изберем за начален връх 2. 1. Създаваме масив visit[8] и инициализираме елементите му с нули. 2. Изпращаме началния връх 2 в стека. 3. Вземаме от стека стартовия връх. Tой не е посетен и затова: извеждаме 2 в списъка на обходените, регистрираме го като посетен (visit[2]=1), намираме от 2-ия ред на матрицата на съседство съседите му 0, 4 и 7 и ги добавяме към стека. 4. Вземаме от стека 7-ия връх. Tой не е посетен и затова: извеждаме 7 в списъка на обходените, регистрираме го като посетен (visit[7]=1), намираме от 7-ия ред на матрицата на съседство съседите му 0, 2 и 6 и ги добавяме към стека. 5. Вземаме от стека 6-ия връх. Tой не е посетен и затова: извеждаме 6 в списъка на обходените, регистрираме го като посетен (visit[6]=1), намираме от 6-ия ред на матрицата на съседство съседите му 1, 5 и 7 и ги добавяме към стека. 6. Вземаме от стека 7-ия връх. Tой е посетен и затова го отминаваме. 7. Вземаме от стека 5-ия връх. Tой не е посетен и затова: извеждаме 5 в списъка на обходените, регистрираме го като посетен (visit[5]=1), намираме от 5-ия ред на матрицата на съседство съседите му 1, 3, 4 и 6 и ги добавяме към стека. 8. Вземаме от стека 6-ия връх. Tой е посетен и затова го отминаваме. 9. Вземаме от стека 4-ия връх. Tой не е посетен и затова: извеждаме 4 в списъка на обходените, регистрираме го като посетен (visit[4]=1), намираме от 4-ия ред на матрицата на съседство съседите му 2, 3, и 5 и ги добавяме към стека. 10. Вземаме от стека 5-ия връх. Tой е посетен и затова го отминаваме. 11. Вземаме от стека 3-ия връх. Tой не е посетен и затова: извеждаме 3 в списъка на обходените, регистрираме го като посетен (visit[3]=1), намираме от 3-ия ред на матрицата на съседство съседите му 4 и 5 и ги добавяме към стека. 12. Вземаме от стека 5-ия връх. Tой е посетен и затова го отминаваме. 13. Вземаме от стека 4-ия връх. Tой е посетен и затова го отминаваме. 14. Вземаме от стека 3-ия връх. Tой е посетен и затова го отминаваме. 15. Вземаме от стека 2-ия връх. Tой е посетен и затова го отминаваме. 16. Вземаме от стека 3-ия връх. Tой е посетен и затова го отминаваме. 17. Вземаме от стека 1-ия връх. Tой не е посетен и затова: извеждаме 1 в списъка на обходените, регистрираме го като посетен (visit[1]=1), намираме от 3-ия ред на матрицата на съседство съседите му 5 и 6 и ги добавяме към стека. 18. Вземаме от стека 5-ия връх. Tой е посетен и затова го отминаваме. 19. Вземаме от стека 4-ия връх. Tой е посетен и затова го отминаваме. 20. Вземаме от стека 1-ия връх. Tой е посетен и затова го отминаваме. 21. Вземаме от стека 2-ия връх. Tой е посетен и затова го отминаваме. 22. Вземаме от стека 0-ия връх. Tой не е посетен и затова: извеждаме 0 в списъка на обходените, регистрираме го като посетен (visit[0]=1), намираме от 0-ия ред на матрицата на съседство съседите му 2 и 7 и ги добавяме към стека. 23. Вземаме от стека 7-ия връх. Tой е посетен и затова го отминаваме. 24. Вземаме от стека 2-ия връх. Tой е посетен и затова го отминаваме. 25. Вземаме от стека 4-ия връх. Tой е посетен и затова го отминаваме. 26. Вземаме от стека 0-ия връх. Tой е посетен и затова го отминаваме. Стекът вече е празен. Обхождането в дълбочина е завършило. Следват две програми за обхождане на граф в дълбочина с използване на стек: програма за обхождане граф, представен чрез матрица на съседство и програма за обхождане граф, представен чрез масив от списъци на съседство. Обърнете внимание на това, че в отделни моменти броят на върховете в стека е по-голям от общия им брой. Затова броят на елементите на масива, ползван от стека, е два пъти по-голям от броя на върховете. Програма 5.7. Обхождане в дълбочина на граф, представен чрез матрица на съседство # include # include #include "graf_mat.h" //Член-функция за обхождане в дълбочина void clasGraph::DFS() { unsigned i,j,k,n,sv,*visit; if(!(visit=new unsigned[BrV])) exit(1); for (i=0; i cout<<"Стартов връх: "; cin>>sv;
cout<<"Обхождане в дълбочина от стартов връх "< Stek.DobEl(sv); //Добавяме към стека стартовия връх
while (Stek.Br){ //Докато в стекът има чакащи върхове, ... Stek.VzeEl(k); //... вземаме от стека върховия елемент, ...
if (visit[k]) continue;// и ако е обходен, отминаваме го, ... visit[k]=1; // ... маркираме го като обходен и ...
cout< // добавяме към стека всички негови съседи.
for (j=0;j if (A[k][j]&&!Stek.DobEl(j)){cout<<"\nСтекът е пълен!\n";getch();exit(1);}
}
delete []visit; void main() {
char ime_vh_fl[21]; 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.DFS(); //Обхожда графа в дълбочина
getch();
# include # include # include "graf_sp.h" //Функция за обхождане в дълбочина
void clasGraph::DFS() {
unsigned i,j,k,n,sv,*visit; for (i=0;i cout<<"Стартов връх: "; cin>>sv;
cout<<"Обхождане в дълбочина от стартов връх "< Stek.DobEl(sv);
while (Stek.Br>0) {//Докато в стека има чакащи върхове ... Stek.VzeEl(k);//... вземаме върховия елемент от стека, ...
if (visit[k]==1) continue; // ако е обходен, го отминаваме,... cout< visit[k]=1; //... маркираме го като обходен и ... rebro *p=a[k].first;
while (p){ //... изпращаме в стека съседите му. j=p->nom;
if (visit[j]==0) Stek.DobEl(j); p=p->next;
}
} void main() {
char ime_vh_fl[21]; 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.DFS(); cout< getch();
Ако обходим в дълбочина графа от фиг. 1а с тази програма, вземайки за стартов връх върха 2, ще получим следния ред на обхождане : 2, 0, 7, 6, 1, 5, 3, 4. Както се вижда двете програми предлагат различни редове на обхождане. Защо е така?
Ще покажем два варианта на програма за обхождане в дълбочина. #include #include "graf_mat.h"
unsigned *visit; //Рекурсивна член-функция за обхождане на граф в дълбочина
void clasGraph::DFS(unsigned i) {
unsigned j; cout< for (j=0;j fout< if (A[i][j] && !visit[j]) { DFS(j); fout<<'\n'< }
} {
char ime_vh_fl[21]; unsigned k,sv; 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);//Извежда матр. на съседство в т. файл if(!(visit=new unsigned[BrV])) exit(1);
for (k=0; k fout.open("DopInf",ios::ate);
cout<<"Стартов връх: "; cin>>sv;//Въвеждаме стартовия връх cout<<"Обхождане в дълбочина от стартов връх "< Graph.DFS(sv); fout.close();
cout<<"\nДопълнителна информация можете да намерите във файл \"DopInf.\"\n"; }
Програмата използва матрицата на съседство и масива visit, показващ във всеки момент от изпълнението на програмата кои върхове са посетени и кои не са. Главната функция се обръща към член-функцията DFS, като замества фиктивния аргумент i с номера на стартовия връх. Започва първото изпълнение на член-функцията DFS. Тя отбелязва стартовия връх, като посетен, извежда го на екрана (в списъка на обходените върхове) и започва да търси в i-ия ред на матрицата на съседство непосетен съсед на i-ия връх. Щом се намери такъв връх, функцията се обръща към себе си, като замества фиктивния аргумент i с номера j на намерения непосетен съседен връх.
Ф С това временно се спира първото изпълнението на DFS и започва новото изпълнение на рекурсивната функция. Отбелязва се i-ия връх (това i няма нищо общо с i-то от първото изпълнение на рекурсивната функция) като посетен, извежда се номерът му на екрана и започва търсене на негов непосетен съсед. Ако се намери такъв, следва ново обръщение към рекурсивната функция, но ако не се намери, следва излизане от изпълняваното в момента обръщение към DFS.
Т 0 0 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0
2 1 0 0 1 0 0 0 1 3 0 1 1 0 1 0 0 0
4 0 1 0 1 0 0 0 0 5 1 1 0 0 0 0 1 0
6 0 1 0 0 0 1 0 0 7 1 0 1 0 0 0 0 0
Матрица на съседство Следващата информация проследява реализираните обръщения към рекурсивната функция: 2 0 Търсене непосетен съсед на 2-ия. Такъв е 0-ия. Ново обръщение към рекурсивната функция.
0 0 1 2 3 4 5 Търсене непосетен съсед на 0-ия. Такъв е 5-ия. Ново обръщение към рекурсивната функция. 5 0 1 Търсене непосетен съсед на 5-ия. Такъв е 1-ия. Ново обръщение към рекурсивната функция.
1 0 1 2 3 Търсене непосетен съсед на 1-ия. Такъв е 3-ия. Ново обръщение към рекурсивната функция. 3 0 1 2 3 4 Търсене непосетен съсед на 3-ия. Такъв е 4-ия. Ново обръщение към рекурсивната функция.
4 0 1 2 3 4 5 6 7 Търсене непосетен съсед на 4-ия. Няма. Връщане от рекурсивната функция. 3 5 6 7 Търсене непосетен съсед на 3-ия. Няма. Връщане от рекурсивната функция.
1 4 5 6 Търсене непосетен съсед на 1-ия. Такъв е 6-ия. Ново обръщение към рекурсивната функция. 6 0 1 2 3 4 5 6 7 Търсене непосетен съсед на 6-ия. Няма. Връщане от рекурсивната функция.
1 7 Търсене непосетен съсед на 1-ия. Няма. Връщане от рекурсивната функция. 5 2 3 4 5 6 7 Търсене непосетен съсед на 5-ия. Няма. Връщане от рекурсивната функция.
0 6 7 Търсене непосетен съсед на 0-ия. Такъв е 7-ия. Ново обръщение към рекурсивната функция. 7 0 1 2 3 4 5 6 7 Търсене непосетен съсед на 7-ия. Няма. Връщане от рекурсивната функция.
0 Търсене непосетен съсед на 0-ия. Няма. Връщане от рекурсивната функция. 2 1 2 3 4 5 6 7 Търсене непосетен съсед на 2-ия. Няма. Връщане от рекурсивната функция.
Намерен ред на обхождане: 2, 0, 5, 1, 3, 4, 6, 7. # include # include # include "graf_sp.h" unsigned *visit;
//Функция за обхождане в дълбочина от даден врах void clasGraph::DFS(unsigned i)
{
unsigned j; cout< rebro *p=a[i].first;
while (p){ j=p->nom;
if (visit[j]) p=p->next; else DFS(j);
}
} {
char ime_vh_fl[21]; int sv; 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); cout<<"Стартов връх: "; cin>>sv;
cout<<"Обхождане в дълбочина от стартов връх "< if (!(visit=new unsigned[BrV])) exit(0);
for (int i=0;i Graph.DFS(sv); cout< }
Новата програма се различава от предходната само по това, че съседите на даден връх се търсят в масива от списъци на съседство, а не в матрицата на съседство. |
