Grafer og traversering

To måter å holde på en graf

En graf er bare noder og kanter, men før vi kan kjøre en algoritme må vi velge hvordan grafen ligger i minnet, og valget påvirker både plass og fart. Tenk på et veikart: byer er noder, veier mellom dem er kanter. De fleste byer har vei til bare noen få naboer, ikke til alle andre byer. Det er en glissen graf, og den fanger vi best med en naboliste: for hver node lagrer vi en liste over nodene den har en kant til. Plassen blir proporsjonal med hvor mange kanter som faktisk finnes.

Alternativet er en nabomatrise: et rutenett med én rad og én kolonne per node, der cellen $(u,v)$ sier om kanten finnes. Oppslaget «går det en kant fra $u$ til $v$?» er da konstant tid — ett tabelloppslag. Prisen er at matrisen alltid bruker plass for alle par, uansett hvor få kanter som finnes. ƒplass for nabolister vs. nabomatrise For en glissen graf med få kanter er nabolisten langt mer kompakt; for en tett graf der nesten alle par er forbundet, jevner forskjellen seg ut, og matrisens raske oppslag kan være verdt det. I dette emnet bruker vi som regel nabolister, fordi de fleste interessante grafer er glisne.

Bredde-først-søk: ringene i vannet

Den første traverseringen utforsker grafen i ringer utover fra en startnode, som bølger fra en stein kastet i vann. Dette er bredde-først-søk (bfs). Først besøker vi kilden, så alle dens naboer (avstand 1), så alle deres ubesøkte naboer (avstand 2), og slik videre lag for lag. Nøkkelen til den lagvise rekkefølgen er en kø: vi legger noder bakerst når vi oppdager dem, og tar dem ut forfra. Fordi køen er først-inn-først-ut, tømmer vi alltid et helt lag før vi rører det neste.

I figuren starter vi i $S$. Vi farger $S$ og legger den i køen. Vi tar $S$ ut, ser på naboene $A$ og $B$, oppdager begge og legger dem i køen. Så tar vi $A$ ut og oppdager $C$ og $D$; deretter $B$, som oppdager $E$ (og ser at $D$ allerede er funnet). Lag for lag fyller vi på til hele grafen er besøkt. Hver gang vi oppdager en node noterer vi hvilken node vi kom fra — forgjengeren — og disse forgjenger-kantene utgjør til sammen et BFS-tre (de uthevede kantene i figuren).

Den store gevinsten: BFS finner korteste vei i antall kanter fra kilden til alle andre noder. Når en node oppdages for første gang, er det langs den korteste mulige stien målt i kanter, nettopp fordi vi tømmer nærmere lag før fjernere. Vi kan lese av avstanden ved å telle lag: $C$, $D$ og $E$ ligger to kanter unna $S$. I 0-indeksert stil:

BFS(graf, kilde)
    for hver node u:  besøkt[u] = false; dist[u] = uendelig
    besøkt[kilde] = true; dist[kilde] = 0
    kø = [kilde]
    while kø ikke tom
        u = kø.dequeue()              // ta forfra
        for hver nabo v av u
            if not besøkt[v]
                besøkt[v] = true
                dist[v] = dist[u] + 1
                kø.enqueue(v)          // legg bakerst
    return dist

Hver node legges i køen nøyaktig én gang, og vi ser på hver kant et konstant antall ganger. Det gir lineær kjøretid. ƒkjøretid for bfs og dfs

Dybde-først-søk: så langt det bærer

Den andre traverseringen er motsatt av temperament. dybde-først-søk (dfs) graver så dypt den kan langs én sti før den rygger tilbake og prøver en annen retning. Der BFS bruker en kø, bruker DFS en stack — eller, mer naturlig, rekursjon, som er en stack i forkledning. Vi velger en ubesøkt nabo, går dit, og gjentar; først når vi sitter fast rygger vi.

Det som gjør DFS spesielt nyttig er to tidsstempler den setter på hver node. Vi har en teller som tikker for hvert besøk. $d[u]$ er tidspunktet vi oppdager $u$ (farger den grå og går inn), og $f[u]$ er tidspunktet vi er ferdig med $u$ (alle naboene utforsket, vi farger den svart og rygger ut). Mellom $d[u]$ og $f[u]$ behandler vi hele undertreet under $u$.

