Топологично сортиране на граф

5.6.Топологично сортиране на граф

Фиг. 33. Граф за илюстрация на топологично сортиране

Топологичен ред се получава по следния алгоритъм:

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

2. Един по един, в произволен ред записваме в топологичния ред върховете без предшественици и ги изтриваме.

3. Ако още има неизтрити върхове, премининаваме към операция 1, ако са изтрити всички, топологичното сортиране е завършило.

Нека да приложим този алгоритъм за графа от фиг. 33.

1. Без предшественици е връх 0. Записваме го в топологичния ред и го изтриваме.

2. Без предшественици е връх 1. Записваме го топологичния ред и го изтриваме.

3. Сега без предшественици са върхове 2 и 3. Записваме в топологичния ред и изтриваме първо връх 2 и след това връх 3, но можем да го направим и в обратен ред.

4. След изтриването на върхове 2 и 3, без предшественици остава връх 5. Записваме го в топологичния ред и го изтриваме.

5. Сега без предшественици е връх 4. Записваме го в топологичния ред и го изтриваме.

Всички върхове са изтрити. Един топологичен ред за този граф е: 0, 1, 2, 3, 5, 4. Графът е ацикличен.

Сега сменете посоката на ребро 3, 4 и се опитайте да намерите топологичен ред на променения граф.

Разгледаният алгоритъм е прост и ясен, но той не е компютърен алгоритъм.

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

Има друг по-добър алгоритъм. Той ползва масивите: visit[] за регистрация на посетените върхове и br_pred[] за текущия брой предшественици на всеки връх и брояча на посетените върхове br_visit.

Алгоритъмът се състои в следното:

1. Регистрират се всички върхове като непосетени.

2. Намира се входната степен (преброяват се предшествениците) на всеки връх.

3. Всички върхове без предшественици се изпращат в опашката на чакащите върхове.

4. Един по един се вземат чакащите върхове от опашката, извеждат се в топологичния ред, регистрират се като посетени, преброяват се като посетени, намалява се входната степен на всеки техен наследник, всички наследници, останали с входна степен 0, се изпращат в опашката. Това продължава докато в опашката има чакащи върхове. Когато опашката остане празна има две възможности:

• 
  посетени са всички върхове и топологичният ред е създаден;
  
• 
  посетени са само част от върховете – графът е цикличен и не се поддава на топологично сортиране.
  

# include

#include "graf_mat.h"
void clasGraph::top_sort()

{

unsigned i,j,k,n,

br_visit=0, // Брой на посетените върхове

*visit, // За масива, отчитащ посетеността на върховете

*br_pred; // За масива, отчитащ броя на предшествениците на всеки връх

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

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

for (i=0;i

//Намираме броя на предшествениците на всеки връх

//и изпращаме елементите без предшественици в опашката

for (j=0;j

for (i=0;i

if (br_pred[j]==0) Opashka.DobEl(j);

}

//Генериране на топологичен ред

cout<<"Топологичен ред: ";

while (Opashka.Br) { //Докато опашката не е празна,...

n=Opashka.Br;

for (i=0;i

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

cout<

visit[k]=1; //... маркираме го като посетен и...

br_visit++; //... го преброяваме, като посетен.

for (j=0;j

if (A[k][j]!=0 && visit[j]==0){ //На непосетените наследници на к-ия връх ...

br_pred[j]--; //... намаляваме входната степен и...

if (br_pred[j]==0) Opashka.DobEl(j); //ако стане 0, пращаме го в опашката

}

}

}

if (br_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.make_graf();

Graph.display_graf();

Graph.top_sort();

}
Програма 5.12. Топологично сортиране на граф, представен чрез масив от списъци на съседство

#include

#include

#include "graf_sp.h"

//Член-функция за топологичнo сортиране.

void clasGraph::top_sort()

{

unsigned i,j,k,n,br_visit=0,*br_pred, *visit; rebro* p;//br_visit - брой посетени

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

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

for (i=0;i

// Преброяване на предшествениците

for (i=0;i

p=a[i].first;

while (p) {

j=p->nom;

br_pred[j]++;//br_pred[j] е брой на предшествениците на j-ия връх.

p=p->next;

}

}

//Изпращаме в опашката всички елементи без предшественици

for (i=0;i

cout<<"Toпологичен ред: ";

// Докато опашката не е празна, вземаме връх, извеждаме го и намаляваме

//с 1 входната степен на всички негови непосредствени наследници. Щом обновената

//входна степен на някой наследник стане нула, изпращаме го в опашката

while (Opashka.Br) { //Докато опашката не е празна,...

n=Opashka.Br;

for (i=0;i

Opashka.VzeEl(j); //...вземаме връх oт опашката,...

cout<

br_visit++;

p=a[j].first;

while (p) {

k=p->nom; // k - номер на поредния наследник

if (visit[k]==0){

br_pred[k]--;//... намаляваме входната степен на този наследник,...

if (br_pred[k]==0) //...и ако тя стане 0,...

Opashka.DobEl(k);//...изпрщаме го в опашката от върхове без предщественици...

}

p=p->next;

}

}

}

if (br_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.make_graf();

Graph.display_graf();

Graph.top_sort(); cout<

}

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

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

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