Lühimad teed, DSU, minimaalne toesepuu

Põhimõisted

Graaf (graph) on struktuur, mis koosneb hulgast tippudest (vertices) ja tippe omavahel ühendavatest servadest (edges).

Sellist struktuuri võib programmi koodis erinevatel viisidel meeles hoida. Võib teha lihtsa nimekirja kõikidest graafi servadest (edge list).

        [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (8, 6), (7, 6), (4, 6)]

Võib hoida iga tipu kohta meeles tema naabrite listi (adjacency list).

        1: [2, 5]
        2: [1, 3]
        3: [2, 4]
        4: [3, 5, 6]
        5: [1, 4]
        6: [4, 7, 8]
        7: [6]
        8: [6]

Võib aga ka hoopis ehitada $N \times N$ maatriksi, mille $i$-ndal real ja $j$-ndas veerus on 1 parajasti siis, kui graafis on tippude $i$ ja $j$ vahel serv.

        0 1 0 0 1 0 0 0
        1 0 1 0 0 0 0 0
        0 1 0 1 0 0 0 0
        0 0 1 0 1 1 0 0
        1 0 0 1 0 0 0 0
        0 0 0 0 0 0 1 1
        0 0 0 0 0 1 0 0
        0 0 0 0 0 1 0 0
      

Kõigil nendel lähenemistel on omad plussid ja miinused. Teist varianti kasutades saab kiiresti läbi käia kõik etteantud tipu naabrid, kolmandat kasutades aga kiiresti kontrollida, kas kahe etteantud tipu vahel on serv. Enamus ülesannetes antakse sisend esimesel viisil (tavaliselt $m$ rida, igal real kaks täisarvu), aga lahenduses endas on mugavaim kasutada teist varianti. Tüüpilise graafiülesande lahendus algab sisendi lugemisest, mis näeb enamasti välja umbes nii:

int n, m;
cin >> n >> m;

vector<vector<int>> adj (n, vector<int> (0));
for (int i = 0; i < n; i++) {
  int u, v;
  cin >> u >> v;
  adj[u].push_back(v);
  adj[v].push_back(u);
}

Veel tuleb ettevaatlik olla kahe pisut patoloogilise juhuga: paralleelsed servad (parallel edges) ja silmused (loop või self-loop). Mõnes graafis võib kahe tipu vahel olla enam kui üks serva; lisaks võib mõni serv ühendada mingit tippu iseendaga. Paljude ülesannete tekstides on niisugune olukord välistatud, aga mitte alati. Mõnikord on selliste servade leidumine isegi ülesande vaatenurgast tähtis.

Lühima tee leidmine

Dijkstra algoritm: ühest tipust kõikidesse teistesse

Idee on tipud läbi käia kauguse järjekorras. Hetkel, kui käime läbi tipu $u$, teame juba tema kaugust algtipust $s$. Seejärel uuendame kõikide (veel läbi käimata) tippude kaugust.

vector<int> dist (n, INF); // esialgu on kõikide tippude kauguseks lõpmatus        
dist[s] = 0; // ...välja arvatud algustipp, mis on kaugusel 0
vector<int> visited (n, 0); // visited[u] - kas oleme tipus u käinud? 0 kui ei, 1 kui jah
while (true) {
  // leiame lähima tipu, mida me pole veel külastanud
  int u = -1;
  int closest_dist = INF;
  for (int i = 0; i < n; i++) {
    if (!visited[i] && dist[i] < closest_dist) {
      u = i;
      closest_dist = dist[i];
    }
  }

  if (closest_dist == INF)
    // pole enam rohkem tippe, mida külastada
    break;
                                 
  // tipu u külastamine
  // märgime tipu u külastatuks
  visited[u] = 1;

  // ...ja seejärel käime läbi kõik tema naabrid
  for (auto e : adj[u]) {
    // adj[u] koosneb paaridest kujul (teine tipp, serva pikkus)
    dist[e.first] = min(dist[e.first], dist[u] + e.second);
  }
}

Sellist algoritmi nimetatakse Dijkstra algoritmiks. Kui vaja on leida lisaks teekonna pikkusele teekond ise, siis tuleb iga tipu kohta meelde jätta, missugune on eelmine tipp lühimal teekonnal tipust $s$ sellesse tippu. Loomulikult võib ka juhtuda, et mõnesse tippu ei olegi võimalik jõuda. Sel juhul jääb tema kauguseks INF.

