Algorytmy i Struktury Danych - Sortowanie topologiczne grafu

Do sortowania topologicznego grafu wykorzystamy własność, która mówi, że w acyklicznym grafie skierowanym musi wystąpić przynajmniej jeden wierzchołek o stopniu wchodzącym zero (czyli wierzchołek, który nie jest sąsiadem żadnego innego wierzchołka w grafie). Usunięcie wierzchołka z grafu nigdy nie powoduje, że staje się on grafem cyklicznym. Zatem po każdej operacji usunięcia wierzchołka w grafie pojawia się przynajmniej jeden wierzchołek o stopniu wchodzącym zero. Stąd mamy prosty algorytm sortowania topologicznego:

Z grafu usuwamy wierzchołki o stopniu wchodzącym zero dotąd, aż będzie on pusty lub nie znajdziemy wierzchołka o stopniu wchodzącym zero, co oznacza, że graf jest cykliczny i nie może być posortowany topologicznie. Usuwane wierzchołki tworzą listę wierzchołków grafu posortowanego topologicznie.

Aby zilustrować ten algorytm, prześledźmy operacje w poniższej tabelce:

	Wy:	Oto nasz graf do posortowania topologicznego.
	Wy:	Wyznaczamy stopnie wchodzące poszczególnych wierzchołków. Dwa wierzchołki mają stopień wchodzący równy zero: wierzchołek 3 i 5. Możemy usunąć dowolny z nich, ponieważ nie są one od siebie zależne.
	Wy: 3	Usuwamy z grafu wierzchołek nr 3 wraz z krawędziami i przesyłamy go na wyjście. Powoduje to zmianę stopni wchodzących wierzchołków sąsiednich. W grafie wciąż pozostał wierzchołek 5 o stopniu wejściowym zero.
	Wy: 3 5	Usuwamy z grafu wierzchołek 5 i przesyłamy go na wyjście. W grafie zmieniły się stopnie wchodzące wierzchołków sąsiednich. Teraz wierzchołek 4 ma stopień wchodzący równy zero.
	Wy: 3 5 4	Usuwamy z grafu wierzchołek 4 i przesyłamy go na wyjście. W wyniku usunięcia wierzchołka 4 wierzchołek 1 ma stopień wchodzący zero.
	Wy: 3 5 4 1	Usuwamy z grafu wierzchołek 1 i przesyłamy go na wyjście. Stopień wchodzący zero otrzymuje wierzchołek 0.
	Wy: 3 5 4 1 0	Usuwamy z grafu wierzchołek 0 i przesyłamy go na wyjście. W grafie pozostał tylko wierzchołek 2 i ma on teraz stopień wchodzący 0.
	Wy: 3 5 4 1 0 2	Usuwamy z grafu ostatni wierzchołek 2 i przesyłamy go na wyjście. Graf stał się grafem pustym i nie posiada już dalszych wierzchołków. Sortowanie topologiczne jest zakończone.

Algorytm sortowania topologicznego acyklicznego grafu skierowanego

Wejście:

n : liczba wierzchołków w grafie; n ∈ C.
graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

Ciąg wierzchołków posortowanych topologicznie. Jeśli graf jest cykliczny, to na wyjściu pojawi się mniej wierzchołków niż jest ich w grafie (wyprowadzane wierzchołki można zliczać i porównywać z n – otrzymamy w ten sposób algorytm badający przy okazji cykliczność grafu).

Elementy pomocnicze:

L : lista dwukierunkowa wierzchołków grafu.
Vind : tablica stopni wchodzących grafu.
u : wierzchołek; u ∈ C.
p, r : wskaźniki elementów listy L.
test : zmienna logiczna do testowania usunięć wierzchołków.

Lista kroków:

K01: Utwórz n elementową tablicę Vind
     i wyzeruj jej elementy
K02: Dla v = 0, 1, …, n-1:
     wykonuj krok K03
K03:   ; obliczamy stopnie wchodzące wierzchołków
       Dla każdego sąsiada u wierzchołka v:
       wykonuj: Vind[u] ← Vind[u]+1
K04: ; inicjujemy listę wierzchołków
     Umieść na liście L n elementów
     o wartościach od 0 do n-1
K05: test ← false ; zakładamy,
     ; że nie było usunięcia wierzchołka
K06: p ← L
K07: Dopóki p ≠ nil, ; przeglądamy wierzchołki
     wykonuj kroki K08…K14 ; na liście L
