Traversering av grafer

Å traversere en graf er å besøke nodene du har oppdaget. I starten har du bare oppdaget startnoden, men hver gang du besøker en node, oppdager du naboene dens. Slik når du alle nodene som kan nås fra startnoden. Traversering er nyttig i seg selv, og mange grafalgoritmer bygger på den. Læreboka kaller traversering søk (search), og derfor heter de to algoritmene bredde-først-søk og dybde-først-søk.

Grafrepresentasjoner

En graf $G = (V, E)$ har nodene $V$ og kantene $E$. I en rettet graf går kanten $(u, v)$ fra $u$ til $v$, og $v$ er en ut-nabo av $u$. I en urettet graf går kanten begge veier. Kjøretiden til en grafalgoritme har to parametre, og inne i asymptotisk notasjon står $V$ for $|V|$ og $E$ for $|E|$, så $O(V + E)$ betyr $O(|V| + |E|)$.

Med nabolister har hver node sin egen liste: $G.\mathit{Adj}[u]$ inneholder ut-naboene til $u$. Grafen er altså en tabell med én liste per node, og ikke én liste. I en rettet graf står kanten $(u, v)$ bare i lista til $u$, så listene har til sammen $|E|$ elementer ($\sum_{u \in V} |G.\mathit{Adj}[u]| = |E|$). I en urettet graf står den i begge listene, og summen blir $2|E|$. Plassen er $\Theta(V + E)$. En nabomatrise er en $|V| \times |V|$-tabell $A$ der $a_{uv} = 1$ når $(u, v)$ er en kant, og 0 ellers. Den tar $\Theta(V^2)$ plass uansett hvor mange kanter grafen har, og for en urettet graf er den symmetrisk.

En vektet graf lagrer vekten $w(u, v)$ sammen med $v$ i lista til $u$, eller som $a_{uv}$ i matrisen. Tabellen viser hva de vanligste operasjonene koster.

Nabomatrisen egner seg til direkte oppslag, og nabolistene til traversering. Det sies ofte at matrisen er raskere og listene tar mindre plass, men det stemmer bare delvis. Listene tar mindre plass når grafen har få kanter. Har den nær $|V|^2$ kanter, tar begge $\Theta(V^2)$. Algoritmene i læreboka bruker nabolister med mindre de trenger raske oppslag, og listene kan gjerne byttes ut med hashtabeller.

Traversering

Start i node 5 i figur 1, med 5 alene på en liste. Du tar 5 av lista, besøker den og fører opp naboene 3 og 4. Du besøker 3 og fører opp 6. Når du besøker 4, står 6 alt på lista. Du besøker 6, og lista er tom. Nodene 5, 3, 4 og 6 er besøkt, og 1 og 2 kan ikke nås fra 5.

Lista er en huskeliste med noder som er oppdaget, men ikke besøkt. Å besøke en node er å ta den av lista og føre opp naboene den har. Når lista er tom, er alle nodene som kan nås fra startnoden, besøkt. En node på en sti fra startnoden føres nemlig opp senest når noden foran den på stien besøkes, og alt som føres opp, tas av lista før den er tom. Hvilken node som tas av lista først, bestemmer hvilken traversering det blir.

Algoritmene i læreboka holder styr på hvilke noder som er oppdaget og besøkt, med farger. En node er hvit før den er oppdaget, grå når den er oppdaget, men ikke ferdig, og svart når den er ferdig. Uten fargene ville en sykel sendt traverseringen rundt og rundt. Med dem behandles hver node én gang, på samme måte som memoisering løser hver delinstans én gang. Når $v$ oppdages langs kanten $(u, v)$, får den forgjengeren $v.\pi = u$. Kantene $(v.\pi, v)$ danner et traverseringstre med startnoden som rot.

Dybde-først-søk

Dybde-først-søk (DFS) går alltid videre fra den nyeste noden den har oppdaget. DFS-Visit$(G, u)$ gjør $u$ grå og går gjennom naboene. Møter den en hvit nabo $v$, setter den $v.\pi = u$ og kaller seg selv på $v$ med en gang. Først når alle naboene er sett, blir $u$ svart. Kallstakken er huskelista. DFS$(G)$ farger alle nodene hvite og kaller DFS-Visit fra hver node som fortsatt er hvit, i rekkefølge. Den når dermed hele grafen, og hvert kall fra hovedløkka gir et nytt tre. Til sammen blir trærne en dybde-først-skog.

