Sortowanie topologiczne

RNO-Wiki

Sortowanie topologiczne polega na ułożeniu wszystkich wierzchołków grafu w taki sposób, że jeśli graf zawiera krawędź z u do v, to w porządku podanym nam przez algorytm sortowania topologicznego u znajdzie się przed v. Oczywiście znalezienie takiego porządku nie jest możliwe w grafie posiadającym cykle. Do znajdowania porządku topologicznego wierzchołków będziemy używać algorytmu przeszukiwania grafu wgłąb. Skorzystamy z obserwacji, że jeśli jeśli DFS nie odwiedzi żadnego wierzchołka po odwiedzeniu wierzchołka x to znaczy, że x może być ostatni w porządku topologicznym.

W naszym algorytmie będziemy mieć procedurę TOPOLOGICAL-SORT( G), która dostanie acykliczny graf skierowany (dag) G i zwróci nam posortowaną topologicznie listę wierzchołków grafu G.

TOPOLOGICAL-SORT( G)
var
    Q   : lista wierzchołków;
    c   : integer; { kolor dla spójnych składowych G }
    color: array [1..n] of integer; { tablica z kolorowaniem }
begin
    Na początek Q ma być puste.
    Tablica color ma być wypełniona zerami.
    c ← 1;
    for każdy v wierzchołek grafu G do begin
        if color[ v] <> 0 then begin 
            DFS( v, c );
            c ← c + 1;
        end;
    end;
   return Q;
end.
 
DFS( x, c)
begin
    color[ x] = c;
    for każdy sąsiad v wierzchołka x w grafie G do begin
        if color[ v] == 0 then
            DFS( v, c );
    end;
    Q.push-front( x);
end.