den store forskjellen MELLOM BFS og DFS er AT BFS fortsetter nivå for nivå mens DFS følger først en bane danner start til sluttnoden( vertex), deretter en annen bane fra start til slutt, og så videre til alle noder er besøkt. VIDERE bruker bfs køen for lagring av nodene mens DFS bruker stakken for traversering av nodene.

BFS og DFS er traversering metoder som brukes i å søke en graf. Graf traversal er prosessen med å besøke alle noder av grafen. En graf er en gruppe Av Hjørner ‘V’ Og Kanter ‘E’ som forbinder til hjørnene.

Innhold: BFS Vs DFS

1. Comparison Chart
2. Definition
3. Key Differences
4. Conclusion

Comparison Chart

Ikke optimal

Basis for comparison	BFS	DFS
Basic	Vertex-based algorithm	Edge-based algorithm
Data structure used to store the nodes	Queue	Stack
Memory consumption	Inefficient	Efficient
Structure Av det konstruerte treet	Bred og kort	Smal og lang
Traverserende mote	Eldste ubesøkte hjørner utforskes først.	Hjørner langs kanten utforskes i begynnelsen.
Optimalitet	Optimal for å finne den korteste avstanden, ikke i pris.
Søknad	Undersøker todelt graf, tilkoblet komponent og korteste vei til stede i en graf.	Undersøker to-kant tilkoblet graf, sterkt koblet graf, asyklisk graf og topologisk rekkefølge.

Definisjon AV Bfs

Bredde Første Søk (Bfs) er traverseringsmetoden som brukes i grafer. Den bruker en kø for å lagre de besøkte hjørnene. I denne metoden er vektleggingen på grafens hjørner, et toppunkt er valgt først da det er besøkt og merket. Hjørnene ved siden av det besøkte toppunktet blir deretter besøkt og lagret i køen i rekkefølge.

På Samme måte behandles de lagrede hjørnene en etter en, og deres tilstøtende hjørner blir besøkt. En node er fullt utforsket før du besøker en annen node i grafen, med andre ord, det krysser grunne uutforskede noder først.

Eksempel

Vi har en graf hvis hjørner Er A, B, C, D, E, F, G. Vurderer A som utgangspunkt. Trinnene som er involvert i prosessen er:

• Vertex a utvides og lagres i køen.
• Hjørner B, D og G etterfølgere Av A, blir utvidet og lagret i køen i mellomtiden Vertex a fjernet.
• Nå blir B på forsiden av køen fjernet sammen med lagring av etterfølgerens hjørner E Og F.Vertex D er på forsiden av køen er fjernet, Og den tilkoblede noden F er allerede besøkt.
• Vertex G er fjernet Fra køen, og den har etterfølger E som allerede er besøkt.
• Nå Fjernes E Og F fra køen, og etterfølgeren vertex C krysses og lagres i køen.
• endelig c er også fjernet Og køen er tom, noe som betyr at vi er ferdige.
• Den genererte Utgangen er – A, B, D, G, E, F, C.

Applikasjoner

BFS kan være nyttig for å finne ut om grafen har tilkoblede komponenter eller ikke. Og også det kan brukes til å oppdage en todelt graf.

en graf er todelt når grafen topp-punktene er delt inn i to udelte sett; ingen to tilstøtende topp-punktene ville ligge i samme sett. En annen metode for å sjekke en todelt graf er å sjekke forekomsten av en merkelig syklus i grafen. En todelt graf må ikke inneholde merkelig syklus.

BFS er også bedre å finne den korteste banen i grafen som kan ses som et nettverk.

Definisjon AV DFS

Dybde Første Søk (Dfs) traversering metoden bruker stakken for lagring av besøkte toppunktene. DFS er kantbasert metode og fungerer på rekursiv måte der kryssene utforskes langs en bane (kant). Utforskningen av en node er suspendert så snart en annen uutforsket node er funnet og de dypeste uutforskede noder er krysset i hovedsak. DFS traverse / besøk hvert toppunkt nøyaktig en gang, og hver kant blir inspisert nøyaktig to ganger.

Eksempel

I Likhet MED BFS kan vi ta samme graf for å utføre dfs-operasjoner, og de involverte trinnene er:

• Vurderer A som start toppunktet som utforskes og lagres i stakken.
• b etterfolgende toppunkt Av A er lagret i stakken.Vertex b har to etterfølgere E Og F, blant dem alfabetisk e blir utforsket først og lagret i stabelen.
• etterfølgeren til vertex E, dvs. g er lagret i stakken.
• Vertex G har to tilkoblede hjørner, og begge er allerede besøkt, Så G er poppet ut fra stakken.
• På Samme Måte, e s også fjernet.
• nå er vertex B øverst i stakken, den andre noden (vertex) F utforskes Og lagres i stakken.Vertex F har to etterfølger C Og D, Mellom Dem er C krysset først og lagret i stakken.Vertex C har bare en forgjenger som allerede er besøkt, så den fjernes fra stakken.
• nå vertex D koblet Til F er besøkt og lagret i stakken.
• som vertex D ikke har noen unvisited noder, derfor d er fjernet.
• På Samme måte er F, B og A også poppet.
• den genererte utgangen er – A, B, E, G, F, C, D.

Søknad

applikasjonene TIL DFS inkluderer inspeksjon av to kantkoblet graf, sterkt tilkoblet graf, asyklisk graf og topologisk rekkefølge.

en graf kalles to kanter forbundet hvis og bare hvis den forblir tilkoblet selv om en av kantene er fjernet. Denne applikasjonen er veldig nyttig, i datanettverk hvor feilen på en lenke i nettverket ikke vil påvirke det gjenværende nettverket, og det vil fortsatt være tilkoblet.

Sterkt tilkoblet graf er en graf der det må eksistere en bane mellom bestilte par hjørner. DFS brukes i den rettede grafen for å søke banen mellom hvert bestilt par hjørner. DFS kan enkelt løse tilkoblingsproblemer.

Konklusjon

BFS og DFS, begge grafsøketeknikkene har lignende kjøretid, men forskjellig romforbruk, dfs tar lineær plass fordi VI må huske enkeltbane med uutforskede noder, MENS BFS holder hver node i minnet.DFS gir dypere løsninger og er ikke optimal, men det fungerer bra når løsningen er tett mens BFS er optimal som søker det optimale målet først.