DFS gir hver node to tider fra en felles teller time: starttiden $u.d$ når $u$ oppdages og blir grå, og sluttiden $u.f$ når $u$ er ferdig og blir svart. Telleren øker med 1 hver gang, så tidene er heltallene fra 1 til $2|V|$, og $u.d < u.f$.

def dfs(G):  # G[u] er lista med ut-naboene til u
  color = {u: "white" for u in G}
  pi = {u: None for u in G}
  d, f = {}, {}  # u.d og u.f er d[u] og f[u]
  time = 0

  def dfs_visit(u):
      nonlocal time
      time += 1
      d[u] = time
      color[u] = "gray"
      for v in G[u]:
          if color[v] == "white":
              pi[v] = u
              dfs_visit(v)
      time += 1
      f[u] = time
      color[u] = "black"

  for u in G:
      if color[u] == "white":
          dfs_visit(u)
  return d, f, pi

DFS-Visit kalles én gang per node, for den kalles bare på hvite noder, og noden blir grå med en gang. Hvert kall går gjennom nabolista én gang, så alle kallene undersøker til sammen $|E|$ kanter i en rettet graf. Med initialiseringen blir kjøretiden $\Theta(V + E)$ ($\Theta(V) + \sum_{u \in V} \Theta(1 + |G.\mathit{Adj}[u]|) \allowbreak = \Theta(V + E)$).

Parentesteoremet og hvit-sti-teoremet

Skriv «(u» når $u$ oppdages og «u)» når $u$ er ferdig. Da blir parentesene riktig nøstet. Kallet på en node ligger inni kallene på forfedrene, så noden oppdages etter dem og blir ferdig før dem.

I DFS-stepperen er hver node en stolpe fra $u.d$ til $u.f$, og to stolper overlapper bare når den ene ligger inni den andre. $v$ er altså en ekte etterkommer av $u$ hvis og bare hvis $u.d < v.d < v.f < u.f$ ($u.d < v.d < v.f < u.f$).

Er $v$ en etterkommer, oppdages den etter $u$, og det gjør alle nodene på trestien mellom dem, så de er hvite ved $u.d$. Omvendt, la $v$ være den første noden på en hvit sti fra $u$ som ikke blir en etterkommer. Noden før $v$ på stien er $u$ eller en etterkommer av $u$, og den blir ikke ferdig før den har undersøkt kanten til $v$. Da oppdages $v$ mens $u$ er grå, og etter parentesteoremet er den en etterkommer likevel.

Kantklassifisering

DFS deler kantene i fire typer etter dybde-først-skogen. Fargen til $v$ når kanten $(u, v)$ undersøkes, avgjør typen.

En grå node ligger på kallstakken, så den er en forfader til $u$, og kanten lukker en sykel. Omvendt, har grafen en sykel, la $v$ være den første noden i sykelen som DFS oppdager, og $u$ noden foran $v$ i sykelen. Ved $v.d$ er resten av sykelen en hvit sti fra $v$ til $u$, så $u$ blir en etterkommer av $v$ etter hvit-sti-teoremet, og kanten $(u, v)$ blir en bakoverkant. En rettet graf har altså en sykel hvis og bare hvis DFS finner en bakoverkant.

I en urettet graf er hver kant en tre-kant eller en bakoverkant. Er $u.d < v.d$, er $v$ hvit ved $u.d$, og kanten er en hvit sti fra $u$ til $v$. Etter hvit-sti-teoremet blir $v$ da en etterkommer av $u$ og ferdig mens $u$ er grå. Undersøkes kanten første gang fra $u$, er $v$ hvit, og kanten blir en tre-kant. Undersøkes den første gang fra $v$, er $u$ fortsatt grå, og kanten blir en bakoverkant.

Eksamensoppgave Start- og sluttider på en sti

Ordinær eksamen, desember 2024, oppgave 6

Utfør DFS på grafen nedenfor, slik at første kall til DFS-Visit starter i node $y$. Hva blir $v.d$ og $v.f$ (discovery time og finish time) for hver node $v$?

Oppgi svaret som to lister med 4 tall på hver sin linje, som f.eks.:

1, 2, 4, 7
5, 6, 3, 8

