BFS vs DFS - Forskjellen mellom dem

Hva er BFS?

BFS er en algoritme som brukes til å grafere data eller søke i tre eller krysse strukturer. Algoritmen besøker og merker effektivt alle nøkkelnodene i en graf på en nøyaktig breddevis måte.

Denne algoritmen velger en enkelt node (initial- eller kildepunkt) i en graf og besøker deretter alle nodene ved siden av den valgte noden. Når algoritmen besøker og markerer startnoden, beveger den seg mot de nærmeste ubesøkte nodene og analyserer dem.

Når de er besøkt, er alle noder merket. Disse iterasjonene fortsetter til alle nodene i grafen har blitt besøkt og merket. Den fullstendige formen for BFS er Breadth-first-søket.

Hva er DFS?

DFS er en algoritme for å finne eller krysse grafer eller trær i dybderetning. Utførelsen av algoritmen begynner ved rotnoden og utforsker hver gren før den går tilbake. Den bruker en stabeldatastruktur for å huske, for å få det påfølgende toppunktet og for å starte et søk, når en blindvei vises i en iterasjon. Den fullstendige formen for DFS er Dybde-først-søk.

Forskjellen mellom BFS og DFS Binary Tree

Her er de viktige forskjellene mellom BFS og DFS.

BFS	DFS
BFS finner den korteste veien til destinasjonen.	DFS går til bunnen av et undertre, og går deretter tilbake.
Den fullstendige formen for BFS er Breadth-First Search.	Den fullstendige formen for DFS er Depth First Search.
Den bruker en kø for å holde styr på det neste stedet å besøke.	Den bruker en stabel for å holde styr på det neste stedet å besøke.
BFS krysser i henhold til trenivå.	DFS krysser i henhold til tredybden.
Den er implementert ved hjelp av FIFO-liste.	Den er implementert ved hjelp av LIFO-listen.
Det krever mer minne sammenlignet med DFS.	Det krever mindre minne sammenlignet med BFS.
Denne algoritmen gir den grunneste veiløsningen.	Denne algoritmen garanterer ikke den grunneste veiløsningen.
Det er ikke behov for backtracking i BFS.	Det er behov for backtracking i DFS.
Du kan aldri bli fanget i endelige løkker.	Du kan bli fanget i uendelige løkker.
Hvis du ikke finner noe mål, kan det hende du må utvide mange noder før løsningen blir funnet.	Hvis du ikke finner noe mål, kan tilbakesporingen av bladnoden forekomme.

Eksempel på BFS

I følgende eksempel på BFS har vi brukt graf med 6 toppunkter.

Eksempel på BFS

Trinn 1)

Du har en graf med syv tall fra 0 – 6.

Trinn 2)

0 eller null er merket som en rotnode.

Trinn 3)

0 besøkes, merkes og settes inn i kødatastrukturen.

Trinn 4)

Gjenværende 0 tilstøtende og ubesøkte noder besøkes, merkes og settes inn i køen.

Trinn 5)

Gjennomgående iterasjoner gjentas til alle noder er besøkt.

Eksempel på DFS

I følgende eksempel på DFS har vi brukt en urettet graf med 5 toppunkter.

Trinn 1)

Vi har startet fra toppunkt 0. Algoritmen begynner med å sette den inn i besøkslisten og samtidig sette alle tilstøtende toppunkter i data struktur kalt stack.

Trinn 2)

Du vil besøke elementet, som er på toppen av stabelen, for eksempel 1 og gå til dets tilstøtende noder. Det er fordi 0 allerede er besøkt. Derfor besøker vi toppunkt 2.

Trinn 3)

Toppunkt 2 har et ubesøkt nærliggende toppunkt i 4. Derfor legger vi det til i stabelen og besøker det.

Trinn 4)

Til slutt vil vi besøke den siste toppunktet 3, den har ingen ubesøkte tilstøtende noder. Vi har fullført kryssingen av grafen ved hjelp av DFS-algoritmen.

Applikasjoner av BFS

Her er applikasjoner av BFS:

Uvektede grafer

BFS-algoritmen kan enkelt lage den korteste veien og et minimumsspenningstre for å besøke alle toppunktene i grafen på kortest mulig tid med høy nøyaktighet.

P2P-nettverk

BFS kan implementeres for å lokalisere alle de nærmeste eller nærliggende nodene i et peer-to-peer-nettverk. Dette vil finne de nødvendige dataene raskere.

Webcrawlere

Søkemotorer eller webcrawlere kan enkelt bygge flere nivåer av indekser ved å bruke BFS. BFS-implementering starter fra kilden, som er nettsiden, og deretter besøker den alle koblingene fra den kilden.

Nettverkskringkasting

En kringkastet pakke blir guidet av BFS-algoritmen for å finne og nå alle nodene den har adressen til.

Applikasjoner av DFS

Her er viktige bruksområder for DFS:

Vektet graf

I en vektet graf genererer DFS-graftraversering det korteste banetreet og minimumspenningstreet.

Oppdage en syklus i en graf

En graf har en syklus hvis vi fant en bakkant under DFS. Derfor bør vi kjøre DFS for grafen og verifisere for bakkanter.

Stifinning

Vi kan spesialisere oss i DFS-algoritmen for å søke en vei mellom to toppunkter.

Topologisk sortering

Den brukes først og fremst til å planlegge jobber fra de gitte avhengighetene blant gruppen av jobber. I informatikk brukes det i instruksjonsplanlegging, dataserialisering, logikksyntese, bestemme rekkefølgen på kompileringsoppgaver.

Søke sterkt sammenkoblede komponenter i en graf

Den brukes i DFS-grafen når det er en bane fra hvert eneste toppunkt i grafen til andre gjenværende toppunkter.

Løse gåter med bare én løsning

DFS-algoritmen kan enkelt tilpasses for å søke i alle løsninger til en labyrint ved å inkludere noder på den eksisterende banen i det besøkte settet.