BFS kontra DFS: välj rätt traversal
↑BFS och DFS undersöker båda samband i grafer men prioriterar olika noder. BFS går nivåvis med en kö, medan DFS följer en gren först med stack eller rekursiva anrop. Skillnaden syns tydligt när grafen innehåller flera alternativa vägar.
Jämför på samma graf
Section titled “Jämför på samma graf”Besökta: –
Queue: –
Grannar behandlas i alfabetisk ordning. DFS använder omvänd push-ordning för att besöka den alfabetiskt första grannen först.
Välj BFS och stega från A. Återställ sedan och välj DFS. Färgade noder är besökta, och strukturen visar väntande arbete. Besöksordningen är förutsägbar här eftersom grannordningen är alfabetisk. Andra grannordningar kan ge andra giltiga resultat.
| Fråga | BFS | DFS |
|---|---|---|
| Datastruktur | FIFO-kö | LIFO-stack / rekursion |
| Prioritet | Minsta antal kanter först | Djupare gren först |
| Kortaste väg i antal kanter | Ja, i oviktad graf med föräldraspårning | Ingen generell garanti |
| Tid med grannlistor | O(V + E) | O(V + E) |
| Extra minne | O(V) visited + kö | O(V) visited + stack |
| Vanliga användningar | Kortaste oviktad väg, nivåer | Nåbarhet, backtracking, cykler, topologisk sortering |
Hur skiljer sig minnet?
Section titled “Hur skiljer sig minnet?”Båda kan använda O(V) extra minne i värsta fall, men väntestrukturerna ser olika ut. På ett brett träd kan BFS lagra nästan en hel nivå. Rekursiv DFS på ett träd behåller en aktiv väg och använder O(h) anropsstack, plus eventuella resultat. I allmänna grafer tar visited-set ofta O(V). DFS använder alltså inte alltid mindre minne.
Samband med träd
Section titled “Samband med träd”Preorder, inorder och postorder är DFS-ordningar på binära träd. Nivåordning är BFS på ett träd. Inorder är inte en allmän graftraversering eftersom grafer saknar en given vänster-/högerstruktur.
Varför vikter ändrar frågan
Section titled “Varför vikter ändrar frågan”BFS minimerar antalet kanter, inte en godtycklig total kostnad. Om A-B kostar 100 och vägen A-C-B kostar 2 kan BFS välja direktvägen trots högre kostnad. För viktade vägar med icke-negativa kostnader kan Dijkstra passa; A* använder även en heuristik.
Övning: Rita en graf med två vägar från A till D, en med två kanter och en med fyra. Testa båda algoritmerna för hand. Kan DFS hitta D först via den längre vägen?
Referenser: GeeksforGeeks BFS och DFS, W3Schools graftraversering.