Første linje er $x.d$, $y.d$, $z.d$, $w.d$, i rekkefølge, og andre linje er $x.f$, $y.f$, $z.f$, $w.f$.

Hint: Husk at DFS starter en ny dybde-først-traversering med DFS-Visit fra hver eneste node som ikke allerede er besøkt.

Vis løsning Skjul løsning

$y$ oppdages først, med $y.d = 1$. Kanten $(y, z)$ gir $z.d = 2$, og $(z, w)$ gir $w.d = 3$. $w$ har ingen kanter ut og blir ferdig med $w.f = 4$, og så blir $z.f = 5$ og $y.f = 6$. Hovedløkka i DFS fortsetter med nodene som er hvite, og det er bare $x$. Den får $x.d = 7$, kanten $(x, y)$ går til en svart node, og $x.f = 8$.

Svar

7, 1, 2, 3 og 8, 6, 5, 4.

Topologisk sortering

En rettet asyklisk graf, en DAG, er en rettet graf uten sykler. En topologisk sortering av en DAG er en rekkefølge av nodene der alle kantene peker fremover: for hver kant $(u, v)$ kommer $u$ før $v$. Kantene kan være avhengigheter, som at buksa må på før skoene. Har grafen en sykel, finnes ingen slik rekkefølge, for en av kantene i sykelen må peke bakover.

En klassisk metode tar ut en node uten inn-kanter, fjerner den fra grafen og gjentar. Topological-Sort bruker i stedet DFS. Hver gang en node blir ferdig, settes den først i en lenket liste, så lista ender opp sortert etter synkende sluttid. Innsettingen tar konstant tid, og alt tar $\Theta(V + E)$.

Synkende sluttid er riktig fordi $v.f < u.f$ for hver kant $(u, v)$ ($(u, v) \in E \;\Rightarrow\; v.f < u.f$). Når DFS undersøker kanten, er $v$ hvit, svart eller grå. Er $v$ hvit, blir den en etterkommer av $u$ og ferdig før $u$. Er $v$ svart, er den alt ferdig. Er $v$ grå, er kanten en bakoverkant, og grafen har en sykel, så i en DAG er $v$ aldri grå. Argumentet bruker ingenting om rekkefølgen i hovedløkka og nabolistene. En annen rekkefølge kan gi en annen sortering, men den er like riktig.

Koden trenger ikke tidene, bare rekkefølgen nodene blir ferdige i.

from collections import deque

def topological_sort(G):
  color = {u: "white" for u in G}
  order = deque()  # appendleft setter inn først i O(1)

  def visit(u):
      color[u] = "gray"
      for v in G[u]:
          if color[v] == "white":
              visit(v)
      color[u] = "black"
      order.appendleft(u)

  for u in G:
      if color[u] == "white":
          visit(u)
  return list(order)

Sterke komponenter

En urettet graf er sammenhengende når det finnes en sti mellom hvert par av noder, og de sammenhengende komponentene er de største delene som er sammenhengende. DFS finner dem direkte: hvert dybde-først-tre er én komponent, for traverseringen fra en node stopper når det ikke er flere kanter å følge.

En rettet graf er sterkt sammenhengende når det for hvert par $u$ og $v$ finnes en sti fra $u$ til $v$ og en sti fra $v$ til $u$. De sterke komponentene er de største mengdene av noder der alle kan nå alle. Kollapser du hver komponent til én node, får du komponentgrafen. Den er en DAG, for en sykel mellom to komponenter ville gjort dem til én.

Kjører du DFS rett på $G$, kan et tre gå fra én komponent og inn i en annen. Starter DFS i en komponent der alle nodene er hvite og alle kantene ut av komponenten går til svarte noder, blir treet nøyaktig den komponenten. Du trenger derfor startnoder i en rekkefølge der hver komponent bare har kanter ut til komponenter som alt er besøkt. Sluttidene fra en første runde med DFS på $G$ gir en slik rekkefølge, men for den transponerte grafen og ikke for $G$ selv.

La sluttiden til en komponent være den høyeste sluttiden i den. Går en kant i $G$ fra komponent $C$ til en annen komponent $C'$, har $C$ høyere sluttid enn $C'$. Oppdager DFS en node i $C$ først, når den hele $C'$ langs hvite stier før den noden blir ferdig. Oppdager den en node i $C'$ først, kan den ikke nå $C$ derfra, for da ville $C$ og $C'$ vært én komponent. Da er hele $C'$ ferdig før $C$ blir oppdaget.