K08:   Jeśli Vind[p→v] > 0, ; wierzchołki
       to p ← p→next ; o niezerowym stopniu wchodzącym
       i następny obieg pętli K07 ; pomijamy
K09:   test ← true ; zaznaczamy,
       ; że jest usunięcie wierzchołka
K10:   ; obliczamy nowe stopnie wchodzące dla wszystkich
       ; sąsiadów usuwanego wierzchołka
       Dla każdego sąsiada u wierzchołka p→v:
       wykonuj: Vind[u] ← Vind[u]-1
K11:   Pisz p→v ; usuwany wierzchołek wyprowadzamy na wyjście
K12:   r ← p
K13:   p ← p→next
K14:   Usuń z L element ; a następnie usuwamy go z listy L
       wskazywany przez r
K15: Jeśli test = true, ; jeśli było usunięcie, to powtarzamy
     to idź do kroku K05
K16: Zakończ ; w przeciwnym razie kończymy

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje definicję grafu skierowanego, a następnie wypisuje w oknie konsoli ciąg wierzchołków grafu posortowanych topologicznie.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

Pascal

// Sortowanie topologiczne
// Data: 13.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program tsort;

// Typy danych
type
  PSLel = ^SLel;
  SLel =  record
    next : PSLel;
    v    : integer;
  end;

  PDLel = ^DLel;
  DLel =  record
    prev, next : PDLel;
    v : integer;
  end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  n, m, i, v1, v2 : integer;
  ps, rs : PSLel;
  pd, rd, L : PDLel;
  graf : array of PSLel;
  Vind : array of integer;
  test : boolean;

begin
  // Czytamy liczbę wierzchołków
  // i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(graf, n);
  for i := 0 to n-1 do
    graf[i] := nil;
  // Odczytujemy definicje
  // krawędzi grafu
  for i := 0 to m-1 do
  begin
    read(v1, v2);
    new(ps);
    ps^.v := v2;
    ps^.next := graf[v1];
    graf[v1] := ps;
  end;
  writeln;
  // Wykonujemy sortowanie
  // topologiczne grafu
  //----------------------
  // Tworzymy tablicę
  // stopni wchodzących
  SetLength(Vind, n);
  for i := 0 to n-1 do
    // Zerujemy tablicę Vind[]
    Vind[i] := 0;
  // Przeglądamy graf
  for i := 0 to n-1 do
  begin
    // Przeglądamy sąsiadów
    // każdego wierzchołka
    ps := graf[i];
    while ps <> nil do
    begin
      // Wyznaczamy ich
      // stopnie wchodzące
      inc(Vind[ps^.v]);
      // Następny sąsiad
      ps := ps^.next;
    end;
  end;
  L := nil;
  // Na liście L umieszczamy
  // od 0 do n-1
  for i := n-1 downto 0 do
  begin
    new(pd);
    pd^.v := i;
    pd^.next := L;
    if pd^.next <> nil then
      pd^.next^.prev := pd;
    pd^.prev := nil;
    L := pd;
  end;
  repeat
    // Oznaczamy brak
    // usunięcia wierzchołka
    test := false;
    // Przeglądamy listę L
    pd := L;
    while pd <> nil do
      // Wierzchołki o niezerowym
      // stopniu wchodzącym
      // pomijamy
      if Vind[pd^.v] > 0 then
        pd := pd^.next
      else
      begin
        // Będzie usunięcie
        // wierzchołka
        test := true;
        // Przeglądamy listę
        // sąsiadów
        ps := graf[pd^.v];
        while ps <> nil do
        begin
          // Modyfikujemy ich
          // stopnie wchodzące
          dec(Vind[ps^.v]);
          // Następny sąsiad
          ps := ps^.next;
        end;
        // Wypisujemy usuwany
        // wierzchołek
        write(pd^.v, ' ');
        // Zapamiętujemy adres
        // elementu L
        rd := pd;
        // Następny wierzchołek
        // na liście lub nil!
        pd := pd^.next;
        // Zapamiętany element rd
        // listy L usuwamy z pamięci
        if rd^.next <> nil then
          rd^.next^.prev := rd^.prev;
        if rd^.prev <> nil then
          rd^.prev^.next := rd^.next
        else L := pd;
        dispose(rd);
      end;
   until not test;
  writeln; writeln;
  // Usuwamy zmienne dynamiczne
  SetLength(Vind, 0);
  for i := 0 to n-1 do
  begin
    ps := graf[i];
    while ps <> nil do
    begin
      rs := ps;
      ps := ps^.next;
      dispose(rs);
    end;
  end;
  SetLength(graf, 0);
  pd := L;
  while pd <> nil do
  begin
    rd := pd;
    pd := pd^.next;
    dispose(rd);
  end;
