2.4 Topološko sortiranje

Pretpostavimo da je zadat skup poslova u vezi sa čijim redosledom izvršavanja postoje neka ograničenja. Neki poslovi zavise od drugih, odnosno ne mogu se započeti pre nego što se ti drugi poslovi završe. Sve zavisnosti su poznate, a cilj je napraviti takav redosled izvršavanja poslova koji zadovoljava sva zadata ograničenja; drugim rečima, traži se redosled izvršavanja za koji važi da svaki posao započinje tek kad su završeni svi poslovi od kojih on zavisi. Na primer, želimo da sagradimo kuću. Da bismo to uspeli potrebno je da postavimo temelj, da sazidamo zidove, da stavimo krov, da uvedemo struju i vodu. Pritom, naravno, nije moguće, na primer, sazidati zidove dok se ne postavi temelj, niti uvesti vodu dok se ne stavi krov na kuću. Zadatak je odrediti neki ispravan redosled izvršavanja ovih poslova.

Dati problem ima primenu u raznim domenima: na primer, za određivanje redosleda u kom je potrebno izvršiti ponovno izračunavanje vrednosti formula u programima za tabelarna izračunavanja, za utvrđivanje redosleda u kom treba izvršiti zadatke u mejkfajlu, za unapređenje paralelizma instrukcija i slično. Zadatak je osmisliti efikasan algoritam za formiranje takvog redosleda.

Opisani problem može se formulisati u terminima grafova i naziva se topološko sortiranje grafa (engl. topological sort). Naime, zadatim poslovima i njihovim međuzavisnostima može se na prirodan način pridružiti usmereni graf \(G=(V,E)\): svakom poslu pridružuje se čvor, a usmerena grana od čvora \(x\) do čvora \(y\) postoji ako se posao \(y\) ne može započeti pre završetka posla \(x\).¹ Zadatak je odrediti topološki poredak čvorova, odnosno numeraciju čvorova brojevima od \(1\) do \(n=|V|\) (ili od \(0\) do \(n-1\)) tako da za svaku granu grafa \((u, v)\) važi da je polazni čvor \(u\) grane numerisan manjom vrednošću nego završni \(v\) čvor te grane. Graf nad kojim razmatramo ovaj problem mora biti bez usmerenih ciklusa, jer se u protivnom neki poslovi nikada ne bi mogli započeti.

Primer 2.4.1. Razmotrimo graf prikazan na slici 1.

U njemu postoji samo jedno ispravno topološko uređenje čvorova i to je \(B,A,D,C,E\). Čvor \(D\), recimo, mora da bude numerisan većim brojem od čvorova \(B\) i \(A\) jer postoje grane do \(D\) iz čvorova \(A\) i \(B\). Slično čvor \(D\) mora biti numerisan manjim brojem od čvorova \(C\) i \(E\) jer postoje grane od čvora \(D\) do čvorova \(C\) i \(E\). Dakle, u ovom grafu redni broj čvora \(D\) mora biti 3. Graf sa slike 1 možemo predstaviti i pogodnije, tako da čvorovi budu poređani duž jedne prave uređeni u odnosu na topološki poredak. Tada su sve grane grafa usmerene udesno (slika 2).

U opštem slučaju može postojati veći broj ispravnih topoloških uređenja grafa.

Primer 2.4.2. Ako razmotrimo graf sa slike 3, levo, u njemu postoje dva ispravna topološka uređenja: \(B,A,D,C,E\) i \(B,D,A,C,E\). Oni su prikazani na slici 3, desno.

Razmotrićemo dva različita algoritma za određivanje topološkog uređenja u acikličkom usmerenom grafu: Kanov algoritam (engl. Kahn’s algorithm) i algoritam zasnovan na pretrazi grafa u dubinu.

2.4.1 Kanov algoritam

Prirodno je započeti algoritam tako što uradimo onaj posao koji ne zavisi ni od jednog drugog posla. Nakon toga nam problem postaje jednostavniji, jer neki poslovi koji sa zavisili od tog prvog posla više ne zavise od njega. Dakle, problem rešavamo svođenjem na manji potproblem istog tipa, tj. induktivno-rekurzivnom konstrukcijom.

Prirodna je, dakle, naredna induktivna hipoteza.

