BFS vs DFS - Forskel mellem dem

Hvad er BFS?

BFS er en algoritme, der bruges til at tegne data eller søge i træer eller krydse strukturer. Algoritmen besøger og markerer effektivt alle nøgleknuder i en graf på en nøjagtig breddevis måde.

Denne algoritme vælger en enkelt node (initial- eller kildepunkt) i en graf og besøger derefter alle noder, der støder op til den valgte node. Når algoritmen besøger og markerer startknudepunktet, bevæger den sig mod de nærmeste ubesøgte knudepunkter og analyserer dem.

Når de er besøgt, er alle noder markeret. Disse iterationer fortsætter, indtil alle knudepunkterne i grafen er blevet besøgt og markeret. Den fulde form for BFS er Breadth-first-søgningen.

Hvad er DFS?

DFS er en algoritme til at finde eller krydse grafer eller træer i retning mod dybde. Udførelsen af ​​algoritmen begynder ved rodknudepunktet og udforsker hver gren, før den går tilbage. Den bruger en stak datastruktur til at huske, for at få det efterfølgende toppunkt og til at starte en søgning, når der dukker en blindgyde op i enhver iteration. Den fulde form for DFS er dybde-først-søgning.

Forskellen mellem BFS og DFS binært træ

Her er de vigtige forskelle mellem BFS og DFS.

BFS	DFS
BFS finder den korteste vej til destinationen.	DFS går til bunden af ​​et undertræ og går derefter tilbage.
Den fulde form for BFS er Breadth-First Search.	Den fulde form for DFS er Depth First Search.
Den bruger en kø til at holde styr på det næste sted at besøge.	Den bruger en stak til at holde styr på det næste sted at besøge.
BFS krydser i henhold til træniveau.	DFS krydser i henhold til trædybden.
Det er implementeret ved hjælp af FIFO-listen.	Det implementeres ved hjælp af LIFO-listen.
Det kræver mere hukommelse sammenlignet med DFS.	Det kræver mindre hukommelse sammenlignet med BFS.
Denne algoritme giver den laveste vejløsning.	Denne algoritme garanterer ikke den laveste vejløsning.
Der er ikke behov for backtracking i BFS.	Der er behov for backtracking i DFS.
Du kan aldrig blive fanget i endelige sløjfer.	Du kan blive fanget i uendelige sløjfer.
Hvis du ikke finder noget mål, skal du muligvis udvide mange noder, før løsningen er fundet.	Hvis du ikke finder noget mål, kan bladknudetilbagesporingen forekomme.

Eksempel på BFS

I det følgende eksempel på BFS har vi brugt graf med 6 hjørner.

Eksempel på BFS

Trin 1)

Du har en graf med syv tal fra 0 til 6.

Trin 2)

0 eller nul er blevet markeret som en rodnode.

Trin 3)

0 besøges, markeres og indsættes i køens datastruktur.

Trin 4)

Resterende 0 tilstødende og ubesøgte noder besøges, markeres og indsættes i køen.

Trin 5)

Gennemgående iterationer gentages, indtil alle noder er besøgt.

Eksempel på DFS

I det følgende eksempel på DFS har vi brugt en urettet graf med 5 hjørner.

Trin 1)

Vi er startet fra toppunkt 0. Algoritmen begynder med at lægge den på listen over besøgte og samtidig sætte alle dens tilstødende hjørner i datastruktur kaldet stak.

Trin 2)

Du vil besøge elementet, som er øverst i stakken, for eksempel 1 og gå til dets tilstødende noder. Det er fordi 0 allerede er besøgt. Derfor besøger vi vertex 2.

Trin 3)

Vertex 2 har et ubesøgt nærliggende vertex i 4. Derfor tilføjer vi det i stakken og besøger det.

Trin 4)

Til sidst vil vi besøge det sidste toppunkt 3, det har ingen ubesøgte tilstødende noder. Vi har gennemført gennemgangen af ​​grafen ved hjælp af DFS-algoritme.

Anvendelser af BFS

Her er applikationer af BFS:

Uvægtede grafer

BFS-algoritmen kan nemt skabe den korteste vej og et minimum spændingstræ for at besøge alle hjørnerne af grafen på kortest mulig tid med høj nøjagtighed.

P2P netværk

BFS kan implementeres til at lokalisere alle de nærmeste eller tilstødende noder i et peer-to-peer-netværk. Dette vil finde de nødvendige data hurtigere.

Webcrawlere

Søgemaskiner eller webcrawlere kan nemt bygge flere niveauer af indekser ved at bruge BFS. BFS-implementering starter fra kilden, som er websiden, og derefter besøger den alle links fra den kilde.

Netværksudsendelse

En udsendt pakke styres af BFS-algoritmen til at finde og nå alle de noder, den har adressen til.

Anvendelser af DFS

Her er vigtige anvendelser af DFS:

Vægtet graf

I en vægtet graf genererer DFS-grafgennemløb det korteste vejtræ og minimumspændingstræ.

Detektering af en cyklus i en graf

En graf har en cyklus, hvis vi fandt en bagkant under DFS. Derfor bør vi køre DFS for grafen og verificere for bagkanter.

Stifinding

Vi kan specialisere os i DFS-algoritmen til at søge en vej mellem to hjørner.

Topologisk sortering

Det bruges primært til at planlægge job fra de givne afhængigheder blandt gruppen af ​​job. I datalogi bruges det i instruktionsplanlægning, dataserialisering, logiksyntese, bestemmelse af rækkefølgen af ​​kompileringsopgaver.

Søgning efter stærkt forbundne komponenter i en graf

Det bruges i DFS-grafen, når der er en sti fra hvert eneste knudepunkt i grafen til andre resterende knudepunkter.

Løs gåder med kun én løsning

DFS-algoritmen kan nemt tilpasses til at søge i alle løsninger til en labyrint ved at inkludere noder på den eksisterende sti i det besøgte sæt.