Sortowanie topologiczne grafu skierowanego


Tematy pokrewne   Podrozdziały
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
  Rozwiązanie nr 1
Rozwiązanie nr 2

Problem

Dany graf skierowany 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:

 

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 symbol 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).
Elementy pomocnicze:
L  –  lista dwukierunkowa wierzchołków grafu
Vind  –  tablica stopni wchodzących grafu
u  –  wierzchołek, u symbol 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 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:     pL  
K07:     Dopóki p ≠ nil, wykonuj 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:         rp  
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 K05 ; jeśli było usunięcie, to powtarzamy
K16: Zakończ ; w przeciwnym razie kończymy

 

Program

Ważne:

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.  

Przykładowe dane dla programu:

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

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 

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:
  • 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 DFStsort(graf,v,S)
Wejście
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
v  –  wierzchołek startowy, v symbol 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 symbol 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  
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 symbol 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 symbol C
Lista kroków:
K01: Pokoloruj wierzchołki grafu na biało  
K02: Dla każdego wierzchołka v grafu wykonuj:
    Jeśli v nie jest biały, to następny obieg pętli K02
 
K03:     Jeśli DFStsort(graf,v,S) = false, to zakończ ; dla każdego nieprzetworzonego wierzchołka wywołujemy DFS
K04: Zakończ  

 

Program

Ważne:

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.  

Przykładowe dane dla programu:

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

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.