Komponenten med høyest sluttid har derfor ingen kanter inn fra andre komponenter i $G$. Noden med lavest sluttid ligger derimot ikke nødvendigvis i en komponent uten kanter ut. Med kantene $(a, b)$, $(b, a)$ og $(a, c)$ og DFS fra $a$, som følger $(a, b)$ først, blir $b$ ferdig først, men komponenten $\{a, b\}$ har en kant ut til $c$. Snur du alle kantene, får du den transponerte grafen $G^{\mathrm T}$, og der har komponenten ingen kanter ut. $G$ og $G^{\mathrm T}$ har de samme sterke komponentene, for hver sti i den ene er en sti baklengs i den andre. Strongly-Connected-Components kjører derfor en runde til, på $G^{\mathrm T}$.

1. DFS på $G$

   Kjør DFS på $G$ for å finne sluttiden $u.f$ for hver node.

2. Snu kantene

   Lag $G^{\mathrm T}$. Med nabolister tar det $\Theta(V + E)$.

3. DFS på $G^{\mathrm T}$

   Kjør DFS på $G^{\mathrm T}$, men la hovedløkka ta nodene etter synkende $u.f$ fra første runde.

4. Les av trærne

   Hvert dybde-først-tre fra andre runde er én sterk komponent.

Andre runde starter i noden med høyest sluttid, og DFS besøker nøyaktig komponenten dens. Hver ny startnode har høyest sluttid av nodene som er igjen, og i $G^{\mathrm T}$ fører kantene ut av komponenten dens bare til komponenter som alt er svarte. Hvert tre blir dermed én komponent, og hele algoritmen tar $\Theta(V + E)$.

Koden bruker topological_sort ovenfor som første runde. Grafen kan ha sykler, så lista er ikke en topologisk sortering, men den har fortsatt nodene etter synkende sluttid.

def transpose(G):
  GT = {u: [] for u in G}
  for u in G:
      for v in G[u]:
          GT[v].append(u)
  return GT

def strongly_connected_components(G):
  order = topological_sort(G)
  GT = transpose(G)
  color = {u: "white" for u in G}
  components = []

  def visit(u, component):
      color[u] = "gray"
      component.append(u)
      for v in GT[u]:
          if color[v] == "white":
              visit(v, component)
      color[u] = "black"

  for u in order:
      if color[u] == "white":
          component = []
          visit(u, component)
          components.append(component)
  return components

Bredde-først-søk

Bredde-først-søk (BFS) bruker en FIFO-kø $Q$ som huskeliste, så nodene som ble oppdaget først, besøkes først. BFS$(G, s)$ farger alle nodene hvite med $u.d = \infty$, gjør startnoden $s$ grå med $s.d = 0$ og legger den i køen. Så lenge køen ikke er tom, tas den første noden $u$ ut. Hver hvite nabo $v$ blir grå med $v.d = u.d + 1$ og $v.\pi = u$ og settes bakerst i køen. Når alle naboene er sett, blir $u$ svart. I BFS teller $u.d$ kanter fra $s$ og er ikke en starttid som i DFS.

Avstanden $\delta(s, v)$ er det minste antallet kanter på en sti fra $s$ til $v$, og $\infty$ hvis $v$ ikke kan nås. Traverseringen går ut fra $s$ lag for lag. Hver kant $(u, v)$ som gjør $v$ grå, gir $v.d = u.d + 1$, så $v.d$ er lengden av stien fra $s$ til $v$ i bredde-først-treet. Ingen sti er kortere enn $\delta(s, v)$, så $v.d \ge \delta(s, v)$.

Køen er FIFO, og en node som settes inn, får $d$ én høyere enn noden som ble tatt ut. Nodene tas derfor ut i stigende $d$, og køen har aldri mer enn to verdier av $d$.

At $v.d \le \delta(s, v)$, viser du med induksjon på avstanden $k$. Har alle nodene med avstand $k$ fått $d = k$, har en node $v$ med $\delta(s, v) = k + 1$ en kant inn fra en node $u$ med avstand $k$. Når $u$ tas ut, er $v$ hvit og får $v.d = k + 1$, eller den er alt oppdaget av en node som ble tatt ut før $u$, og da er $v.d \le u.d + 1 = k + 1$.

