den største forskel mellem BFS og DFS er, at BFS fortsætter niveau for niveau, mens DFS først følger en sti fra start til slutnoden (toppunkt), derefter en anden sti fra start til slut og så videre, indtil alle noder besøges. Desuden bruger BFS køen til lagring af noderne, mens DFS bruger stakken til gennemgang af noderne.
BFS og DFS er de gennemløbsmetoder, der bruges til at søge i en graf. Graph traversal er processen med at besøge alle knudepunkter i grafen. En graf er en gruppe af hjørner ‘ V ‘og kanter’ E’, der forbinder til hjørnerne.
indhold: BFS Vs DFS
- Comparison Chart
- Definition
- Key Differences
- Conclusion
Comparison Chart
| 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 af det konstruerede træ | bred og kort | smal og lang |
| krydsende mode | ældste ikke-besøgte hjørner udforskes først. | hjørner langs kanten udforskes i begyndelsen. |
| optimalitet | Optimal til at finde den korteste afstand, ikke i omkostninger. | ikke optimal |
| ansøgning | undersøger topartsgraf, tilsluttet komponent og korteste sti til stede i en graf. | undersøger to-kant tilsluttet graf, stærkt forbundet graf, acyklisk graf og topologisk rækkefølge. |
Definition af BFS
bredde første søgning (BFS) er den gennemløbsmetode, der anvendes i grafer. Det bruger en kø til opbevaring af de besøgte hjørner. I denne metode er understregningen på grafens hjørner, et toppunkt vælges først, så det besøges og markeres. Hjørnerne ved siden af det besøgte toppunkt besøges derefter og gemmes i køen sekventielt.
tilsvarende behandles de lagrede hjørner derefter en efter en, og deres tilstødende hjørner besøges. En node udforskes fuldt ud, før du besøger en anden node i grafen, med andre ord krydser den først De laveste uudforskede noder.
eksempel
Vi har en graf, hvis hjørner er A, B, C, D, E, F, G. overvejer A som udgangspunkt. De trin, der er involveret i processen, er:
- toppunkt a udvides og gemmes i køen.
- hjørner B, D og G efterfølgere af A, udvides og gemmes i køen i mellemtiden toppunkt a fjernet.
- nu fjernes B i den forreste ende af køen sammen med lagring af dens efterfølgende hjørner E og F.
- toppunkt D er i den forreste ende af køen fjernes, og dens tilsluttede node F er allerede besøgt.
- toppunkt G fjernes fra køen, og det har efterfølger E, som allerede er besøgt.
- nu fjernes E og F fra køen, og dens efterfølgende toppunkt C krydses og gemmes i køen.
- endelig fjernes C også, og køen er tom, hvilket betyder, at vi er færdige.
- den genererede udgang er-A, B, D, G, E, F, C.
applikationer
BFS kan være nyttige til at finde ud af, om grafen har tilsluttede komponenter eller ej. Og det kan også bruges til at detektere en topartsgraf.
en graf er todelt, når grafens hjørner er opdelt i to adskilte sæt; ingen to tilstødende hjørner ville opholde sig i det samme sæt. En anden metode til kontrol af en topartsgraf er at kontrollere forekomsten af en ulige cyklus i grafen. En todelt graf må ikke indeholde ulige cyklus.
BFS er også bedre til at finde den korteste vej i grafen kunne ses som et netværk.
Definition af DFS
dybde første søgning (DFS) gennemkører metode bruger stakken til lagring af besøgte knudepunkter. DFS er den kantbaserede metode og fungerer på rekursiv måde, hvor hjørnerne udforskes langs en sti (kant). Udforskningen af en knude suspenderes, så snart en anden uudforsket knude er fundet, og de dybeste uudforskede noder først og fremmest krydses. DFS traverse / besøg hvert toppunkt nøjagtigt en gang, og hver kant inspiceres nøjagtigt to gange.
eksempel
svarende til BFS lad os tage den samme graf til udførelse af DFS-operationer, og de involverede trin er:
- overvejer A som startpunkt, som udforskes og gemmes i stakken.
- b efterfølger toppunkt af A er gemt i stakken.
- toppunkt B har to efterfølgere E og F, blandt dem alfabetisk e udforskes først og gemmes i stakken.
- efterfølgeren til toppunkt E, dvs. G er gemt i stakken.
- toppunkt G har to forbundne hjørner, og begge er allerede besøgt, så G er poppet ud fra stakken.
- tilsvarende fjernes også.
- nu er toppunkt B øverst i stakken, dens en anden knude(toppunkt) F udforskes og gemmes i stakken.
- toppunkt F har to efterfølgere C og D, mellem dem C krydses først og gemmes i stakken.
- toppunkt C har kun en forgænger, som allerede er besøgt, så den fjernes fra stakken.
- nu er toppunkt D forbundet til F besøgt og gemt i stakken.
- da toppunkt D ikke har nogen ikke-besøgte noder, fjernes D derfor.
- tilsvarende er F, B og A også poppet.
- den genererede udgang er-A, B, E, G, F, C, D.
ansøgning
anvendelserne af DFS inkluderer inspektion af to kantforbundet graf, stærkt forbundet graf, acyklisk graf og topologisk rækkefølge.
en graf kaldes to kanter forbundet, hvis og kun hvis den forbliver tilsluttet, selvom en af dens kanter fjernes. Denne applikation er meget nyttig i computernetværk, hvor fejlen i et link i netværket ikke påvirker det resterende netværk, og det vil stadig være forbundet.
stærkt forbundet graf er en graf, hvor der skal eksistere en sti mellem ordnede par hjørner. DFS bruges i den rettede graf til at søge stien mellem hvert ordnet par hjørner. DFS kan nemt løse forbindelsesproblemer.
nøgleforskelle mellem BFS og DFS
- BFS er toppunktsbaseret algoritme, mens DFS er en kantbaseret algoritme.
- kø datastruktur bruges i BFS. På den anden side bruger DFS stak eller rekursion.
- hukommelsesplads udnyttes effektivt i DFS, mens pladsudnyttelse i BFS ikke er effektiv.
- BFS er optimal algoritme, mens DFS ikke er optimal.
- DFS konstruerer smalle og lange træer. I modsætning hertil konstruerer BFS bredt og kort træ.
konklusion
BFS og DFS, begge grafsøgningsteknikker har lignende køretid, men forskelligt rumforbrug, DFS tager lineært rum, fordi vi skal huske en enkelt sti med uudforskede noder, mens BFS holder hver node i hukommelsen.
DFS giver dybere løsninger og er ikke optimal, men det fungerer godt, når løsningen er tæt, mens BFS er optimal, som først søger det optimale mål.