See on toimiv lahendus, aga liiga aeglane: me otsime $N$ korda $N$ arvu seast vähimat, mis tähendab, et keerukus peab olema juba vähemalt $O(N^2)$. Et algoritm kiiremini töötaks, vajame andmestruktuuri, millega saaks kiiremini lähimat veel külastamata tippu leida.

Üks selline sisseehitatud andmestruktuur on C++ keeles priority_queue. Pythonis on sellele lähim vaste heapq. Näiteks priority_queue<int> toetab muuhulgas järgmisi operatsioone:

• push(x): lisab andmestruktuuri täisarvu x;
• top(): leiab suurima andmestruktuuris oleva täisarvu;
• pop(): eemaldab suurima struktuuris oleva täisarvu.

See on lähedal sellele, mida me tahame, aga mitte päris sama. Esiteks on meil vaja lähimat tippu leides teada ka tippu ennast, mitte ainult tema kaugust. Selleks hoiame andmestruktuuris mitte täisarve, vaid paare: priority_queue<pair<int, int>>. Paari esimene element tähistab tipu kaugust, teine tipu enda numbrit. Paare sorteeritakse leksikograafiliselt: esmalt esimese elemendi järgi, võrduse korral teise järgi.

Teiseks ei ole meil vaja leida mitte suurimat, vaid vähimat elementi. Selleks on vaja priority_queue sisemine sorteerimisjärjekord ümber pöörata: priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>. See viimane tüübinimi on päris pikk ja lohisev; lihtsustamiseks võib kasutada järgmist trikki: teha kusagil programmi alguses

        template<typename T>
        using inverted_priority_queue = priority_queue<T, vector<T>, greater<T>>;

ja seejärel kasutada lihtsalt inverted_priority_queue<pair<int, int>>.

Sellise andmestruktuuriga optimeeritud Dijkstra algoritm võiks välja näha midagi sellist.

vector<int> dist (n, INF); // esialgu on kõikide tippude kauguseks lõpmatus
// muudatus võrreldes eelmisega - dist seatakse alles tipu külastamise hetkel

inverted_priority_queue<pair<int, int>> Q;
while (!Q.empty()) {
  auto cur = Q.top();
  Q.pop();

  int u = cur.second;
  if (dist[u] != INF) {
    // võib juhtuda, et oleme juba seda tippu külastanud
    // sel juhul lihtsalt ignoreerime seda paari
    continue;
  }

  dist[u] = cur.first;
  // nagu enne, käime läbi kõik tipu u naabrid
  for (auto e : adj[u]) {
    Q.push(make_pair(e.first, dist[u] + e.second)); // võib ka Q.emplace(...)
  }
}

Mis on selle uue lahenduse keerukus? Järjekorda pannakse iga serva kohta üks paar, see tähendab kokku $O(M)$ paari; priority_queue operatsioonid võtavad kokku aega $O(M \log M)$. Lisaks käiakse iga tipp läbi ülimalt ühe korra. Kõik kokku $O(N + M \log M)$.

Floydi-Warshalli algoritm: igast tipust igasse teisse

Üks võimalus ülesannet lahendada on rakendada $N$ korda Dijkstra algoritmi: sel juhul on keerukus $O(NM \log M)$. Aga on ka üks teine algoritm, mis on suure $M$ korral pisut kiirem, ja mida on lisaks ka väga kerge implementeerida.

Selles ülesandes on mugav graafi esitada naabrusmaatriksina. Loome maatriksi $\mathrm{dist}$ järgmisel viisil: kui tippude $u$ ja $v$ vahel on serv, siis $\mathrm{dist}[u][v]$ ja $\mathrm{dist}[v][u]$ on selle serva kaal. Kui $u$ ja $v$ vahel serva pole, siis seame $\mathrm{dist}[u][v] = \mathrm{dist}[v][u] = \infty$ (programmeerides võib lõpmatuse asendada mõne hästi suure arvuga). Lisaks seame $\mathrm{dist}[u][u] = 0$ iga $u$ korral.

Kujutame ette ülesande variatsiooni, kus alguses ei ole ühtegi tippu lubatud kasutada teekonnal vahetipuna. Sel juhul ongi ülalkirjeldatud $\mathrm{dist}[u][v]$ lühim teekond tipust $u$ tippu $v$. Seejärel hakatakse ükshaaval tippe lubama ka vahepeatustena: esialgu on vahetipuna lubatud kasutada ainult tippu 1, seejärel tippe 1 ja 2 ja nii edasi. Igal sellisel "etapil" arvutame maatriksi $\mathrm{dist}[u][v]$ üle.

