Det er flere forskjeller mellom DFS og BFS (kort svar: Begge av dem kan finne den korteste veien i den uvektede grafen). Både BFS og DFS vil gi den korteste veien fra A til B hvis du implementerte riktig.
Er korteste vei DFS eller BFS?
BFS finner den korteste veien til -destinasjonen, mens DFS går til bunnen av et undertre og går tilbake. Den fullstendige formen for BFS er Breadth-First Search, mens den fullstendige formen for DFS er Depth First Search. BFS bruker en kø for å holde styr på det neste stedet å besøke.
Kan DFS finne korteste vei i vektet graf?
Som med BFS, kan DFS brukes til å finne alle toppunktene som kan nås fra et startpunkt v, for å bestemme om en graf er koblet sammen, eller for å generere et spenntre. I motsetning til BFS, kan den ikke brukes til å finne de korteste uvektede banene.
Kan du bruke BFS for å finne den korteste veien?
Teknisk sett lar Breadth-first Search (BFS) deg ikke i seg selv finne den korteste veien, ganske enkelt fordi BFS ikke leter etter en korteste vei: BFS beskriver en strategi for å søke i en graf, men det står ikke at du må søke etter noe spesielt.
Kan vi bruke DFS i Dijkstra?
2 svar. DFS fortsetter å hoppe langs noder til den finner en sti, mens Dijkstra er mer lik en BFS bortsett fra at den holder styr på vekter (ikke alle stier har like kostnader) og vil fortsette å sjekke den korteste banenikke allerede sjekket før den når målet.