traversalsekvenser

Traver​salsekvenser beskriver rekkefølgen av noder som besøkes i en graf når man gjennomfører en traversering, det vil si en systematisk runde gjennom grafen. En traversalsekvens er en ordnet liste over alle noder som blir besøkt av en traverseringsalgoritme, ofte startingert av en valgt startnode. For generelle grafer må man markere noder som besøkte for å unngå gjentatte besøk i sykliske eller uavsluttede strukturer.

De mest kjente traverseringsmetodene er depth-first search (DFS) og breadth-first search (BFS). DFS følger en sti så langt som mulig før den backtracker, og gir typisk en traversalsekvens som avhenger av naboenes behandlingsrekkefølge. BFS besøker noder i stigende avstand fra startpunktet og produserer en jinlig traversalsekvens som representerer nivåvis utforskning. I trær finnes også spesialiserte sekvenser som pre-order, in-order og post-order, som brukes til ulike operasjoner og analyser av trestrukturer.

Egenskaper og begrensninger: Traversalsekvenser er i stor grad ikke unike; forskjellige implementasjoner eller naboorden kan gi forskjellige sekvenser selv for samme graf. For å oppnå effektivitet måene alltid merkes noder som besøkt. I sammenheng med sammenhengende grafer gir en riktig gjennomført traversering en fullstendig sekvens som inkluderer alle noder, med tidskompleksitet O(n + m) hvor n er antall noder og m antall kanter.

Anvendelser inkluderer bygging av spanningstrær, grafanalyse, søkeoppgaver og forberedelser til videre grafalgoritmer som topologisk sortering i passende kontekster. Se også graftraversering, DFS, BFS, og tretraverseringer for relaterte konsepter.