Намиране на всички прости пътища между два върха в безтегловен граф

5.8.Намиране на всички прости пътища между два върха в безтегловен граф

Нека да се опитаме да потърсим някои от тези пътища.

Т
0 1 2 5 4 6 8

0 1 2 5 6 8

0 1 2 5 7 8

0 1 2 5 8

0 1 4 5 6 8

0 1 4 5 7 8

0 1 4 5 8

ръгваме от началния връх 0. Можем да преминем във всеки от върховете 1, 2, 3 и 7. Избираме да преминем във връх 1, защото е с най-малък номер. От връх 1 можем да преминем във всеки от върховете 2, 4 и 5. Избираме да преминем във връх 2, защото е с най-малък номер. От връх 2 можем да преминем само във връх 5. От връх 5 можем да преминем във всеки от върховете 4, 6, 7 и 8. Избираме да преминем във връх 4, защото е с най-малък номер. От връх 4 преминаваме в 6, защото нямаме друга възможност. От връх 6 преминаваме в 8, защото отново нямаме друга възможност и с това е намерен първият прост път: 0, 1, 2, 5, 4, 6, 8.

За да намерим втори път, ще се върнем с една стъпка назад, т.е. във връх 6. Тъй като връх от 6 не може да се продължи по нов път към 8, ще се върнем с още една стъпка назад, т.е. във връх 4. И от връх 4 не можем да продължим по нов път към 8, затова ще се върнем с още една стъпка назад, т.е. във връх 5. От връх 5 можем да преминем във всеки от върховете 6, 7 и 8. Избираме да преминем във връх 6, защото е с най-малък номер. От връх 6 преминаваме във връх 8, защото нямаме друга възможност и с това е намерен вторият прост път: 0, 1, 2, 5, 6, 8.

За да намерим трети път, ще се върнем с една стъпка назад, т.е. във връх 6. Тъй като връх от 6 не може да се продължи по нов път към 8, ще се върнем с още една стъпка назад, т.е. във връх 5. От връх 5 можем да преминем само във връх 7 и 8. Избираме да преминем във връх 7, защото е с най-малък номер. От връх 7 преминаваме във връх 8, защото нямаме друга възможност, и с това е намерен третият прост път: 0, 1, 2, 5, 7, 8.

За да намерим четвърти път, ще се върнем с една стъпка назад, т.е. във връх 7. Тъй като връх от 7 не може да се продължи по нов път към 8, ще се върнем с още една стъпка назад, т.е. във връх 5. От връх 7 преминаваме във връх 8, защото нямаме друга възможност, и с това е намерен четвъртият прост път: 0, 1, 2, 5, 8.

От изложеното се разбира, че, за да създадем алгоритъм за намиране на всички прости пътища, трябва да променим алгоритъма за обхождане в дълбочина, като направим следните промени:

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

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

3. Ще регистрираме в масива path[] всеки връх, включен в поредния генериран път. За индекс на елементите на масива path[] ще ползваме нивото (nivo), на което се намира всеки от тях.

4. След всяко достигане до крайния връх, т.е. намиране на нов път, ще го извеждаме.

Програма 5.15. Намиране на всички прости пътища между два върха от граф, представен с матрица на съседство

#include

#include

#include

#include "graf_mat.h"

unsigned *visit,

*path; //Масив път, в който се регистрира намереният път

unsigned nivo; //Ниво, на което се намира посетеният връх, използва се за индекс

//на елементите от масива път

//Член-функция за намиране на всички прости пътища между върховете i и j

void clasGraph::vsiDFS(unsigned i, unsigned j)

{

unsigned k;

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

path[nivo++]=i;//Включване i-ия връх в масива път

for (k=0;k

if (A[i][k] && !visit[k]) vsiDFS(k,j); //След връщане от vsiDFS:

visit[i]=0; // отмяна маркировката на врърха, като посетен и...

nivo--; //... изключване на върха от масива път

return;

path[nivo]=i; //Записване на връх i като краен в масива път

for (k=0;k<=nivo;k++) cout<

cout<

}
void main()

{

char ime_vh_fl[21];unsigned i,k;

unsigned kv; //Краен връх при обхождането

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(); //Извеждаме на екрана матрицата на съседство

cout<

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

for (k=0;k

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

nivo=0;

cout<<"Краен връх:"; cin>>kv;

cout<<"Простите пътища между върховете "<

Graph.vsiDFS(nv,kv);

cout<

}

Програма 5.16. Намиране на всички прости пътища между два върха от граф, представен с масив от списъци на съседство

//Програма за намиране на всички прости пътища между два върха

#include

#include

#include

#include "graf_sp.h"

unsigned *visit,

*path; //Масив път, в който се регистрира намерения път

unsigned nivo; //Ниво, на което се намира посетения връх. Използва се //за индекс на елементите от масива път

//Член-функция за намиране на всички прости пътишта между върховете i и j

void clasGraph::vsiDFS(unsigned i, unsigned j)

{

unsigned k,m;

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

path[nivo++]=i; //Включване на i-ия връх в масива път

rebro *p=a[i].first;

while (p){

k=p->nom;

if (!visit[k]) vsiDFS(k,j);//След връщане от vsiDFS:

p=p->next;

}

visit[i]=0; // отмяна маркировката на врърха, като посетен и...

return;

path[nivo]=i; //Записване на връх i като краен в масива път

for (k=0;k<=nivo;k++) cout<

cout<

}
void main()

{

char ime_vh_fl[21];unsigned i,k;

unsigned kv; //Краен връх при обхождането

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(); //Извежда матрицата на съседство на екрана

cout<

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

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

nivo=0;

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

cout<<"Простите пътища между върховете "<

Graph.vsiDFS(nv,kv);

cout<

}