Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Sortowanie topologiczne grafu skierowanego

SPIS TREŚCI
Podrozdziały

Problem

Dany graf skierowany należy posortować topologicznie

Sortowanie topologiczne (ang. topological sort) grafu skierowanego polega na utworzeniu 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 jest acyklicznym grafem skierowanym (ang. DAG - directed acyclic graph ). Kolejność wierzchołków nie połączonych ścieżką jest dowolna.

Rozwiązanie nr 1

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:

obrazek Wy: Oto nasz graf do posortowania topologicznego.
obrazek 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.
obrazek 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.
obrazek 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.
obrazek 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.
obrazek 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.
obrazek 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.
obrazek 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 i porównywać z n – otrzymamy w ten sposób algorytm badający przy okazji cykliczność grafu ).
Zmienne 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:     Dla każdego sąsiada u  wierzchołka v :
    wykonuj: Vind [ u  ] ← Vind [ u  ] + 1
obliczamy stopnie wchodzące wierzchołków
K04: Umieść na liście L  n  elementów
o wartościach od 0 do n  - 1
inicjujemy listę wierzchołków
K05:     test  ← false zakładamy, że nie było usunięcia wierzchołka
K06:     p  ← L  
K07:     Dopóki p  ≠ nil,
    wykonuj kroki K08...K14
przeglądamy wierzchołki na liście L
K08:         Jeśli Vind [ ( pv  ) ] > 0,
        to p  ← ( pnext  )
             i następny obieg pętli K07
wierzchołki o niezerowym stopniu wchodzącym pomijamy
K09:         test  ← true zaznaczamy, że jest usunięcie wierzchołka
K10:         Dla każdego sąsiada u  wierzchołka ( pv  ):
        wykonuj: Vind [ u  ] ← Vind [ u  ] - 1
obliczamy nowe stopnie wchodzące dla wszystkich sąsiadów usuwanego wierzchołka
K11:         Pisz ( pv  ) usuwany wierzchołek wyprowadzamy na wyjście
K12:         r  ← p  
K13:         p  ← ( pnext  )  
K14:         Usuń z L  element
         wskazywany przez r
a następnie usuwamy go z listy L
K15: Jeśli test  = true,
to idź do kroku K05
jeśli było usunięcie, to powtarzamy
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 posortowany topologicznie. 
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli ):
obrazek 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
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

  PdlistEl = ^dlistEl;
  dlistEl =  record
    prev, next : PdlistEl;
    v          : integer;
  end;

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

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

