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.

C++C#
Python
  1. class dane(object):
  2.   def __init__(self, id, v, p):
  3.     self.odwiedzony = v
  4.     self.poprzednik = p
  5.     self.pre = -1
  6.     self.post = -1
  7.     self.id = id

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.

C++C#
Python
  1. def DFS(macierz, start):
  2.   tab = []
  3.   for i in range(0, len(macierz)):
  4.     tab.append(dane(i, False, -1))
  5.   p = 1
  6.   tab, p = odwiedzWezel(macierz, tab, start, p)
  7.   for i in range(0, len(macierz)):
  8.     if (not tab[i].odwiedzony):
  9.       tab, p = odwiedzWezel(macierz, tab, i, p)
  10.   return tab

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!

C++C#
Python
  1. def odwiedzWezel(macierz, tab, u, p):
  2.   tab[u].odwiedzony = True
  3.   tab[u].pre = p
  4.   p += 1
  5.   for i in range(0, len(macierz)):
  6.     if (macierz[u][i] > 0 and not tab[i].odwiedzony):
  7.       tab[i].poprzednik = u
  8.       tab, p = odwiedzWezel(macierz, tab, i, p)
  9.   tab[u].post = p
  10.   p += 1
  11.   return tab, p

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ę.

C++C#
Python
  1. def sortowanieTopologiczne(macierz):
  2.   tab = DFS(macierz, 0);
  3.   tab.sort(key=lambda x: x.post)
  4.   return tab

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.

C++C#
Python
  1.   tab.sort(key=lambda x: x.post)

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.

C++C#
Python
  1. n = int(input('Podaj ile węzłów ma graf\n n = '))
  2. print('Podaj elementy macierzy:')
  3. macierz = []
  4. for i in range(0, n):
  5.   tab = [int(x) for x in input().split()]
  6.   macierz.append(tab)
  7.  
  8. tab = sortowanieTopologiczne(macierz)
  9. for i in range(0, n):
  10.   print(tab[i].id, end=' ')