Bazni slučaj je slučaj praznog grafa, koji ne sadrži čvorove i on se trivijalno rešava. Kao i obično, posmatrajmo proizvoljni graf sa \(n\) čvorova, uklonimo jedan čvor iz njega, primenimo induktivnu hipotezu na preostale čvorove u grafu i pokušajmo da proširimo numeraciju na polazni graf. Ono što je važno primetiti jeste da imamo slobodu izbora čvora koji uklanjamo pa, kao što smo rekli, biramo čvor sa ulaznim stepenom nula; njemu se može dodeliti broj \(1\). Postavlja se pitanje da li u proizvoljnom usmerenom acikličkom grafu uvek postoji čvor sa ulaznim stepenom nula? Intuitivno se nameće potvrdan odgovor, jer se sa označavanjem negde mora započeti. Sledeća lema potvrđuje ovu činjenicu.

Pretpostavimo da smo pronašli čvor čiji je ulazni stepen nula. Numerišimo ga sa \(1\), uklonimo sve grane koje vode iz njega, i numerišimo ostatak grafa (koji je takođe aciklički) brojevima od \(2\) do \(n\): prema induktivnoj hipotezi oni se mogu numerisati brojevima od \(1\) do \(n-1\), a zatim se svaki redni broj može povećati za jedan. Napomenimo još u ovom trenutku da nije neophodno efektivno izbacivati grane iz grafa, jer je to operacija koja se ne izvršava efikasno ako je graf predstavljen listom povezanosti. Naime, odgovarajući efekat moguće je realizovati i efikasnije, smanjivanjem za \(1\) ulaznog stepena čvora u koji data grana ulazi.

Dakle, problem se može rešiti sukcesivnim pronalaženjem čvorova sa ulaznim stepenom \(0\). Pri realizaciji ovog algoritma treba pronalaziti čvor sa ulaznim stepenom nula i ažurirati ulazne stepene čvorova posle uklanjanja grana koje polaze iz datog čvora. Drugi problem možemo rešiti tako što alociramo niz ulazniStepen dimenzije jednake broju čvorova u grafu i inicijalizujemo ga na vrednosti ulaznih stepena čvorova. Ulazne stepene čvorova u grafu možemo jednostavno odrediti prolaskom kroz skup svih grana u proizvoljnom redosledu i povećavanjem za jedan vrednosti ulazniStepen[w] svaki put kad se naiđe na neku granu \((v,w)\). Ukoliko je graf zadat listom povezanosti, sve grane su navedene u listi povezanosti kojom je predstavljen i ovaj korak je linearne složenosti po broju grana u grafu. Prilikom uklanjanja čvora \(v\), svim njegovim susedima \(w\) vrednost ulaznog stepena koja se nalazi u nizu na poziciji \(w\) smanjujemo za \(1\) (što je operacija složenosti \(O(1)\)). Svaka grana će biti uklonjena tačno jednom, tako da će ukupna složenost opet biti linearna po broju grana u grafu.

Pronalaženje čvora sa ulaznim stepenom nula može se sprovesti iteracijom kroz niz ulaznih stepena, međutim, složenost tog koraka je linearna u odnosu na broj čvorova, tako da bi ukupna složenost algoritma bila kvadratna. Problem možemo rešiti i efikasnije tako što tokom izvršavanja algoritma održavamo spisak svih čvorova čiji je ulazni stepen \(0\) – primetimo da takvih čvorova u svakom koraku može biti više. Dakle, potrebno je čvorove sa ulaznim stepenom nula čuvati u nekoj kolekciji u koju je efikasno umetati i iz koje je efikasno uklanjati elemente. U ove svrhe može se koristiti red (ili stek, što je jednako dobro). Prema prethodnoj lemi u acikličkom grafu postoji bar jedan čvor sa ulaznim stepenom nula, a pošto je graf sve vreme izvršavanja algoritma aciklički, red će u svakom trenutku, do samog kraja, biti neprazan. Svaki put kada uklonimo i numerišemo čvor \(v\) iz reda, uklanjamo i sve njegove grane \((v,w)\) tako što vrednost ulazniStepen[w] smanjujemo za jedan. Ako vrednost ulaznog stepena čvora \(w\) pri tome postane nula, čvor \(w\) upisuje se u red, čime se postiže da će se svi čvorovi stepena nula u smanjenom grafu nalaziti u redu (za čvorove koji nisu bili susedni sa \(v\) od ranije znamo da su u redu ako i samo ako im je ulazni stepen bio nula, a taj ulazni stepen se nije promenio nakon uklanjanja čvora \(v\), dok smo za čvorove susedene čvoru \(v\) upravo efektivno proverili da li im je stepen u smanjenom grafu postao nula i stavili smo ih u red ako i samo ako jeste). Algoritam završava sa radom kada red koji sadrži čvorove stepena nula postane prazan, jer su u tom trenutku svi čvorovi numerisani. Opisani algoritam zove se Kanov algoritam, po njegovom autoru Arturu Kanu.