DFS(graf)
    tid = 0
    for hver node u:  farge[u] = HVIT
    for hver node u
        if farge[u] == HVIT
            BESØK(u)

BESØK(u)
    tid = tid + 1;  d[u] = tid;  farge[u] = GRÅ
    for hver nabo v av u
        if farge[v] == HVIT
            forgjenger[v] = u
            BESØK(v)
    farge[u] = SVART;  tid = tid + 1;  f[u] = tid

Disse tidsstemplene er ikke vilkårlige. Parentes-teoremet sier at intervallene $[d[u],f[u]]$ for to noder enten er helt disjunkte eller nøstet inni hverandre — de overlapper aldri bare delvis. ƒparentes-teoremet Skriver du en venstreparentes når en node oppdages og en høyreparentes når den blir ferdig, får du et velformet parentesuttrykk, som ( ( ) ( ) ). At intervallet til $v$ ligger inni intervallet til $u$ betyr nøyaktig at $v$ er en etterkommer av $u$ i DFS-treet. Hvit-sti-teoremet supplerer dette: $v$ blir etterkommer av $u$ hvis og bare hvis det finnes en sti av uoppdagede (hvite) noder fra $u$ til $v$ idet $u$ oppdages. ƒhvit-sti-teoremet

I en rettet graf klassifiserer tidsstemplene dessuten kantene. En tilbakekant er en kant fra en node til en av sine forfedre i DFS-treet, og eksistensen av minst én tilbakekant er ensbetydende med at grafen inneholder en sykel. Det gir oss en rask syklustest: kjør DFS og se etter en kant til en node som er grå (under behandling).

Topologisk sortering: legg jobbene i rekkefølge

Anta at du har oppgaver med avhengigheter — du må ta forkurset før kurset, blande før du baker, kompilere modul A før modul B som bruker den. Avhengighetene danner en rettet graf, og hvis den ikke har sykler kaller vi den en dag. En topologisk sortering er en lineær oppstilling av nodene slik at hver kant peker framover: kommer kanten fra $u$ til $v$, skal $u$ stå før $v$ i rekka. ƒtopologisk sortering

I figuren peker hver pil framover når nodene står 1, 2, …, 7 fra venstre mot høyre — det er en gyldig topologisk orden. En DAG har gjerne flere gyldige ordninger; det avgjørende er at ingen kant peker bakover. En DAG har alltid minst én topologisk orden, og en graf med en sykel har ingen, for da må en node både komme før og etter seg selv.

Den elegante måten å finne en topologisk orden på er via DFS og ferdigtidene. Kjør DFS over hele grafen, og hver gang en node blir ferdig (settes svart), legg den fremst i en liste. Når DFS er ferdig, leser lista en gyldig topologisk orden. Intuisjonen: en node blir ferdig etter alle nodene den peker til, så ved å legge ferdige noder fremst havner forutsetningene foran det de muliggjør. Hele jobben tar lineær tid, akkurat som DFS selv.

Sterkt sammenhengende komponenter

I en rettet graf er det ikke nok at to noder henger sammen — retningen teller. En sterkt sammenhengende komponent (scc) er en maksimal mengde noder der alle kan nå alle andre langs rettede kanter. Innenfor en komponent kan du reise fra hvilken som helst node til hvilken som helst annen og tilbake igjen; mellom to ulike komponenter går forbindelsen høyst én vei.

SCC-er finnes med to runder DFS. Først kjører vi DFS på grafen og noterer ferdigtidene. Så snur vi alle kantene og kjører DFS på den transponerte grafen, men starter med nodene i synkende ferdigtid fra første runde. Hvert tre vi får i andre runde er nøyaktig én sterkt sammenhengende komponent. Hvorfor det virker, hviler igjen på ferdigtidene og parentes-strukturen fra DFS — den samme maskinen som ga oss topologisk sortering. Begge traverseringene koster det samme: lineært i grafens størrelse, $\Theta (V+E)$ med nabolister. Det er den gjennomgående lærdommen i dette kapittelet — så lenge vi representerer grafen som nabolister og rører hver node og kant et konstant antall ganger, er BFS, DFS, topologisk sortering og SCC alle lineære.