Snabb
Startpunkt
Mål (Utgång)
Vägg / Hinder
Aktuell Front (DFS)
Aktuell Front (BFS)
Besökt DFS
Besökt BFS
Väg ut (DFS)
Kortaste väg (BFS)
Depth-First Search (DFS)
Utforskar så djupt som möjligt längs varje gren innan återgång (Backtracking).
Besökta Celler
0
Väglängd
-
Observera: DFS garanterar inte den kortaste vägen ut, men kan hittas snabbt i djupa labyrinter.
Breadth-First Search (BFS)
Utforskar grannar på nuvarande djup innan nästa nivå (Expanderande ringar).
Besökta Celler
0
Väglängd
-
Observera: BFS garanterar alltid den garanterat kortaste vägen i o-viktade grafer/labyrinter.
Teoretisk Jämförelse: DFS vs BFS
Depth-First Search (DFS)
- Datastruktur: Använder en Stack (Sist in, först ut - LIFO).
- Beteende: Dykers rätt ner i en väg tills det blir stopp, backar sedan ett steg och prövar nästa förgrening.
- Minnesanvändning: Ofta lägre minneskrav O(h) där h är maximalt djup.
- Kortaste vägen: Finnes sällan först. Kan hitta en omväg med fler steg.
Breadth-First Search (BFS)
- Datastruktur: Använder en Kö (Först in, först ut - FIFO).
- Beteende: Sprider sig jämnt utåt från startpunkten likt ringar på vattnet.
- Minnesanvändning: Kan kräva mer minne O(w) där w är den bredaste nivån.
- Kortaste vägen: Garanterar alltid den absolut kortaste vägen i steg räknat.