Algoritmer og datastrukturerHjem

CMD + K

Tilbake til Algoritmer og datastrukturer

TDT4120 · Grafer

Graf-traversering — BFS & DFS

Samme graf, samme start, én bitteliten forskjell: en kø versus en stakk. Det ene valget er det som får det ene søket til å gå bredt og det andre til å gå dypt.

Klikk en node for å starte søket der.
BehandlesI frontierFerdig
ABCDEFG
1 / 64Start BFS fra A — legg den i køen.
Kø — frontierFIFO
fremst→Abakerst

En kø betjener den noden som har ventet lengst først (FIFO). Den uthevede cellen er fremst — den neste som besøkes.

Lær mer

Begge utforsker hele den nåbare delen av grafen, men datastrukturen avgjør rekkefølgen. En kø (FIFO) gir lagvis utforsking — BFS finner korteste vei i antall kanter. En stakk (LIFO) følger én gren helt ned før den backtracker — DFS gir oppdagelses- og ferdig-tider som blant annet driver topologisk sortering.

Naboene velges alltid i stigende node-rekkefølge, så kjøringen er reproduserbar. Begge er O(V + E): hver node og hver kant behandles en konstant antall ganger. Klikk en node for å starte traverseringen et annet sted.

Relaterte kapitler

8Grafer og traversering