5.2 BFS og DFS — traversering

Prebetingelse: s er en node i V.
Postbetingelse: hver node som kan nås fra s, har besokt = sant og
avstand lik antall kanter på den korteste veien fra s. Noder som ikke kan
nås, har besokt = usant og avstand = uendelig.

Procedure BFS(G, s)
  Input:  graf G = (V, E) som nabolister, startnode s
  Output: hver node som kan naas fra s er merket, med avstand i antall kanter
  for hver node v i V:
      v.besokt = usant
      v.avstand = uendelig
  s.besokt = sant
  s.avstand = 0
  Ko = tom ko
  Ko.settInn(s)
  while Ko er ikke tom:
      u = Ko.taUt()
      for hver nabo v av u:
          if v.besokt er usant:
              v.besokt = sant
              v.avstand = u.avstand + 1
              Ko.settInn(v)

Invarianten i én setning: køen inneholder til enhver tid bare noder fra
høyst to nabolag — først alle på avstand $d$, så alle på avstand $d+1$ — og
derfor tas nodene ut i ikke-synkende avstand fra s.

Detaljen som er lett å bomme på: noden merkes besokt når den legges
inn i køen, ikke når den tas ut. Merker du den først ved uttak, kan den
samme noden legges inn flere ganger — og da er kjøretiden ikke lenger
$O(|V| + |E|)$.

Kjøretid: $O(|V| + |E|)$. Initialiseringsløkka er $O(|V|)$; hver node
legges inn og tas ut av køen nøyaktig én gang, og for hver node ramses
naboene opp én gang, som til sammen er $O(|E|)$ over hele grafen.

I en uvektet graf gir BFS(G, s) for hver node $v$ den korteste veien
fra $s$ til $v$ målt i antall kanter. Verdien står i v.avstand.

Grunnen i én setning: køen tømmes lagvis, så en node kan ikke tas ut før
alle noder med lavere avstand er tatt ut — og den får derfor avstanden til
den første noden som nådde den.

De to grensene du må kjenne, og som spørres om:

- Bare i uvektet graf. Har kantene vekter, er det ikke lenger antall
kanter som er interessant, og bredde-først kan gi feil svar: en vei med to
kanter kan være lengre enn en vei med fem. Vektet korteste vei krever andre
verktøy, og de kommer i Del 6.
- Dybde-først gjør det ikke. Dybde-først finner en sti, men ikke
nødvendigvis den korteste — den går så dypt den kan før den snur, og kan
komme fram til en node langs en lang omvei. Å hevde at dybde-først gir
korteste vei, er et fast trekkpunkt.

Prebetingelse: u.besokt er usant, og alle noder har fått besokt
satt (det gjøres av den som kaller — se DFSFull under).
Postbetingelse: hver node som kan nås fra u gjennom umerkede noder,
har besokt = sant. Ingen andre noder er endret.

Procedure DFSVisit(G, u)
  Input:  graf G = (V, E) som nabolister, node u med u.besokt = usant
  Output: alle noder som kan naas fra u er merket besokt
  u.besokt = sant
  for hver nabo v av u:
      if v.besokt er usant:
          DFSVisit(G, v)

Grunnideen i én setning: merket settes før de rekursive kallene, så
en node aldri kan bli besøkt to ganger, og traverseringen kan ikke gå i ring
selv om grafen har sykler.

Rekursjonen har en kostnad du skal nevne: kallstakken blir like dyp som
den lengste veien traverseringen følger, altså $O(|V|)$ i verste fall. På en
graf som er en lang kjede, ligger alle nodene på stakken samtidig.

Kjøretid: $O(|E|)$ fra én node. Prosedyren har ingen løkke over $V$;
arbeidet er å gå langs kantene, og hver kant ses høyst to ganger — én gang
fra hver ende. Merk godt: dette er kjøretiden for ett kall fra én
node. Skal hele grafen dekkes, er svaret et annet — se DFSFull.

Prebetingelse: s er en node i V.
Postbetingelse: de samme nodene er merket som etter DFSVisit(G, s), og
de er besøkt i den samme rekkefølgen.

Procedure DFSIterativ(G, s)
  Input:  graf G = (V, E) som nabolister, startnode s
  Output: alle noder som kan naas fra s er merket besokt
  for hver node v i V:
      v.besokt = usant
  Stakk = tom stakk
  Stakk.leggPa(s)
  while Stakk er ikke tom:
      u = Stakk.taAv()
      if u.besokt er usant:
          u.besokt = sant
          for hver nabo v av u i omvendt rekkefolge:
              if v.besokt er usant:
                  Stakk.leggPa(v)

Grunnideen i én setning: stakken gir alltid tilbake den sist oppdagede
noden, og det er nøyaktig det et rekursivt kall gjør — bare at her ser du
stakken.

Hvorfor if u.besokt er usant gjentas ved uttak: en node kan bli lagt på
stakken av flere naboer før den blir tatt av. Uten sjekken ville den blitt
besøkt to ganger. Dette er den eneste virkelige forskjellen mot den rekursive
formen, og den er en fast kilde til feil.

Kjøretid: $O(|V| + |E|)$. Initialiseringen er $O(|V|)$, og hver kant kan
føre til høyst én legging på stakken fra hver ende, altså $O(|E|)$ leggingar
og uttak til sammen.

Prebetingelse: ingen.
Postbetingelse: hver node i V har besokt = sant, og hver node er
besøkt nøyaktig én gang.

Procedure DFSFull(G)
  Input:  graf G = (V, E) som nabolister
  Output: hver node i G er besokt noeyaktig en gang
  for hver node v i V:
      v.besokt = usant
  for hver node v i V:
      if v.besokt er usant:
          DFSVisit(G, v)

Grunnideen i én setning: hvert kall til DFSVisit fra den ytre løkka
merker nøyaktig én sammenhengende bit av grafen, og løkka fortsetter til
ingen umerkede noder er igjen.

Kjøretid: $O(|V| + |E|)$. De to løkkene over $V$ gir $|V|$-leddet, og
alle DFSVisit-kallene til sammen ser hver kant høyst to ganger, som gir
$|E|$-leddet. Merk at det ytre if gjør at hver node behandles én gang, ikke
én gang per kall.

Legg merke til én ting til: hver gang den ytre løkka faktisk starter et
kall, har den funnet en ny bit av grafen. Å telle hvor mange ganger det skjer
er derfor å telle bitene — men den oppgaven hører til
kap. 5.3, og der skrives den ut i sin helhet.

kjøres uansett hvor få kanter grafen har.
Det skarpeste eksempelet: en graf med en million noder og null kanter.
Her er $|E| = 0$. DFSVisit fra én node gjør nesten ingenting. DFSFull
bruker likevel en million steg, fordi den må innom hver eneste node. Uten
$|V|$-leddet ville påstanden vært at hele arbeidet er gratis.

Fellenote. Dette er felle #6 i bokas feilregister: å oppgi $O(|E|)$
for en algoritme som i virkeligheten går over alle nodene, eller
$O(|V| + |E|)$ for et enkelt DFSVisit-kall. Kontrollen som tar to
sekunder: har algoritmen din en løkke for hver node v i V? Da er $|V|$

med i kjøretiden. Har den det ikke, skal $|V|$ ikke stå der.
Og motsatt vei, som er like viktig: å skrive $O(|V| + |E|)$ overalt «for
sikkerhets skyld» er ikke gratis. Kjøretiden skal matche algoritmen du
faktisk skrev.