end.

C++

// Sortowanie topologiczne
// Data: 13.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Typy danych
struct SLel
{
  SLel *next;
  int v;
};

struct DLel
{
  DLel *prev, *next;
  int v;
};

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n, m, i, v1, v2, *Vind;
  SLel *ps, *rs, **graf;
  DLel *pd, *rd, *L;
  bool test;

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy
  // tablice dynamiczne
  graf = new SLel * [n];
  for(i = 0; i < n; i++)
      graf[i] = nullptr;
  // Odczytujemy definicje
  // krawędzi grafu
  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    ps = new SLel;
    ps->v = v2;
    ps->next = graf[v1];
    graf[v1] = ps;
  }
  cout << endl;
  // Wykonujemy sortowanie
  // topologiczne grafu
  //----------------------
  // Tworzymy tablicę
  // stopni wchodzących
  Vind = new int [n];
  // Zerujemy tablicę Vind[]
  for(i = 0; i < n; i++)
    Vind[i] = 0;
  // Przeglądamy graf
  for(i = 0; i < n; i++)
    // Przeglądamy sąsiadów
    // każdego wierzchołka
    for(ps = graf[i];ps;ps = ps->next)
      // Wyznaczamy
      // ich stopnie wchodzące
      Vind[ps->v]++;
  L = nullptr;
  // Na liście L umieszczamy
  // od 0 do n-1
  for(i = n-1; i >= 0; i--)
  {
    pd = new DLel;
    pd->v = i;
    pd->next = L;
    if(pd->next)
      pd->next->prev = pd;
    pd->prev = nullptr;
    L = pd;
  }
  do
  {
    // Oznaczamy brak
    // usunięcia wierzchołka
    test = false;
    // Przeglądamy listę L
    pd = L;
    while(pd)
      // Wierzchołki o niezerowym
      // stopniu wchodzącym pomijamy
      if(Vind[pd->v])
        pd = pd->next;
      else
      {
        // Będzie usunięcie wierzchołka
        test = true;
        // Przeglądamy listę sąsiadów
        for(ps = graf[pd->v];ps;ps = ps->next)
          // Modyfikujemy
          // ich stopnie wchodzące
          Vind[ps->v]--;
        // Wypisujemy usuwany wierzchołek
        cout << pd->v << " ";
        // Zapamiętujemy adres elementu L
        rd = pd;
        // Następny wierzchołek
        // na liście lub NULL!
        pd = pd->next;
        // Zapamiętany element rd
        // listy L usuwamy z pamięci
        if(rd->next)
          rd->next->prev = rd->prev;
        if(rd->prev)
          rd->prev->next = rd->next;
        else
          L = pd;
        delete rd;
      }
  } while(test);
  cout << endl << endl;
  // Usuwamy zmienne dynamiczne
  delete [] Vind;
  for(i = 0; i < n; i++)
  {
    ps = graf[i];
    while(ps)
    {
      rs = ps;
      ps = ps->next;
      delete rs;
    }
  }
  delete [] graf;
  pd = L;
  while(pd)
  {
    rd = pd;
    pd = pd->next;
    delete rd;
  }
  return 0;
}

Basic

' Sortowanie topologiczne
' Data: 13.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy danych
Type SLel
  Dim As SLel Ptr next
  Dim As Integer v
End Type

Type DLel
  Dim As DLel Ptr prev, next
  Dim As Integer v
End Type

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer n, m, i, v1, v2
Dim As Integer Ptr Vind
Dim As SLel Ptr ps, rs
Dim As SLel Ptr Ptr graf
Dim As DLel Ptr pd, rd, L
Dim As Byte test

Open Cons For Input As #1
' Czytamy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice dynamiczne
graf = New SLel Ptr [n]
For i = 0 To n-1
  graf[i] = 0
Next
' Odczytujemy definicje
' krawędzi grafu
For i = 0 To m-1
  Input #1, v1, v2
  ps = New SLel
  ps->v = v2
  ps->next = graf[v1]
  graf[v1] = ps
Next
Close #1
Print
' Wykonujemy sortowanie
' topologiczne grafu
' ---------------------
' Tworzymy tablicę
' stopni wchodzących
Vind = new integer [n]
For i = 0 To n-1
  ' Zerujemy tablicę Vind[]
  Vind[i] = 0