Ako nakon završetka rada algoritma za neke čvorove važi da nisu bili dodati u red, to znači da postoji podskup skupa čvorova takav da u odgovarajućem indukovanom podgrafu svi čvorovi imaju ulazni stepen veći od nula. Stoga indukovani podgraf (a time i polazni graf) sadrži usmereni ciklus, suprotno pretpostavci da je graf aciklički.

void topolosko_sortiranje() {
  int brojCvorova = listaSuseda.size();
  // niz koji cuva ulazne stepene cvorova
  vector<int> ulazniStepen(brojCvorova,0);
  // niz koji cuva redne brojeve cvorova u topoloskom uredjenju
  vector<int> topoloskoUredjenje;
  // broj posecenih cvorova
  int brojPosecenih = 0;

  // inicijalizujemo niz ulaznih stepena cvorova
  for (int i = 0; i < listaSuseda.size(); i++)
    for (int j = 0; j < listaSuseda[i].size(); j++)
      ulazniStepen[listaSuseda[i][j]]++;

  // red koji cuva cvorove ulaznog stepena nula
  queue<int> cvoroviStepenaNula;

  // cvorove koji su ulaznog stepena 0 dodajemo u red
  for (int i = 0; i < brojCvorova; i++)
    if (ulazniStepen[i] == 0)
       cvoroviStepenaNula.push(i);
  
  while(!cvoroviStepenaNula.empty()) {
    // cvor sa pocetka reda numerisemo narednim brojem
    int cvor = cvoroviStepenaNula.front();
    cvoroviStepenaNula.pop();
    topoloskoUredjenje.push_back(cvor);

    brojPosecenih++;

    // za sve susede tog cvora azuriramo ulazne stepene
    for (int i = 0; i < listaSuseda[cvor].size(); i++) {
      int sused = listaSuseda[cvor][i];
      ulazniStepen[sused]--;
      // ako je ulazni stepen suseda postao 0, dodajemo ga u red
      if (ulazniStepen[sused] == 0)
         cvoroviStepenaNula.push(sused);
    }
  }

  // ako smo numerisali sve cvorove u grafu
  if (brojPosecenih == brojCvorova) {
     // stampamo dobijeno topolosko uredjenje
     cout << "Redosled cvorova u topoloskom uredjenju je:" << endl;
     for (int i = 0; i < brojCvorova; i++)
        cout << topoloskoUredjenje[i] << ": " << i+1 << endl;
  }
  else
     // zakljucujemo da graf sadrzi usmereni ciklus
     cout << "Graf nije aciklicki" << endl;
}

int main() {
  topolosko_sortiranje();
  return 0;
}

U slučaju kada je graf zadat listama povezanosti vremenska složenost inicijalizacije niza ulazniStepen je \(O(|V|+|E|)\). U petlji while (kroz koju se prolazi \(|V|\) puta) za pronalaženje čvora sa ulaznim stepenom nula potrebno je konstantno vreme (pristup redu). Svaka grana \((v,w)\) razmatra se tačno jednom, u petlji kroz koju se prolazi nakon uklanjanja čvora \(v\) iz reda. Prema tome, ukupan broj promena vrednosti elemenata niza ulazniStepen u svim izvršavanjima spoljašnje petlje while jednak je broju grana u grafu. Vremenska složenost Kanovog algoritma je dakle \(O(|V|+|E|)\), odnosno linearna je funkcija od veličine grafa.

2.4.2 Algoritam zasnovan na pretrazi u dubinu

