Sortowanie topologiczne



Pobieranie 38.04 Kb.
Data07.05.2016
Rozmiar38.04 Kb.

Sortowanie topologiczne


Sortowanie topologiczne digrafu polega na wygenerowaniu listy wierzchołków grafu w taki sposób, aby każdy wierzchołek posiadający sąsiadów znalazł się na tej liście przed nimi. Zadanie to jest możliwe do wykonania tylko wtedy, gdy graf nie posiada cykli. Kolejność wierzchołków niepołączonych ścieżką jest dowolna.

Metoda usuwania wierzchołków o stopniu wejściowym równym zero


Do posortowania topologicznego grafu wykorzystujemy własność, że jeśli graf jest acyklicznym grafem skierowanym, to musi posiadać przynajmniej jeden wierzchołek stopnia wejściowego zero.

Dopóki graf posiada wierzchołki o stopniu wejściowym zero, znajdujemy taki wierzchołek, usuwamy go z grafu wraz ze wszystkimi wychodzącymi z niego krawędziami i umieszczamy go na liście wierzchołków posortowanych topologicznie.

Jeśli w grafie pozostaną jakieś wierzchołki, to graf posiada cykle i sortowania topologicznego nie można wykonać.

Tworzymy tablicę indeg[ ] o tylu elementach, ile jest wierzchołków w grafie. Zerujemy wszystkie komórki tej tablicy. Następnie przechodzimy jednokrotnie przez poszczególne wierzchołki grafu. Dla każdego sąsiada u wierzchołka v grafu zwiększamy o 1 zawartość komórki indeg[u]. W efekcie w tablicy znajdzie się informacja o stopniach wejściowych wierzchołków.

Tworzymy pusty stos QS. Przeglądamy tablicę indeg[ ] i jeśli znajdziemy komórkę o wartości 0, to odpowiadający jej wierzchołek grafu umieszczamy na szczycie stosu QS.

W opisany powyżej sposób otrzymamy stos QS wszystkich wierzchołków grafu o stopniu wejściowym zero. Ze stosu QS będziemy pobierać wierzchołki do przesłania na wyjście do stosu wierzchołków uporządkowanych topologicznie. Każdy przesłany na wyjście wierzchołek powinien być zliczany - jeśli na końcu pracy algorytmu liczba wierzchołków posortowanych topologicznie będzie się różnić od liczby wierzchołków grafu, to graf nie był grafem acyklicznym.

Na stosie QS będziemy umieszczać wierzchołki, gdy po usunięciu krawędzi od wierzchołka v do u i zmniejszeniu indeg[u] o 1 okaże się, iż indeg[u] jest równe 0. Dzięki temu podejściu nie wystąpi potrzeba ponownego przeglądania grafu w poszukiwaniu wierzchołków o stopniu wejściowym zero.

Najlepszą metodą reprezentacji grafu dla omawianego algorytmu są listy sąsiedztwa. Algorytm działa w czasie liniowym O(n + m).



Dane wejściowe

n

-

liczba wierzchołków w grafie

L[ ]

-

n elementowa tablica list sąsiedztwa. Każdy element tablicy jest adresem listy wierzchołków. Element listy zawiera dwa pola:

next

- wskaźnik następnego elementu listy lub NULL

u

- numer wierzchołka grafu



Dane wyjściowe


nTS

-

liczba wierzchołków w tablicy-stosie TSS[ ] wierzchołków posortowanych topologicznie. Jeśli nTS jest mniejsze od n (lub nQ > 0), to graf nie jest acyklicznym grafem skierowanym i tablica TSS[ ] nie zawiera wszystkich jego wierzchołków - sortowanie topologiczne jest niewykonalne.

TSS[ ]

-

n elementowa tablica-stos zawierająca numery wierzchołków grafu w kolejności topologicznej. Indeksy od 0.

Dane pomocnicze


indeg[ ]

-

n elementowa tablica zawierająca stopnie poszczególnych wierzchołków w grafie

QS[ ]

-

n elementowy stos wierzchołków o stopniu wejściowym zero. Indeksy od 0.

nQ

-

liczba elementów na stosie QS[ ]

v

-

wierzchołek grafu

p

-

wskaźnik elementu listy wierzchołków

Lista kroków


K01:

Wyzeruj tablicę indeg[ ]

 

K02:

Dla v = 1, 2, ..., n: wykonuj kroki K03...K06

przechodzimy przez poszczególne wierzchołki w grafie

K03:

    p ← L[v]

p ustawiamy na pierwszy wierzchołek na liście

K04:

    Dopóki p ≠ NULL wykonuj kroki K05...K06