Next
' Przeglądamy graf
For i = 0 To n-1
  ps = graf[i]
  ' Przeglądamy sąsiadów
  ' każdego wierzchołka
  While ps <> 0
    ' Wyznaczamy ich
    ' stopnie wchodzące
    Vind[ps->v] += 1
    ' Następny sąsiad
    ps = ps->next
  Wend
Next 
L = 0
 ' Na liście L umieszczamy
 ' od 0 do n-1
 For i = n-1 To 0 Step -1
  pd = New DLel
  pd->v = i
  pd->next = L
  If pd->Next Then _
    pd->next->prev = pd
  pd->prev = 0
  L = pd
Next
Do
  ' Oznaczamy brak
  ' usunięcia wierzchołka
  test = 0
  ' Przeglądamy listę L
  pd = L
  While pd
    If Vind[pd->v] > 0 Then
      ' Wierzchołki o niezerowym
      ' stopniu wchodzącym
      ' pomijamy
      pd = pd->next
    Else
      ' Będzie usunięcie
      ' wierzchołka
      test = 1
      ps = graf[pd->v]
      ' Przeglądamy
      ' listę sąsiadów
      While ps <> 0
        ' Modyfikujemy ich
        ' stopnie wchodzące
        Vind[ps->v] -= 1
        ' Następny sąsiad
        ps = ps->next
      Wend
      ' Wypisujemy usuwany
      ' wierzchołek
      print pd->v;
      ' Zapamiętujemy adres
      ' elementu L
      rd = pd
      ' Następny wierzchołek
      ' na liście lub 0!
      pd = pd->next
      ' Zapamiętany element rd
      ' listy L usuwamy z pamięci
      If rd->next then _
        rd->next->prev = rd->prev
      If rd->prev Then
        rd->prev->next = rd->next
      Else
        L = pd
      End If
      Delete rd
    End If
  Wend
Loop While test = 1
Print
Print
' Usuwamy zmienne dynamiczne
Delete [] Vind
For i = 0 To n-1
  ps = graf[i]
  While ps <> 0
    rs = ps
    ps = ps->next
    Delete rs
  Wend
Next
Delete [] graf
pd = L
While pd <> 0
  rd = pd
  pd = pd->next
  Delete rd
Wend
End

Python (dodatek)

# Sortowanie topologiczne
# Data: 12.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasy
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


class DLel:
    def __init__(self):
        self.prev = None
        self.next = None
        self.v = 0


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice dynamiczne
graf = [None] * n
# Odczytujemy definicje
# krawędzi grafu
for i in range(m):
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    ps = SLel()
    ps.v = v2
    ps.next = graf[v1]
    graf[v1] = ps
print()
# Wykonujemy sortowanie
# topologiczne grafu
# ---------------------
# Tworzymy tablicę
# stopni wchodzących
vind = [0] * n
# Przeglądamy graf
for i in range(n):
    ps = graf[i]
    # Przeglądamy sąsiadów
    # każdego wierzchołka
    while ps:
        # Wyznaczamy ich
        # stopnie wchodzące
        vind[ps.v] += 1
        # Następny sąsiad
        ps = ps.next
lst = None
# Na liście lst umieszczamy
# od 0 do n-1
for i in reversed(range(n)):
    pd = DLel()
    pd.v = i
    pd.next = lst
    if pd.next:
        pd.next.prev = pd
    pd.prev = None
    lst = pd
while True:
    # Oznaczamy brak
    # usunięcia wierzchołka
    test = False
    # Przeglądamy listę lst
    pd = lst
    while pd:
        if vind[pd.v] > 0:
            # Wierzchołki o niezerowym
            # stopniu wchodzącym
            # pomijamy
            pd = pd.next
        else:
            # Będzie usunięcie
            # wierzchołka
            test = True
            ps = graf[pd.v]
            # Przeglądamy
            # listę sąsiadów
            while ps:
                # Modyfikujemy ich
                # stopnie wchodzące
                vind[ps.v] -= 1
                # Następny sąsiad
                ps = ps.next
            # Wypisujemy usuwany
            # wierzchołek
            print(pd.v,end=" ")
            # Zapamiętujemy adres
            # elementu lst
            rd = pd
            # Następny wierzchołek
            # na liście lub 0!
            pd = pd.next
            # Zapamiętany element rd
            # listy lst usuwamy
            # z pamięci
            if rd.next:
                rd.next.prev = rd.prev
            if rd.prev:
                rd.prev.next = rd.next
            else:
                lst = pd
            del rd
    if not test: break
