Traversering av grafer

En graf $G = (V, E)$ er nodemengde pluss kanter. Nesten alt vi gjør med grafer starter med å utforske dem systematisk: oppdage hver node og hver kant nøyaktig så mange ganger vi trenger. Traversering er ryggraden under korteste vei, spenntrær, topologisk sortering og mye mer — så det lønner seg å ha de to grunnmønstrene, bredde-først og dybde-først, helt i fingrene.

Grafrepresentasjoner

To representasjoner dominerer, og valget styrer kjøretiden til alt vi bygger oppå.

For tynne grafer ($E \ll V^2$) er nabolista standardvalget, og det er den som gir den fine grensa $O(V+E)$ for både BFS og DFS: hver node behandles én gang og hver kant følges et konstant antall ganger.

Bredde-først-søk

BFS utforsker grafen lagvis: først kilden $s$, så alle naboene til $s$, så alle deres uoppdagede naboer, og så videre. En FIFO-kø holder fronten av oppdagede-men-ikke-ferdige noder. Fordi køen er først-inn-først-ut, behandles alltid alt på avstand $k$ før noe på avstand $k+1$ — og det er nettopp derfor dist[] ender opp med korteste vei målt i antall kanter.

def bfs(G, s):
  for u in G.V:
      dist[u] = INF
  dist[s] = 0
  Q = [s]
  while Q:
      u = Q.pop(0)
      for v in G.adj[u]:
          if dist[v] != INF:
              continue
          dist[v] = dist[u] + 1
          Q.append(v)

Dybde-først-søk

DFS gjør det motsatte av BFS: i stedet for å vifte utover, dykker det så dypt det kan langs én gren, og rygger først tilbake når grenen er kjørt tørr. Fronten er her rekursjonsstakken (LIFO). Hver node får to tidsstempler: en oppdagelsestid $d[u]$ når vi går inn i visit(u), og en ferdigtid $f[u]$ når vi forlater den. Disse tidene bærer overraskende mye struktur.

def dfs(adj, source):
  d, f = {}, {}            # oppdagelses- og ferdigtid
  time = 0

  def visit(u):
      nonlocal time
      time += 1; d[u] = time
      for v in adj[u]:
          if v not in d:
              visit(v)
      time += 1; f[u] = time

  visit(source)
  return d, f

Et nært beslektet resultat er hvit-sti-teoremet: $v$ blir en etterkommer av $u$ i DFS-treet hvis og bare hvis det på tidspunktet $d[u]$ finnes en sti fra $u$ til $v$ som bare går gjennom hvite (uoppdagede) noder. Sammen forklarer disse to hvorfor DFS-trærne fanger nøyaktig nåbarheten i grafen.

Kantklassifisering

Når DFS følger en kant $(u, v)$, kan vi klassifisere den ut fra fargen til $v$:

Topologisk sortering

I en rettet asyklisk graf (DAG) er en topologisk sortering en lineær rekkefølge av nodene slik at hver kant $(u, v)$ peker framover. Algoritmen er forbløffende enkel: kjør DFS, og legg hver node fremst i en liste når den blir ferdig. Synkende ferdigtid $f[u]$ gir nettopp en gyldig topologisk rekkefølge.

Sterkt sammenhengende komponenter

I en rettet graf er en sterkt sammenhengende komponent en maksimal mengde noder der alle kan nå alle. Standardalgoritmen kjører DFS to ganger: én gang på $G$ for å få ferdigtidene, og én gang på den transponerte grafen $G^\top$ (alle kanter snudd), der vi starter nye trær i synkende ferdigtid. Hvert tre i andre runde er én komponent. Hele jobben er fortsatt $O(V + E)$.

Ett mønster, mange algoritmer

BFS og DFS skiller seg bare i hvilken datastruktur fronten er: en FIFO-kø gir BFS, en LIFO-stakk gir DFS. Bytter vi fronten ut med en vilkårlig prioritetskø — ta alltid ut det «beste» elementet etter en nøkkel — får vi et generelt traverseringsskjelett. Velger vi nøkkelen til å være avstandsestimatet $d[v]$, faller Dijkstras algoritme rett ut av samme mønster (se korteste vei). Det er denne abstraksjonen som binder graf­algoritmene sammen.

Sjekk deg selv