Du saugojimo būdai, dvi paieškos

Pirma — kaip grafą laikyti. Yra du būdai ir jie nėra lygiaverčiai.

Gretimumo sąrašas

Kiekvienai viršūnei — jos kaimynų sąrašas:

adj[0] = [1, 47]
adj[1] = [0, 2]
adj[2] = [1]
...

Atmintis: O(V + E). Kaimynų peržiūra: tiek žingsnių, kiek kaimynų.

Gretimumo matrica

Vienas bitas kiekvienai viršūnių porai, nesvarbu, ar briauna yra:

     0  1  2  3
  0  .  1  .  .
  1  1  .  1  .
  2  .  1  .  .
  3  .  .  .  .

Atmintis: O(V²). Klausimas „ar yra briauna A–B?" — vienas žingsnis, be paieškos. Bet kaimynų peržiūra — V žingsnių, net jei kaimynų nė vieno.

Antroje pamokoje skaičiavai, kiek transit kainuotų griežinių antraštės. Tai buvo argumentas, ne matavimas, ir tos pamokos spąstai tai pasakė tiesiai. Septintame šios pamokos žingsnyje tą patį klausimą pamatuosi.

BFS — paieška į plotį

BFS(from, to):
    prev[*] ← −1;  seen[from] ← true
    queue ← [from]
    kol queue netuščia:
        v ← queue PRIEKIS            // ← eilė
        jei v = to: grąžink kelią
        kiekvienam kaimynui w:
            c.Hit()
            jei seen[w]: praleisk
            seen[w] ← true; prev[w] ← v
            queue ← queue + w

Eilė aplanko viršūnes sluoksniais: pirma visus, esančius per vieną perėjimą, tada visus per du, ir taip toliau. Todėl pirmą kartą pasiekus to, tai būtinai yra trumpiausias kelias perėjimais — trumpesnio sluoksnio jau nebeliko.

DFS — paieška į gylį

DFS(from, to):
    prev[*] ← −1
    stack ← [from]
    kol stack netuščias:
        v ← stack GALAS              // ← stekas; VIENINTELIS skirtumas
        jei seen[v]: praleisk
        seen[v] ← true
        jei v = to: grąžink kelią
        kiekvienam kaimynui w:
            c.Hit()
            jei seen[w]: praleisk
            prev[w] ← v; stack ← stack + w

Palygink abu tekstus. Skiriasi viena eilutė — queue PRIEKIS prieš stack GALAS — ir viena smulkmena: DFS tikrina seen imdamas, ne dėdamas, nes ta pati viršūnė gali patekti į steką kelis kartus, kol jos eilė ateis.

Stekas eina kiek įmanoma giliau, kol atsiremia, tada grįžta atgal. Sluoksnių nėra, taigi ir jokio pažado apie ilgį.

Ir trečias variantas

DFSRecursive(v):
    seen[v] ← true
    jei v = to: rasta
    kiekvienam kaimynui w:
        jei ne seen[w]: prev[w] ← v; DFSRecursive(w)

Steko čia nėra — nes jis yra: tai kvietimų stekas. Penkta pamoka tai jau parodė ir pamatavo; šeštas žingsnis parodo, kur ta lygybė turi ribą.

Kaina

Abi paieškos aplanko kiekvieną viršūnę ne daugiau nei kartą ir kiekvieną briauną ne daugiau nei du kartus (po vieną iš kiekvieno galo). Taigi:

O(V + E) — abiem.

Sudėtingumas vienodas. Skiriasi ne kaina, o atsakymas.