Zamislimo na trenutak da je graf zadat tako da su mu grane okrenute od poslova koji zavise ka poslovima od kojih zavise i definišimo rekurzivnu proceduru koja obrađuje posao tj. dodeljuje mu redni broj u topološkom redosledu. Da bi posao za koji je funkcija pozvana mogao da bude urađen, potrebno je da se obezbedi da su svi poslovi od kojih on zavisi završeni pre njega, što znači da je potrebno da se obiđe graf krenuvši od tog posla (čvora) i da se urade svi dostupni poslovi (tj. preskoče ako su već ranije urađeni). Kada se to uradi, tek tada tekućem čvoru može biti dodeljen naredni slobodan broj. Primećujemo, dakle, da ovaj algoritam može da vrši klasičan obilazak grafa u dubinu, dodeljujući traženi broj čvoru u sklopu odlazne numeracije.

Dokažimo da se na ovaj način dobija ispravan topološki redosled.

Dakle, ako su grane usmerene od zavisnog ka nezavisnom čvoru, odlazna numeracija daje ispravan topološki redosled. Implementacija je sasvim jednostavna: u klasičnom DFS obilasku prilikom izlazne obrade čvoru treba dodati redni broj u topološkom redosledu tj. dodati ga na kraj niza u kom se čvorovi čuvaju u skladu sa topološkim redosledom. U glavnoj funkciji pokrećemo DFS obilazak svakog čvora (u proizvoljnom redosledu), preskačući čvorove koji su već ranije obrađeni (slično kao kod određivanja komponenata povezanosti).

Vratimo se na standardnu postavku problema u kom su grane grafa orijentisane od nezavisnog ka zavisnom čvoru. Ako sa \(t(x)\) označimo redni broj čvora \(x\) u topološkom poretku grafa \(G\), za svaku granu \((u,v)\) potrebno je da važi \(t(u) < t(v)\). Pošto za svaku granu \((u, v)\) važi \(u.\mathit{Post} > v.\mathit{Post}\), ako čvorove grafa uredimo u opadajućem redosledu u odnosu na odlaznu numeraciju čvorova, dobićemo jedno topološko uređenje grafa. Implementaciju je potrebno izmeniti samo tako što se u odlaznoj obradi čvorovima dodeljuju brojevi unazad, od \(n\) do \(1\). Ako čvorove ne numerišemo, već ih stavljamo u niz u skladu sa topološkim redosledom, oni će u nizu biti složeni naopako i niz je nakon obrade potrebno obrnuti tj. čvorove obrađivati od kraja ka početku tog niza. Alternativno, čvorove možemo postavljati na namenski stek i obrađivati ih u topološkom redosledu tako što ćemo ih jedan po jedan skidati sa tog steka. Moguće je koristiti i neku strukturu podataka koja dopušta efikasno dodavanje elemenata na početak (npr. listu ili red sa dva kraja).

void dfs(int cvor, vector<bool> &posecen, vector<int> &odlazna) {
  posecen[cvor] = true;
  
  // rekurzivno prolazimo kroz sve susede koje nismo obisli
  for (int sused : listaSuseda[cvor]) {
    if (!posecen[sused])
       dfs(sused,posecen,odlazna);
  }

  // u vektor odlazna dodajemo na kraj naredni cvor
  // koji napustamo pri DFS obilasku
  odlazna.push_back(cvor);
}

void topolosko_sortiranje() {
  int brojCvorova = listaSuseda.size();
  vector<bool> posecen(brojCvorova);
  // niz koji sadrzi redom cvorove prema redosledu napustanja
  vector<int> odlazna;

  for (int cvor = 0; cvor < brojCvorova; cvor++)
    if (!posecen[cvor])
       dfs(cvor,posecen,odlazna);

  // cvorove ispisujemo u opadajućem redosledu odlazne numeracije    
  cout << "Redosled cvorova u topoloskom uredjenju je:" << endl;
  for (int i = brojCvorova - 1; i >= 0; i--)
    cout << odlazna[i] << ": " << brojCvorova - i << endl;
  
}

int main() {
  topolosko_sortiranje();
  return 0;
}

S obzirom na to da se prikazani algoritam svodi na DFS pretragu i određivanje odlazne numeracije čvorova, njegova vremenska složenost iznosi \(O(|E|+|V|)\).