przechodzimy przez listę sąsiedztwa

K05:

        zwiększ o 1 indeg[p→u]

zwiększamy stopień wejściowy wierzchołka sąsiada

K06:

        p ← p→next

przechodzimy do następnego wierzchołka na liście sąsiedztwa

K07:

nQ ← 0

zerujemy stos QS[ ]

K08:

Dla v = 1, 2, ..., n: wykonuj kroki K09...K10

przechodzimy przez tablicę stopni wejściowych wierzchołków

K09:

    Jeśli indeg[v] ≠ 0, wykonaj następny obieg pętli K08

pomijamy wierzchołki o stopniu wejściowym różnym od zera

K10:

    QS[nQ] ← v;    nQ ← nQ + 1

umieszczamy wierzchołek v na stosie QS[ ]

K11:

nTS ← 0

zerujemy stos wierzchołków posortowanych topologicznie

K12:

Dopóki nQ > 0: wykonuj kroki K13...K20

dopóki w grafie są wierzchołki o stopniu wejściowym zero

K13:

    nQ ← nQ - 1;  v ← QS[nQ]

pobieramy numer takiego wierzchołka ze stosu QS[ ]

K14:

    p ← L[v]

rozpoczynamy od pierwszego wierzchołka na liście sąsiedztwa

K15

    Dopóki p ≠ NULL wykonuj kroki K16...K19

Dla każdego wierzchołka na liście sąsiedztwa

K16:

        Zmniejsz o 1 indeg[p→u]

usuwamy krawędź zmniejszając stopień wejściowy

K17:

        Jeśli indeg[p→u] > 0, idź do kroku K19

pomijamy wierzchołek o stopniu wejściowym większym od zera

K18:

        QS[nQ] ← p→u;    nQ ← nQ + 1

wierzchołek sąsiedni umieszczamy na stosie QS[ ]

K19:

        p ← p→next

przechodzimy do następnego wierzchołka na liście sąsiedztwa

K20:

    TSS[nTS] ← v;    nTS ← nTS + 1

wierzchołek v umieszczamy na stosie wierzchołków posortowanych

K21:

Zakończ

 

Program


Poniższy program wykorzystuje omawiany algorytm sortowania topologicznego do posortowania acyklicznego grafu skierowanego. Jeśli jest faktycznie acykliczny, to program wypisuje numery wierzchołków grafu posortowane topologicznie. Jeśli graf zawiera cykle, program wypisuje tekst NOT DAG. Graf zdefiniowany jest ciągiem liczb:

Pierwsza para liczb określa:

n - liczbę wierzchołków
m - liczbę krawędzi

Następne m par liczb u v określają wierzchołki grafu połączone krawędzią. Krawędź jest zawsze skierowana od wierzchołka u do v.


Przykładowe dane:


Acykliczny graf skierowany

Porządek topologiczny:
3 1 2 4 6 5

6 9
1 2
1 6
2 5
2 4
3 2
3 4
3 5
4 6
6 5
 

        

Cykliczny graf skierowany

Brak porządku topologicznego

6 10
1 2
1 6
2 5
2 4
3 2
3 4
3 5
4 6
6 5
6 3




#include
using namespace std;
struct TALelement

{

TALelement * next;



int u;

};
main()

{
int n,m;

cin >> n >> m;


TALelement * L[n + 1];

int indeg[n + 1];
for(int i = 1; i <= n; i++)

{

L[i] = NULL;



indeg[i] = 0;

}
for(int i = 1; i <= m; i++)

{

int u,v;

TALelement * p;

cin >> u >> v;

p = new TALelement;

p->next = L[u];

p->u = v;

L[u] = p;

indeg[v]++;

}
int nQ = 0, QS[n + 1];
for(int v = 1; v <= n; v++) if(!indeg[v]) QS[nQ++] = v;
int nTS = 0, TSS[n + 1];
while(nQ)

{

int v = QS[--nQ];

TALelement * p = L[v];

while(p)

{

if(!(--indeg[p->u])) QS[nQ++] = p->u;

p = p->next;

}

TSS[nTS++] = v;



}
if(nTS != n) cout << "Graf nie jest acykliczny";

else for(int i = 0; i < n; i++) cout << TSS[i] << " ";
cout << "\n\n";

system("pause");

}


6 9

1 2


1 6

2 5


2 4

3 2


3 4

3 5


4 6

6 5


3 1 2 4 6 5


6 10

1 2


1 6

2 5


2 4

3 2


3 4

3 5


4 6

6 5


6 3

Graf nie jest acykliczny










©absta.pl 2016
wyślij wiadomość

    Strona główna