Strona główna » Algorytmy » Sortowanie » Sortowanie Topologiczne
 

Sortowanie Topologiczne

https://mattomatti.com/fs27

Wstęp

Sortowanie Topologiczne jest bardzo przydatnym algorytmem podczas analizy grafu. W codziennym życiu można go zastosować do listy zadań zależnych od siebie, aby odkryć w jakiej kolejności powinny zostać wykonane. Tego typu sortowanie opiera się na algorytmie przeszukiwania grafu w głąb DFS.

Algorytm

Na początku należy wczytać graf skierowany, a następnie wykonać na nim algorytm DFS. Kolejny krok polega na posortowaniu wierzchołków według przypisanych do nich wartości post. W ten sposób uzyskuje się listę wierzchołków posortowaną topologicznie. Oznacza to, że jeśli narysuje się wierzchołki obok siebie w takiej kolejności jak na liście to wszystkie strzałki na grafie będą skierowane w prawo.

Przykład

Dajmy na to, że mamy listę zadań do zrobienia. Jednak część zadań zależy od wykonania poprzednich czyli np. zadania B nie można wykonać przed zadaniem A. W tabelce zostały zebrane informacje dotyczące zadań i które poprzednie zadania muszą zostać wykonane, aby można je było wykonać:

ZadanieWymaga
A-
BA
C-
DA, B
EC, D, F
F-

Zadanie to można przedstawić przy pomocy grafu. Strzałka na grafie wskazuję w którą stronę przekazywana jest gotowość (tj. strzałka kończy się w zadaniu zależnym). Przykładowa organizacja wierzchołków wygląda następująco:

Zadania do wykonania

Na grafie panuje bałagan i ciężko odkryć, które zadanie wykonać jako pierwsze. Z tego powodu rozpoczynamy porządkowanie poprzez zastosowanie algorytmu DFS na grafie. Dokładny opis algorytmu można znaleźć tutaj. Poniżej zostały przedstawione znalezione wartości:

WierzchołekABCDEF
pre1357910
post24681211

Teraz należy posortować dane zgodnie z wartością post. Wtedy otrzymana kolejność to A, B, C, D, F, E. Zadanie E jest ostatnie, ponieważ wymaga wykonania zadania F i wszystkich poprzednich (nie widać tego bezpośrednio na grafie). Uoprządkowany graf przedstawia się następująco:

Wynik

Implementacja

Założenia

Program wczytuje od użytkownika graf jako macierz incydencji, która przechowuje informację o n wierzchołkach. Przykładowo graf przedstawiony w przykładzie zapisany jako macierz ma następującą reprezentację:

  1. 6
  2. 0   0   0   0   0   0
  3. 1   0   0   0   0   0
  4. 0   0   0   0   0   0
  5. 1   1   0   0   0   0
  6. 0   0   1   1   0   1
  7. 0   0   0   0   0   0

Część macierzy nie jest wykorzystana, ponieważ jest to graf skierowany.

DFS

Do przechowywania danych potrzebna jest struktura dane, która pozwala przechować id elementu, jego poprzednika, wartości pre i post oraz czy element był odwiedzony. Zwykle nie istnieje potrzeba przechowywania id, ale tablica będzie sortowana, więc niekoniecznie i-ty wierzchołek zostanie na i-tej pozycji.

  1. struct dane {
  2.   bool odwiedzony;
  3.   int poprzednik;
  4.   int pre;
  5.   int post;
  6.   int id;
  7. };

Funkcja DFS rozpoczyna przeszukiwanie w głąb grafu: najpierw tworzona jest tablica danych i wypełniona zostaje domyślnymi wartościami. Następnie rozpoczyna się odwiedzanie kolejnych, według porządku alfabetycznego, wierzchołków grafu. Wynikiem działa funkcji jest tablica wierzchołków z uzupełnionymi o nich informacjach.

  1. dane* DFS(int** macierz, int n, int start) {
  2.   dane* tab = new dane[n];
  3.   for (int i = 0; i < n; i++) {
  4.     tab[i].odwiedzony = false;
  5.     tab[i].poprzednik = -1;
  6.     tab[i].id = i;
  7.   }
  8.   int p = 1;
  9.   odwiedzWezel(macierz, n, tab, start, p);
  10.   for (int i = 0; i < n; i++)
  11.     if (!tab[i].odwiedzony)
  12.       odwiedzWezel(macierz, n, tab, i, p);
  13.   return tab;
  14. }

Proces odwiedzania wierzchołku polega na nadaniu mu wartości pre, a potem odwiedzeniu wszystkich nieodwiedzonych sąsiadów. Po zakończeniu odwiedzin należy pamiętać, aby nadać na koniec elementowi wartość post!

  1. void odwiedzWezel(int** macierz, int n, dane* tab, int u, int &p) {
  2.   tab[u].odwiedzony = true;
  3.   tab[u].pre = p;
  4.   p++;
  5.   for (int i = 0; i < n; i++) {
  6.     if (macierz[u][i] > 0 && !tab[i].odwiedzony) {
  7.       tab[i].poprzednik = u;
  8.       odwiedzWezel(macierz, n, tab, i, p); 
  9.     }
  10.   }
  11.   tab[u].post = p;
  12.   p++;
  13. }

Sortowanie

Teraz pozostaje napisać funkcję sortowania, która kolejno: (1.) zaakceptuje macierz grafu macierz i ilość wierzchołków n, a potem (2.) wykona na grafie algorytm DFS, (3.) posortuje dane i (4.) zwróci posortowaną tablicę.

  1. dane* sortowanieTopologiczne(int** macierz, int n) {
  2.   dane* tab = DFS(macierz, n, 0);
  3.   sort(tab, tab + n, porownaj);
  4.   return tab;
  5. }

Do sortowania została wbudowana w język funkcja do sortowania, ale należało dodać jak program ma porównać dwa elementy typu dane. Jako klucz została użyta wartość post porównywanych elementów.

  1. bool porownaj(dane a, dane b) {
  2.   return a.post < b.post;
  3. }

Testowanie funkcji

Poniższy kod wczyta od użytkownika potrzebne informacje, a następnie wypisze na ekran wynik czyli posortowane numery wierzchołków grafu.

  1. int main() {
  2.   int n;
  3.   cout << "Ile wierzcholkow ma graf?\n n = ";
  4.   cin >> n;
  5.   cout << "Podaj macierz:" << endl;
  6.   int** macierz = new int*[n];
  7.   for (int i = 0; i < n; i++) {
  8.     macierz[i] = new int[n];
  9.     for (int j = 0; j < n; j++)
  10.       cin >> macierz[i][j];
  11.   }
  12.   dane* tab = sortowanieTopologiczne(macierz, n);
  13.   for (int i = 0; i < n; i++)
  14.     cout << tab[i].id << " ";
  15.   system("pause");
  16.   return 0;
  17. }