print()
print()
# Usuwamy zmienne dynamiczne
del vind
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
del graf
while lst:
    lst = lst.next

Wynik:

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

3 5 4 1 0 2

do podrozdziału do strony

Zadanie sortowania topologicznego można również rozwiązać za pomocą rekurencyjnego przejścia DFS i odpowiedniego zaznaczania odwiedzanych wierzchołków. Zasada działania opiera się na umieszczaniu na stosie wierzchołków po rekurencyjnym umieszczeniu tam wszystkich sąsiadów. Jest ona następująca:

Umówmy się, że będziemy oznaczać wierzchołki grafu kolorami:

biały – wierzchołek jeszcze nieodwiedzony
szary – wierzchołek odwiedzony, lecz jeszcze nieprzetworzony w całości.
zielony – wierzchołek odwiedzony i przetworzony w całości.

Na początku algorytmu kolorujemy wszystkie wierzchołki na biało. Teraz przeglądamy kolejne wierzchołki grafu w pętli. Jeśli natrafimy na wierzchołek biały, to uruchamiamy w nim rekurencyjne przejście DFS. W przejściu DFS najpierw sprawdzamy, czy bieżący wierzchołek jest szary (to nie błąd, ponieważ DFS jest uruchamiane rekurencyjnie, to może się tak zdarzyć, gdy w grafie występuje cykl i wróciliśmy do wierzchołka, który nie został jeszcze w całości przetworzony). Jeśli tak, to grafu nie da się posortować topologicznie. Zgłaszamy błąd i kończymy awaryjnie.

Jeśli wierzchołek jest biały, to kolorujemy go na szaro, a następnie odwiedzamy rekurencyjnie wszystkich sąsiadów. Gdy skończymy odwiedziny sąsiadów, wierzchołek kolorujemy na zielono i umieszczamy go na stosie.

Gdy algorytm zakończy działanie, wystarczy odczytać zawartość stosu, aby otrzymać porządek topologiczny wierzchołków w danym grafie.

Prześledźmy w tabelce kolejne kroki tego algorytmu

	S:	Kolorujemy wszystkie wierzchołki na biało.
	S:	Rozpoczynamy przejście DFS od wierzchołka 0. Wierzchołek ten kolorujemy na szaro, co oznacza, że jest on w trakcie przetwarzania. Z wierzchołka 0 istnieje krawędź prowadząca do wierzchołka 2.
	S:	Przechodzimy do wierzchołka 2. Kolorujemy go na szaro.
	S: 2	Ponieważ wierzchołek 2 nie ma dalszych sąsiadów, kończymy jego przetwarzanie. Kolorujemy go na zielono i umieszczamy na stosie.
	S: 0 2	Wracamy do wierzchołka 0. Nie ma dalszych sąsiadów, zatem kończymy przetwarzanie wierzchołka 0. Kolorujemy go na zielono i umieszczamy na stosie. W tym momencie przejście DFS kończy się.
	S: 0 2	Kolejne przejście uruchamiamy w wierzchołku 1. Kolorujemy go na szaro i odwiedzamy sąsiadów. Odwiedzamy wierzchołki 0 i 2, lecz są one pokolorowane na zielono, czyli ich przetwarzanie zostało zakończone i DFS nie będzie dalej kontynuowało przechodzenia grafu.
	S: 1 0 2	Wracamy do wierzchołka 1. Ponieważ nie posiada on więcej sąsiadów, kolorujemy go na zielono i umieszczamy na stosie. Przejście DFS kończy się.
	S: 1 0 2	Kolejne przejście DFS uruchamiamy w wierzchołku nr 3. Kolorujemy go na szaro i odwiedzamy rekurencyjnie sąsiadów 0, 1 i 4. Odwiedziny w 0 i 1 szybko się kończą, ponieważ wierzchołki te są już przetworzone.
	S: 1 0 2	Przechodzimy do wierzchołka 4. Kolorujemy go na szaro i odwiedzamy sąsiadów 1 i 2.
	S: 4 1 0 2	Ponieważ sąsiedzi 1 i 2 są już przetworzeni, wracamy do wierzchołka 4, kolorujemy go na zielono i umieszczamy na stosie.
	S: 3 4 1 0 2	Wracamy z powrotem do wierzchołka 3. Ponieważ wszyscy jego sąsiedzi zostali odwiedzeni, kolorujemy go na zielono i umieszczamy na stosie. Przejście DFS kończy się tutaj.
	S: 3 4 1 0 2	Ostatnie przejście DFS uruchamiamy w wierzchołku 5. Kolorujemy go na szaro i odwiedzamy jego sąsiadów 0 i 4. Oboje są już przetworzeni.
	S: 5 3 4 1 0 2	Wracamy zatem do wierzchołka 5, kolorujemy go na zielono i umieszczamy na stosie. Ponieważ w grafie nie ma już białych wierzchołków, sortowanie topologiczne jest zakończone, a stos zawiera odpowiednio uporządkowane wierzchołki.