Oletame niisiis, et hetkel tähistab $\mathrm{dist}[u][v]$ lühimat teekonda tipust $u$ tippu $v$ eeldusel, et vahepeatustena tohib kasutada ainult tippe $1, 2, \ldots, k - 1$. Nüüd hakatakse lubama ka tipu $k$ vahepeatusena kasutamist ning peame maatriksi väärtused üle arvutama.

Mis saab muutuda? Meil on kaks võimalust:

• Lühim teekond $u \leadsto v$ (mis võib vahepeatustena kasutada tippe $1 \ldots k$) ei läbi tippu $k$. Lühima sellise teekonna pikkus on (vana) $\mathrm{dist}[u][v]$.
• Lühim teekond $u \leadsto v$ (mis võib vahepeatustena kasutada tippe $1 \ldots k$) läbib tippu $k$. Sel juhul koosneb see teekond kahest osast: esimese pikkus on (vana) $\mathrm{dist}[u][k]$ ja teise pikkus (vana) $\mathrm{dist}[k][v]$.

for (int k = 1; k <= n; k++)
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

Seda algoritmi nimetataksegi Floydi-Warshalli algoritmiks. Ülalkirjeldatud selgitusest lähtudes peaks olema selge, et muutujate i, j ja k järjekord for-tsüklites on väga oluline: kui need for-tsüklid ümber järjestada, siis algoritm korrektselt ei toimi.

Jooksvalt sidususe kontrollimine

Graaf on sidus (connected), kui igast tipust leidub mööda servi teekond igasse teise tippu.

Alati võime graafi tükeldada sidususkomponentideks (connected component) — sidusateks komponentideks, kusjuures komponentide vahel servi pole.

Uurime ülesannet, kus on vaja jooksvalt kontrollida, kas graafis leidub teekond etteantud tippude vahel.

Rõhutame, et tegu on jooksva kontrollimisega: ei ole ette teada, missugused servad tulevikus ette tulevad ega missuguste tippude kohta küsitakse. Paljudes ülesannetes ei ole jooksva informatsiooni haldamine vajalik: sellisel juhul ei ole niisugust masinavärki vaja ja ülesande võib lahendada tavalise laiuti või sügavuti läbimisega. See on eriti mõistlik, kui lisaks sidususele on vaja hallata keerulisemat informatsiooni.

Baaslahendus

Idee: igast tipust on nooleke mingisse tippu. Moodustuvad puud. Teeme nii, et need puud vastaksid täpselt sidususkomponentidele.

// alguses seatakse parent[u] = u iga u korral

// mööda noolekesi üles minemine
int find (int u) {
  if (u == root[u])
    return u;
  return find(root[u]);
}

void merge (int u, int v) {
  u = find(u); // leiame u ja v juured puus
  v = find(v);

  root[u] = v;
}

Niisugust andmestruktuuri nimetatakse union-find (sest andmestruktuur toetab just neid kahte operatsiooni) või disjoint set union (sest andmestruktuur modelleerib lõikumatute hulkade süsteemi). Eesti keeles on kasutatud terminit klassimets.

Probleem: selle algoritmi keerukus on $O(NQ)$, mis on liiga aeglane. Põhimõtteliselt on võimalik, et iga päring võtab $O(N)$ aega. Probleem tekib siis, kui osad puud muutuvad väga kõrgeks.

Seetõttu vajame ülesande efektiivseks lahendamiseks veel midagi. Allpool toome välja kaks meetodit, millest võib kasutada emba-kumba.

Optimisatsioon: union by rank

Idee: suuname puid ühendades noolekese alati madalama puu juurest kõrgema puu juurde. Näiteks tuleks suunata nii, nagu on näidatud alloleval parempoolsel pildil, aga mitte nii, nagu näidatud alloleval vasakpoolsel pildil.

See idee on võimsam, kui võiks arvata. Tasub arutleda nii: puu kõrgus saab kasvada ainult siis, kui me ühendame omavahel kaks sama kõrgusega puud. Nüüd paneme tähele:

• Selleks, et teha puud kõrgusega 0, on vaja 1 tippu.
• Selleks, et teha puud kõrgusega 1, on vaja kaht puud kõrgusega 0 ehk vähemalt 2 tippu.
• Selleks, et teha puud kõrgusega 2, on vaja kaht puud kõrgusega 1 ehk vähemalt 4 tippu.
• Selleks, et teha puud kõrgusega 3, on vaja kaht puud kõrgusega 2 ehk vähemalt 8 tippu.
• ...
• Selleks, et teha puud kõrgusega 20, on vaja kaht puud kõrgusega 19 ehk vähemalt 1048576 tippu.

Optimisatsioon: path compression

Idee: raiskame palju aega, kui läheme iga kord mööda samu noolekesi üles. Kui peame üles minema, suuname pärast need läbitud noolekesed otse üles. See tähendab järgmist muudatust find-meetodis:

int find (int u) {
  if (u != root[u])
    root[u] = find(root[u]);
  return root[u];
}

Path compression keerukuse analüüs on pisut pikem; seda me käesolevas loengus ei vaata, aga selle kohta võib lugeda näiteks siit. Optimeerimismeetodite keerukused võtab kokku allolev tabel.

DSU nooltel täiendava informatsiooni hoidmine

On mõned ülesanded, mida saab sarnasel viisil lahendada, aga kus on DSU nooltel veel mingit informatsiooni vaja meeles pidada. Teeme ühe sellise ülesande läbi.

Ülesande lahendamiseks vajame kahealuselise graafi mõistet. Kahealuseliseks nimetatakse graafi, kus ei leidu paaritu pikkusega tsüklit. Samaväärselt võib kahealuselise graafi defineerida kui graafi, mille tipud saab värvida kahe värviga nii, et ükski serv ei ühenda sama värvi tippe.

1. Kui $u$ ja $v$ on erinevates komponentides, siis teekonda ei leidu.
2. Kui $u$ ja $v$ on paaritu tsükliga komponendis, siis teekond leidub.
3. Kui $u$ ja $v$ on kahealuselises komponendis ja sama värvi, siis teekonda ei leidu.
4. Kui $u$ ja $v$ on kahealuselises komponendis ja eri värvi, siis teekond leidub.

Seega on meil vaja täiendada union-find andmestruktuuri nii, et oskaksime tuvastada, kas kaks tippu on "sama värvi". Idee on järgmine: hoiame iga tipu kohta meeles, kas ta on oma vanemaga sama värvi (joonistel sinised nooled) või eri värvi (joonistel punased nooled).

Minimaalne toesepuu

Põhimõisted ja ülesande püstitus

Puuks (tree) nimetatakse sidusat tsükliteta graafi. Olgu meil sidus graaf. Valime selle servade seast välja mõned servad nii, et nendest moodustuks puu, mis ühendab kõik graafi tipud. Mistahes niimoodi saadud puud nimetatakse toesepuuks (või aluspuuks, spanning tree).

Näide ühe graafi minimaalsest toesepuust:

Kruskali algoritm minimaalse toesepuu leidmiseks

Võistlusprogrammeerimises kõige kasulikum algoritm toesepuu leidmise algoritm on nn Kruskali algoritm. On ka teisi, nt. Primi ja Boruvka algoritmid, aga praktika on näidanud, et enamus olukordades on Kruskali algoritm kõige mõistlikum; seda on ka väga lihtne implementeerida.

Algoritm ise on järgmine:

1. sorteerime servad kaalu järgi kasvavalt;
2. käime läbi kõik servad $uv$; iga serva kohta:
   • kontrollime, kas $u$ ja $v$ on samas sidususkomponendis (kasutame DSU-d);
   • kui ei ole, siis lisame vastusesse serva $uv$; seejuures kasutame jälle DSU-d, et nende vahele serva lisada.

Algoritmi korrektsuse tõestamise jätame lugejale ülesandeks. Lihtsam on alustada juhust, kus graafi kõikidel servadel on erinevad kaalud. Oletame, et leidub mõni väikesema kaaluga toesepuu ja vaatleme vähima kaaluga serva, mis selles toesepuus on, kuid Kruskali algoritmi leitud puus ei ole. Kuidas on võimalik, et Kruskali algoritm seda serva ei valinud? Sarnaseid ideid kasutades on ka võimalik tõestada, et Kruskali algoritm on "võimeline" leidma kõik erinevad minimaalsed toesepuud (samakaalulisi servi ümber järjestades).

Viimaks analüüsime algoritmi keerukust.

• Sorteerimine võtab $O(M \log M)$.
• Iga serva jaoks teeme üks või kaks DSU päringut; kokku $O(M)$ päringut ja keerukus seega $O(M \alpha(M))$.