begin
  read ( n, m );              // Czytamy liczbę wierzchołków i krawędzi

  // 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

  SetLength ( Vind, n );      // Tworzymy tablicę stopni wchodzących
  for i := 0 to n - 1 do Vind [ i ] := 0; // Zerujemy tablicę Vind [ ] 

  for i := 0 to n - 1 do      // Przeglądamy graf
  begin
    ps := graf [ i ];         // Przeglądamy sąsiadów każdego wierzchołka
    while ps <> nil do
    begin
      inc ( Vind [ ps^.v ] ); // Wyznaczamy ich stopnie wchodzące
      ps := ps^.next;         // Następny sąsiad
    end;
  end;

  L := nil;
  for i := n - 1 downto 0 do  // Na liście L umieszczamy od 0 do n - 1
  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
    test := false;            // Oznaczamy brak usunięcia wierzchołka

    pd := L;                  // Przeglądamy listę L
    while pd <> nil do

      if Vind [ pd^.v ] > 0 then pd := pd^.next // Wierzchołki o niezerowym stopniu wchodzącym pomijamy
      else
      begin
        test := true;         // Będzie usunięcie wierzchołka
        ps := graf [ pd^.v ]; // Przeglądamy listę sąsiadów
        while ps <> nil do
        begin
          dec ( Vind [ ps^.v ] ); // Modyfikujemy ich stopnie wchodzące
          ps := ps^.next;     // Następny sąsiad
        end;

        write ( pd^.v, ' ' ); // Wypisujemy usuwany wierzchołek
        rd := pd;             // Zapamiętujemy adres elementu L
        pd := pd^.next;       // Następny wierzchołek na liście lub nil!

        // 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 slistEl
{
  slistEl *next;
  int v;
};

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

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

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

  cin >> n >> m;                // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  graf = new slistEl * [ n ];
  for( i = 0; i < n; i++ ) graf [ i ] = NULL;

  // Odczytujemy definicje krawędzi grafu

  for( i = 0; i < m; i++ )
  {
    cin >> v1 >> v2;
    ps = new slistEl;
    ps->v = v2;
    ps->next = graf [ v1 ];
    graf [ v1 ] = ps;
  }

  cout << endl;

  // Wykonujemy sortowanie topologiczne grafu

  Vind = new int [ n ];         // Tworzymy tablicę stopni wchodzących
  for( i = 0; i < n; i++ ) Vind [ i ] = 0; // Zerujemy tablicę Vind [ ] 

  for( i = 0; i < n; i++ )      // Przeglądamy graf
    for( ps = graf [ i ];ps;ps = ps->next ) // Przeglądamy sąsiadów każdego wierzchołka
      Vind [ ps->v ] ++;        // Wyznaczamy ich stopnie wchodzące

  L = NULL;
  for( i = n - 1; i >= 0; i-- ) // Na liście L umieszczamy od 0 do n - 1
  {
    pd = new dlistEl;
    pd->v = i;
    pd->next = L;
    if( pd->next ) pd->next->prev = pd;
    pd->prev = NULL;
    L = pd;
  }

  do
  {
    test = false;             // Oznaczamy brak usunięcia wierzchołka

    pd = L;                   // Przeglądamy listę L
    while( pd )
      if( Vind [ pd->v ] ) pd = pd->next; // Wierzchołki o niezerowym stopniu wchodzącym pomijamy
      else
      {
        test = true;          // Będzie usunięcie wierzchołka
        for( ps = graf [ pd->v ];ps;ps = ps->next ) // Przeglądamy listę sąsiadów
          Vind [ ps->v ] --;  // Modyfikujemy ich stopnie wchodzące

        cout << pd->v << " "; // Wypisujemy usuwany wierzchołek
        rd = pd;              // Zapamiętujemy adres elementu L
        pd = pd->next;        // Następny wierzchołek na liście lub NULL!

        // 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 slistEl
  Dim As slistEl Ptr Next
  Dim As Integer v
End Type

Type dlistEl
  Dim As dlistEl 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 slistEl Ptr ps, rs
Dim As slistEl Ptr Ptr graf
Dim As dlistEl Ptr pd, rd, L
Dim As Byte test

Open Cons For Input As #1

Input #1, n, m              ' Czytamy liczbę wierzchołków i krawędzi

' Tworzymy tablice dynamiczne

graf = New slistEl 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 slistEl
  ps->v = v2
  ps->next = graf [ v1 ] 
  graf [ v1 ] = ps
Next

Close #1

Print

' Wykonujemy sortowanie topologiczne grafu

Vind = new integer [ n ]    ' Tworzymy tablicę stopni wchodzących
For i = 0 To n - 1
  Vind [ i ] = 0            ' Zerujemy tablicę Vind [ ] 
Next

For i = 0 To n - 1          ' Przeglądamy graf
  ps = graf [ i ] 
  While ps                  ' Przeglądamy sąsiadów każdego wierzchołka
    Vind [ ps->v ] += 1     ' Wyznaczamy ich stopnie wchodzące
    ps = ps->Next           ' Następny sąsiad
  Wend
Next  

L = 0
For i = n - 1 To 0 Step -1  ' Na liście L umieszczamy od 0 do n - 1
  pd = New dlistEl
  pd->v = i
  pd->next = L
  If pd->Next Then pd->next->prev = pd
  pd->prev = 0
  L = pd
Next

Do
  test = 0                  ' Oznaczamy brak usunięcia wierzchołka

  pd = L                    ' Przeglądamy listę L
  While pd
    If Vind [ pd->v ] > 0 Then
    	pd = pd->Next ' Wierzchołki o niezerowym stopniu wchodzącym pomijamy
    Else
      test = 1              ' Będzie usunięcie wierzchołka
      ps = graf [ pd->v ] 
      While ps              ' Przeglądamy listę sąsiadów
        Vind [ ps->v ] -= 1 ' Modyfikujemy ich stopnie wchodzące
        ps = ps->Next       ' Następny sąsiad
      Wend
      print pd->v;          ' Wypisujemy usuwany wierzchołek
      rd = pd               ' Zapamiętujemy adres elementu L
      pd = pd->Next         ' Następny wierzchołek na liście lub 0!

     ' 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
    rs = ps
    ps = ps->Next
    Delete rs
  Wend
Next

Delete [ ] graf

pd = L
While pd
  rd = pd
  pd = pd->Next
  Delete rd
Wend

End
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
Na początek:  podrozdziału   strony 

Rozwiązanie nr 2

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:

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

obrazek S: Kolorujemy wszystkie wierzchołki na biało.
obrazek 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.
obrazek S: Przechodzimy do wierzchołka 2. Kolorujemy go na szaro.
obrazek S: 2 Ponieważ wierzchołek 2 nie ma dalszych sąsiadów, kończymy jego przetwarzanie. Kolorujemy go na zielono i umieszczamy na stosie.
obrazek 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ę.
obrazek 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.
obrazek 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ę.
obrazek 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.
obrazek S: 1 0 2 Przechodzimy do wierzchołka 4. Kolorujemy go na szaro i odwiedzamy sąsiadów 1 i 2.
obrazek 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.
obrazek 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.
obrazek 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.
obrazek 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 DFStsort ( 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.
Zmienne pomocnicze:
u  –  wierzchołek, u  ∈ C.

Lista kroków:

K01: Jeśli v  jest szary,
to pisz
"NOT DAG"
i zakończ z wynikiem false
graf posiada cykl
K02: Jeśli v  jest zielony,
to zakończ z wynikiem true
wierzchołek już przetworzony
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 DFStsort ( graf, u, S  ) = false,
    to zakończ z wynikiem false
odwiedzamy rekurencyjnie wszystkich sąsiadów
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.
Zmienne 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 DFStsort ( graf, v, S  ) = false,
    to zakończ
dla każdego 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 ):
obrazek 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
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

// Zmienne globalne
//-----------------
var
  sptr : integer;
  graf : array of PslistEl;
  visited : array of byte;
  S : array of integer;

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

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

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

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

begin
  read ( n, m );                 // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  SetLength ( graf, n );
  SetLength ( S, n ); sptr := 0; // Pusty stos
  SetLength ( visited, n );
  for i := 0 to n - 1 do
  begin
    graf [ i ] := nil;
    visited [ i ] := WHITE;      // Wierzchołki kolorujemy na biało
  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 visited [ i ] = WHITE then
    begin
      if not DFStsort ( 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 ( visited, 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 slistEl
{
  slistEl *next;
  int v;
};

// Zmienne globalne
//-----------------
int sptr, *S;
slistEl **graf;
char *visited;

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

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

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

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

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

  cin >> n >> m;                  // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  graf = new slistEl * [ n ];
  S    = new int [ n ]; sptr = 0; // Pusty stos
  visited = new char [ n ];
  for( i = 0; i < n; i++ )
  {
    graf [ i ] = NULL;
    visited [ i ] = WHITE;        // Wierzchołki kolorujemy na biało
  }

  // Odczytujemy definicje krawędzi grafu

  for( i = 0; i < m; i++ )
  {
    cin >> v1 >> v2;
    p = new slistEl;
    p->v = v2;
    p->next = graf [ v1 ];
    graf [ v1 ] = p;
  }

  cout << endl;

  // Wykonujemy sortowanie topologiczne grafu

  for( i = 0; i < n; i++ )
    if( visited [ i ] == WHITE )
    {
      if( !DFStsort ( 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 [ ] visited;
  delete [ ] S;

  return 0;
}
Basic
' Sortowanie topologiczne z DFS
' Data: 14.02.2014
' (C)2014 mgr Jerzy Wałaszek
'------------------------------

' Typy danych

Type slistEl
  Dim As slistEl Ptr Next
  Dim As Integer v
End Type

' Zmienne globalne
'-----------------

Dim Shared As Integer sptr
Dim Shared As Integer Ptr S
Dim Shared As slistEl Ptr Ptr graf
Dim Shared As Byte Ptr visited

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

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

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

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

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

Open Cons For Input As #1
Input #1, n, m               ' Czytamy liczbę wierzchołków i krawędzi

' Tworzymy tablice dynamiczne

graf = New slistEl Ptr [ n ] 
S    = New integer [ n ]     ' Pusty stos
sptr = 0 
visited = New Byte [ n ] 
For i = 0 To n - 1
  graf [ i ] = 0
  visited [ i ] = WHITE      ' Wierzchołki kolorujemy na biało
Next

' Odczytujemy definicje krawędzi grafu

For i = 0 To m - 1
  Input #1, v1, v2
  p = New slistEl
  p->v = v2
  p->next = graf [ v1 ] 
  graf [ v1 ] = p
Next

Print

' Wykonujemy sortowanie topologiczne grafu

For i = 0 To n - 1
  If visited [ i ] = WHITE Then
    If DFStsort ( 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
    r = p
    p = p->Next
    Delete r
  Wend
Next
Delete [ ] graf
Delete [ ] visited
Delete [ ] S

End
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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2021 mgr Jerzy Wałaszek

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.