Når BFS er ferdig, er altså $v.d = \delta(s, v)$ ($v.d = \delta(s, v)$). Forgjengerkantene danner et bredde-først-tre, og stien i treet fra $s$ til $v$ er en korteste vei. Print-Path skriver den ut ved å følge forgjengerne bakover fra $v$ og skrive ut nodene på vei ut av rekursjonen.

from collections import deque

def bfs(G, s):
  color = {u: "white" for u in G}
  d = {u: float("inf") for u in G}
  pi = {u: None for u in G}
  color[s] = "gray"
  d[s] = 0
  Q = deque([s])
  while Q:
      u = Q.popleft()
      for v in G[u]:
          if color[v] == "white":
              color[v] = "gray"
              d[v] = d[u] + 1
              pi[v] = u
              Q.append(v)
      color[u] = "black"
  return d, pi

def print_path(pi, s, v):
  if v == s:
      print(s)
  elif pi[v] is None:
      print("ingen sti fra", s, "til", v)
  else:
      print_path(pi, s, pi[v])
      print(v)

Ta grafen fra forelesningen, den første grafen i begge stepperne. DFS fra node 1 når node 4 via 2, 3, 7 og 8, fem kanter fra 1, mens BFS når den med to, langs $(1, 2)$ og $(2, 4)$. DFS følger én sti så langt den kan og kan oppdage en node via en omvei før den undersøker den korte kanten, så dybde-først-treet gir ikke nødvendigvis korteste vei.

Hver node settes i køen høyst én gang, for den blir grå idet den settes inn, og nabolista til en node gås gjennom én gang, når noden tas ut. BFS bruker derfor $O(V + E)$. DFS starter fra alle nodene og bruker alltid $\Theta(V + E)$, mens BFS bare starter i $s$. Har $s$ ingen kanter ut, er det bare initialiseringen igjen, og den tar $\Theta(V)$.

Traversering med andre huskelister

Huskelista i BFS er køen $Q$. Nodene er hvite før de settes inn, grå mens de står i køen og svarte etterpå. FIFO-køen gjør at BFS finner korteste veier, men traverseringen besøker alle nodene som kan nås fra $s$ uansett hvilken node som tas ut i hver runde.

Bytter du bare køen med en stakk, blir traverseringen ikke DFS-Visit. Ta kantene $(s, a)$, $(s, b)$, $(a, b)$ og $(b, a)$. BFS med stakk gjør $a$ og $b$ grå idet $s$ legger dem på stakken, så begge får forgjengeren $s$, og når $b$ besøkes, er $a$ alt grå. DFS-Visit går fra $s$ til $a$ og kaller seg selv på $b$ fra $a$, så $b$ får forgjengeren $a$. DFS-Visit gjør en node grå først når kallet på den starter, og ikke når noden oppdages. Versjonen under venter på samme måte og gjør en node grå først når den kommer øverst i stakken.

Løkka ser på noden øverst i stakken. Er den hvit, blir den grå, og alle de hvite naboene legges på stakken. Er den ikke hvit, er alt som ble lagt over den, tatt av igjen, så den blir svart og tas av. En node kan ligge i stakken flere ganger. Den besøkes fra kopien som ble lagt på sist, og forgjengeren er noden som la den der. Naboene besøkes i motsatt rekkefølge av DFS-Visit, og stakken kan bli $O(E)$ lang.

def iter_dfs_visit(G, s):
  color = {u: "white" for u in G}
  pi = {u: None for u in G}
  S = [s]
  while S:
      u = S[-1]
      if color[u] != "white":
          color[u] = "black"
          S.pop()
          continue
      color[u] = "gray"
      for v in G[u]:
          if color[v] == "white":
              pi[v] = u
              S.append(v)
  return pi

BFS prioriterer de eldste nodene i huskelista, og DFS de nyeste. Med en prioritetskø kan du prioritere etter noe annet, og da får du andre algoritmer. Prims algoritme for minimale spenntrær og Dijkstras algoritme for korteste vei er traverseringer av dette slaget, der nøklene i køen oppdateres underveis. Med en binær haug koster hver køoperasjon $O(\lg V)$, og traverseringen tar $O(E \lg V)$ når alle nodene kan nås fra $s$.

Sjekk deg selv