Prehľadávanie do šírky

Občas sa stretneme s problémom, pri ktorom sa chceme z nejakého počiatočného miesta dostať do cieľa na čo najmenej krokov. (Napríklad sa chceme dostať z domu do školy hromadnou dopravou na čo najmenej prestupov.)

Problémy takéhoto typu nám umožňuje efektívne riešiť práve prehľadávanie do šírky.

Zadanie

Zadaný je orientovaný graf (s $n$ vrcholmi a $m$ hranami), a dva jeho vrcholy $A$ a $B$. Na začiatok nás zaujíma, či existuje cesta z $A$ do $B$, a ak áno, jej dĺžka. (Neskôr sa pozrieme aj na to, ako možno jednu takú cestu nájsť.)

Fyzikálne riešenie

Predstavme si, že do vrcholu $A$ tečie neobmedzene veľa vody, ktorá sa šíri po hranách grafu. V čase $0$ je pod vodou iba $A$. V čase $1$ budú zatopené všetky vrcholy vzdialené od $A$ presne $1$, v čase $2$ budú zatopené tie vzdialené $2$, ... (Vrchol je zatopený, ak v predchádzajúcej jednotke času nebol pod vodou, ale teraz už je.)

V momente, keď je zatopené $B$, môžeme skončiť: čas zatopenia je hľadaná vzdialenosť. Ak $B$ nikdy nezatopíme, tak sa tam z $A$ nevieme dostať.

Formálnejšie...

...zostrojujeme vrecia $M_0, M_1, M_2, \ldots$, pričom $M_k$ obsahuje práve tie vrcholy, ktorých vzdialenosť od $A$ je práve $k$. (Obsahuje teda práve vrcholy, ktoré sú zatopené v čase $k$.)

Ak poznáme $M_k$, tak $M_{k + 1}$ vieme získať tak, že volíme postupne každý vrchol v $M_k$, a rozšírime sa z neho: do $M_{k + 1}$ pridáme všetky vrcholy, do ktorých vedie hrana zo zvoleného vrcholu, a ktoré ešte neboli zatopené. (To zodpovedá tomu, že si zvolíme vrchol zatopený v predchádzajúcom čase, a zatopíme všetky vrcholy, do ktorých vedie hrana zo zvoleného vrcholu, a ktoré ěste neboli zatopené.)

Je jasné, že takýmto spôsobom dostaneme iba vrcholy so vzdialenosťou $k + 1$. Dostaneme ale všetky také vrcholy?

Áno, a dôvod je nasledovný:

Zoberme si ľubovoľný vrchol $C$ z $M_{k + 1}$ (teda jeho vzdialenosť od $A$ je $k + 1$). Nájdeme vrchol z $M_k$, z ktorého keď sa rozšírime, zatopíme $C$.

Kedže má vrchol $C$ vzdialenosť od $A$ rovnú $k + 1$, existuje cesta z $A$ doňho dlhá $k + 1$. Hľadaným vrcholom je napríklad predposledný vrchol na tejto ceste:

• Vedie z neho hrana do $C$, takže keď sa z neho rozšírime, zatopíme $C$.
• Vieme sa doňho dostať z $A$ na $k$ krokov, takže jeho vzdialenosť je najviac $k$. Jeho vzdialenosť ale nemôže byť menšia ako $k$, lebo z neho vedie hrana do $C$, a vedeli by sme sa tak dostať z $A$ do $C$ na menej ako $k + 1$ krokov, čo by bol spor. Takže jeho vzdialenosť je presne $k$ -- je to teda vrchol z $M_k$.

Implementácia

Priamočiara implementácia by asi vyzerala nasledovne:

• Štandardne si vo vector<vector<int> > pre každý vrchol pamätáme, kam sa z neho vieme dostať jednou hranou.
• V poli dlhom $n$ si pre každý vrchol uchovávame jeho vzdialenosť, alebo $-1$, ak ešte nebol zatopený.
• Máme vector<vector<int> > M, s rovnakým významom, ako vo vyššie uvedených odsekoch. Postupne zostrojujeme M[0], M[1], M[2], ... a zastavíme sa buď vtedy, keď zatopíme $B$, alebo sa nám v niektorom kole nepodarí zatopiť žiaden nový vrchol.

Posledná časť implementácie zvykne byť ale nahradená elegantnejšou implementáciou s frontou. (Tá nám umožňuje vkladať prvky na jej koniec, alebo vyberať prvky z jej začiatku.)

Hlavným pozorovaním je, že pre korektnosť algoritmu nie je dôležité, v akom presnom poradí sa rozširujeme z vrcholov v $M_k$, ale iba to, že sa to deje skôr, ako rozširovanie sa z $M_{k + 1}$. Budeme mať teda frontu, v ktorej budú udalosti typu rozšír sa z vrcholu $v$. Na začiatku v nej bude iba vrchol $A$, a vždy, keď sa rozšírime z nejakého vrcholu, pridáme na koniec fronty vrcholy, ktoré sme tak zatopili.

Rozmyslite si, že sa naozaj budeme najprv rozširovať z vrcholov vzdialených $0$, potom $1$, $2$, a tak ďalej.

Zastavíme sa buď vtedy, keď zatopíme $B$, alebo keď je fronta prázdna.

int n; // pocet vrcholov  v grafe
int a, b; // odkial chceme ist a kam

// kam[i] obsahuje zoznam vrcholov, do ktorych sa vieme dostat z i
vector<vector<int> > kam;

... // nacitame graf

if (a == b) { // specialny pripad
  cout << "0\n";
  return 0;
}

vector<int> vzdialenost(n, -1);
queue<int> fronta;

fronta.push(a);
vzdialenost[a] = 0;
while (!fronta.empty()) {
  int v = fronta.front();
  fronta.pop();
  for (int i = 0; i < (int) kam[v].size(); i++) {
    int w = kam[v][i];
    if (vzdialenost[w] != -1) {
      continue;
    }
    vzdialenost[w] = vzdialenost[v] + 1;
    if (w == b) {
      cout << vzdialenost[w] << "\n";
      return 0;
    }
    fronta.push(w);
  }
}

Ďalšie využitia

Pomocou prehľadávania do šírky vieme v rovnakom čase zistiť nielen vzdialenosť od $A$ k jednému konkrétnemu vrcholu $B$, ale ku všetkým vrcholom v grafe. (Jednoducho nemáme žiadne špeciálne inštrukcie "ak si zatopil vrchol $B$ tak skonči".)

Takisto sa dá ľahko upraviť, aby sme aj jednu najkratšiu cestu z $A$ do $B$ aj našli. Stačí si pri zatopení vrcholu pre neho poznačiť, rozšírením ktorého vrcholu sme ho zatopili -- jeho predchodcu. Potom vieme cestu z $A$ do $B$ zrekonštruovať odzadu -- začneme s $B$, a kým nie sme v $A$, presúvame sa do predchodcu aktuálneho vrcholu.