Algorytm sortowania topologicznego acyklicznego grafu skierowanego z wykorzystaniem DFS

Funkcja rekurencyjna DFSts(graf,v,S)

Wejście:

graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
v : wierzchołek startowy; v ∈ C.
S : stos wierzchołków.

Wyjście:

Umieszcza na stosie najpierw rekurencyjnie sąsiadów, a następnie wierzchołek v.
true – normalne zakończenie.
false – błąd, graf nie jest acykliczny.

Elementy pomocnicze:

u : wierzchołek; u ∈ C.

Lista kroków:

K01: Jeśli v jest szary, ; graf posiada cykl
     to pisz "NOT DAG"
     i zakończ z wynikiem false
K02: Jeśli v jest zielony, ; wierzchołek już przetworzony
     to zakończ z wynikiem true
K03: Pokoloruj v na szaro ; oznaczamy wierzchołek jako przetwarzany
K04: Dla każdego sąsiada u wierzchołka v :
     wykonuj krok K05
K05: Jeśli DFSts(graf,u,S) = false, ; odwiedzamy rekurencyjnie wszystkich sąsiadów
     to zakończ z wynikiem false
K06: Pokoloruj v na zielono ; po odwiedzeniu sąsiadów wierzchołek jest przetworzony
K07: S.push(v) ; umieszczamy go na stosie
K08: Zakończ z wynikiem true

Algorytm główny

Wejście:

n : liczba wierzchołków w grafie; n ∈ C.
graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

S – stos zawierający wierzchołki posortowane topologicznie lub awaryjne zakończenie algorytmu w przypadku istnienia cykli w grafie.

Elementy pomocnicze:

v : wierzchołek; v ∈ C.

Lista kroków:

K01: Pokoloruj wierzchołki grafu na biało
K02: Dla każdego wierzchołka v grafu:
     wykonuj kroki K03…K04
K03:   Jeśli v nie jest biały,
       to następny obieg pętli K02
K04:   Jeśli DFSts(graf,v,S) = false, ; dla każdego
       to zakończ ; nieprzetworzonego wierzchołka wywołujemy DFS
K04: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje definicję grafu skierowanego, a następnie wypisuje w oknie konsoli ciąg wierzchołków grafu posortowany topologicznie.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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

Pascal

// Sortowanie topologiczne z DFS
// Data: 14.02.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------

program tsort;

// Typy danych
type
  PSLel = ^SLel;
  SLel =  record
    next : PSLel;
    v    : integer;
  end;

// Zmienne globalne
//-----------------
var
  sptr : integer;
  graf : array of PSLel;
  vs : array of byte;
  S : array of integer;

const
  // kolory wierzchołków
  WHITE = 0;
  GRAY  = 1;
  GREEN = 2;

// Rekurencyjna funkcja
// dokonująca sortowania
// topologicznego
// v - wierzchołek startowy
//-------------------------
function DFSts(v : integer)
                 : boolean;
var
  p : PSLel;

begin
  // Sprawdzamy,
  // czy nie ma cyklu
  if vs[v] = GRAY then
  begin
    // Jest cykl
    // sortowanie topologiczne
    // nie może zostać wykonane
    writeln;
    writeln('NOT A DAG');
    writeln;
    Exit(false);
  end;
  // Jeśli wierzchołek
  // jest biały,
  if vs[v] = WHITE then
  begin
    // to kolorujemy
    // go na szaro
    vs[v] := GRAY;
    // i przeglądamy
    // wszystkich sąsiadów
    p := graf[v];
    while p <> nil do
    begin
      // Wywołanie rekurencyjne
      if not DFSts(p^.v) then
        Exit(false);
      // Następny sąsiad
      p := p^.next;
    end;
    // Wierzchołek kolorujemy
    // na zielono
    vs[v] := GREEN;
    // i umieszczamy go
    // na stosie
    S[sptr] := v;
    inc(sptr);
  end;
  // Kończymy z wynikiem true
  DFSts := true;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  n, m, i, v1, v2 : integer;
  p, r : PSLel;

begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy
  // tablice dynamiczne
  SetLength(graf, n);
  // Pusty stos
  SetLength(S, n);
  sptr := 0;
  SetLength(vs, n);
  for i := 0 to n-1 do
  begin
    graf[i] := nil;
    // Wierzchołki kolorujemy
    // na biało
    vs[i] := WHITE;
  end;
  // Odczytujemy definicje
  // krawędzi grafu
  for i := 0 to m-1 do
  begin
    read(v1, v2);
    new(p);
    p^.v := v2;
    p^.next := graf[v1];
    graf[v1] := p;
  end;
  writeln;
  // Wykonujemy sortowanie
  // topologiczne grafu
  for i := 0 to n-1 do
    if vs[i] = WHITE then
    begin
      if not DFSts(i) then break;
    end;
  // Wypisujemy wyniki
  if sptr = n then
    for i := n-1 downto 0 do
      write(S[i], ' ');
  writeln;
  // Usuwamy zmienne dynamiczne
  for i := 0 to n-1 do
  begin
    p := graf[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;
  SetLength(graf, 0);
  SetLength(vs, 0);
  SetLength(S, 0);
end.

C++

// Sortowanie topologiczne z DFS
// Data: 14.02.2014
// (C)2014 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

// Typy danych
struct SLel
{
  SLel *next;
  int v;
};

// Zmienne globalne
//-----------------
int sptr, *S;
SLel **graf;
char *vs;

// kolory wierzchołków
const char WHITE = 0;
const char GRAY  = 1;
const char GREEN = 2;

// Rekurencyjna funkcja
// dokonująca sortowania
// topologicznego
// v - wierzchołek startowy
//-------------------------
bool DFSts(int v)
{
  SLel *p;

  // Sprawdzamy,
  // czy nie ma cyklu
  if(vs[v] == GRAY)
  {
    // Jest cykl,
    // sortowanie topologiczne
    // nie może zostać wykonane
    cout << "\nNOT A DAG\n\n";
    return false;
  }
  // Jeśli wierzchołek jest biały,
  if(vs[v] == WHITE)
  {
    // to kolorujemy go na szaro
    vs[v] = GRAY;
    // i przeglądamy
    // wszystkich sąsiadów
    for(p = graf[v];p;p = p->next)
      // Wywołanie rekurencyjne
      if(!DFSts(p->v))
        return false;
    // Wierzchołek kolorujemy
    // na zielono
    vs[v] = GREEN;
    // i umieszczamy go
    // na stosie
    S[sptr++] = v;
  }
  // Kończymy z wynikiem true
  return true;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n, m, i, v1, v2;
  SLel *p, *r;

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy
  // tablice dynamiczne
  graf = new SLel * [n];
  // Pusty stos
  S = new int [n];
  sptr = 0;
  vs = new char [n];
  for(i = 0; i < n; i++)
  {
    graf[i] = nullptr;
    // Wierzchołki
    // kolorujemy na biało
    vs[i] = WHITE;
  }
  // Odczytujemy definicje
  // krawędzi grafu
  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    p = new SLel;
    p->v = v2;
    p->next = graf[v1];
    graf[v1] = p;
  }
  cout << endl;
  // Wykonujemy sortowanie
  // topologiczne grafu
  for(i = 0; i < n; i++)
    if(vs[i] == WHITE)
    {
      if(!DFSts(i)) break;
    }
  // Wypisujemy wyniki
  if(sptr == n)
    for(i = n-1; i >= 0; i--)
      cout << S[i] << " ";
  cout << endl;
  // Usuwamy
  // zmienne dynamiczne
  for(i = 0; i < n; i++)
  {
    p = graf[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] graf;
  delete [] vs;
  delete [] S;
  return 0;
}

Basic

' Sortowanie topologiczne z DFS
' Data: 14.02.2014
' (C)2014 mgr Jerzy Wałaszek
'------------------------------

' Typy danych
Type SLel
  Dim As SLel Ptr next
  Dim As Integer v
End Type

' Zmienne globalne
'-----------------
Dim Shared As Integer sptr
Dim Shared As Integer Ptr S
Dim Shared As SLel Ptr Ptr graf
Dim Shared As Byte Ptr vs

' kolory wierzchołków
const WHITE = 0
const GRAY  = 1
const GREEN = 2

' Rekurencyjna funkcja
' dokonująca sortowania
' topologicznego
' v - wierzchołek startowy
'-------------------------
Function DFSts(ByVal v As Integer) _
                       As Integer
  Dim As SLel Ptr p

  ' Sprawdzamy, czy nie ma cyklu
  If vs[v] = GRAY Then
    ' Jest cykl
    ' sortowanie topologiczne
    ' nie może zostać wykonane
    Print
    Print "NOT A DAG"
    Print
    Return 0
  End If
  ' Jeśli wierzchołek jest biały,
  ' to kolorujemy go na szaro
  If vs[v] = WHITE Then
    vs [v] = GRAY
    p = graf[v]
    ' i przeglądamy
    ' wszystkich sąsiadów
    While p <> 0
      ' Wywołanie rekurencyjne
      If DFSts(p->v) = 0 Then _
        Return 0
      ' Następny sąsiad
      p = p->Next
    Wend
    ' Wierzchołek kolorujemy
    ' na zielono
    vs[v] = GREEN
    ' i umieszczamy go na stosie
    S[sptr] = v
    sptr += 1
  End If
  ' Kończymy z wynikiem true
  return 1
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer n, m, i, v1, v2
Dim As SLel Ptr p, r

Open Cons For Input As #1
' Czytamy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice dynamiczne
graf = New SLel Ptr [n]
' Pusty stos
S = New integer [n]
sptr = 0
vs = New Byte [n]
For i = 0 To n-1
  graf[i] = 0
  ' Wierzchołki kolorujemy na biało
  vs[i] = WHITE
Next
' Odczytujemy definicje
' krawędzi grafu
For i = 0 To m-1
  Input #1, v1, v2
  p = New SLel
  p->v = v2
  p->next = graf[v1]
  graf[v1] = p
Next
Print
' Wykonujemy sortowanie
' topologiczne grafu
For i = 0 To n-1
  If vs[i] = WHITE Then
    If DFSts(i) = 0 Then Exit For
  End If
Next
' Wypisujemy wyniki
If sptr = n Then
  For i = n-1 To 0 Step -1
  	 Print S[i];
  Next
End If
Print
' Usuwamy zmienne dynamiczne
For i = 0 To n-1
  p = graf[i]
  While p <> 0
    r = p
    p = p->Next
    Delete r
  Wend
Next
Delete [] graf
Delete [] vs
Delete [] S
End

Python (dodatek)

# Sortowanie topologiczne z DFS
# Data: 13.02.2025
# (C)2025 mgr Jerzy Wałaszek
#------------------------------

# Klasa listy
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


# kolory wierzchołków
WHITE = 0
GRAY  = 1
GREEN = 2

# Rekurencyjna funkcja
# dokonująca sortowania
# topologicznego
# v - wierzchołek startowy
#-------------------------
def dfs_ts(v):
    global vs,graf,s,sptr
    # Sprawdzamy, czy nie ma cyklu
    if vs[v] == GRAY:
        # Jest cykl
        # sortowanie topologiczne
        # nie może zostać wykonane
        print()
        print("NOT A DAG")
        print()
        return False
    # Jeśli wierzchołek jest biały,
    # to kolorujemy go na szaro
    if vs[v] == WHITE:
        vs[v] = GRAY
        p = graf[v]
        # i przeglądamy
        # wszystkich sąsiadów
        while p:
            # Wywołanie rekurencyjne
            if not dfs_ts(p.v):
                return False
            # Następny sąsiad
            p = p.next
        # Wierzchołek kolorujemy
        # na zielono
        vs[v] = GREEN
        # i umieszczamy go na stosie
        s[sptr] = v
        sptr += 1
    # Kończymy z wynikiem true
    return True


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice dynamiczne
graf = [None] * n
# Pusty stos
s = [0] * n
sptr = 0
vs = [0] * n
# Odczytujemy definicje
# krawędzi grafu
for i in range(m):
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    p = SLel()
    p.v = v2
    p.next = graf[v1]
    graf[v1] = p
print()
# Wykonujemy sortowanie
# topologiczne grafu
for i in range(n):
    if vs[i] == WHITE:
        if not dfs_ts(i): break
# Wypisujemy wyniki
if sptr == n:
    for i in reversed(range(n)):
        print(s[i], end=" ")
print()
# Usuwamy zmienne dynamiczne
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
del graf,vs,s

Wynik:

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

5 3 4 1 0 2

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Sortowanie topologiczne grafu skierowanego

Problem

Rozwiązanie nr 1

Algorytm sortowania topologicznego acyklicznego grafu skierowanego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Algorytm sortowania topologicznego acyklicznego grafu skierowanego z wykorzystaniem DFS

Funkcja rekurencyjna DFSts(graf,v,S)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm główny

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy