het belangrijkste verschil tussen BFS en DFS is dat BFS niveau per niveau verloopt terwijl DFS eerst een pad volgt van het begin naar het eindknooppunt (vertex), dan een ander pad van begin tot eind, enzovoort totdat alle knooppunten worden bezocht. Verder gebruikt BFS de wachtrij voor het opslaan van de knooppunten, terwijl DFS de stack gebruikt voor het doorlopen van de knooppunten.
BFS en DFS zijn de doorloopmethoden die worden gebruikt bij het zoeken naar een grafiek. Graph traversal is het proces van het bezoeken van alle knooppunten van de grafiek. Een grafiek is een groep van hoekpunten ‘V’ en randen ‘E’ die zich verbinden met de hoekpunten.
inhoud: 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 van de geconstrueerde boom | breed en kort | smal en lang |
| Traversing fashion | oudste niet bezochte hoekpunten worden eerst onderzocht. | hoekpunten langs de rand worden in het begin onderzocht. |
| optimaliteit | optimaal voor het vinden van de Kortste Afstand, niet in kosten. | niet optimaal |
| toepassing | onderzoekt bipartiete grafiek, verbonden component en kortste pad aanwezig in een grafiek. | onderzoekt twee-rand verbonden grafiek, sterk verbonden grafiek, acyclische grafiek en topologische orde. |
definitie van BFS
Breadth First Search (bfs) is de doorlopende methode die in grafieken wordt gebruikt. Het gebruikt een wachtrij voor het opslaan van de bezochte hoekpunten. Bij deze methode wordt de nadruk gelegd op de hoekpunten van de grafiek, een hoekpunt wordt eerst geselecteerd dan wordt het bezocht en gemarkeerd. De hoekpunten naast de bezochte hoekpunten worden vervolgens bezocht en achtereenvolgens in de wachtrij opgeslagen.
Op dezelfde manier worden de opgeslagen hoekpunten één voor één behandeld en worden hun aangrenzende hoekpunten bezocht. Een knooppunt wordt volledig onderzocht voordat u een ander knooppunt in de grafiek bezoekt, met andere woorden, het doorkruist eerst ondiepste onontgonnen knooppunten.
voorbeeld
We hebben een grafiek waarvan de hoekpunten A, B, C, D, E, F, G zijn. De stappen die betrokken zijn bij het proces zijn:
- Vertex a wordt uitgebreid en opgeslagen in de wachtrij.
- hoekpunten B, D en G opvolgers van A, worden uitgebreid en opgeslagen in de wachtrij terwijl Vertex A verwijderd is.
- nu wordt B aan de voorkant van de wachtrij verwijderd samen met het opslaan van de volgende hoekpunten E en F.
- Vertex D is aan de voorkant van de wachtrij wordt verwijderd, en het verbonden knooppunt F is al bezocht.
- Vertex G is verwijderd uit de wachtrij, en het heeft opvolger E die al wordt bezocht.
- nu worden E en F uit de wachtrij verwijderd, en de opvolger vertex C wordt doorkruist en opgeslagen in de wachtrij.
- eindelijk C is ook verwijderd en de wachtrij is leeg, wat betekent dat we klaar zijn.
- de gegenereerde Output is-A, B, D, G, E, F, C.
toepassingen
BFS kan nuttig zijn bij het vinden of de grafiek verbonden componenten heeft of niet. En het kan ook worden gebruikt bij het detecteren van een bipartiete grafiek.
een grafiek is bipartiet wanneer de grafiekpunten worden verdeeld in twee disjuncte verzamelingen; geen twee aangrenzende hoekpunten zouden in dezelfde verzameling verblijven. Een andere methode om een bipartiete grafiek te controleren is om het voorkomen van een oneven cyclus in de grafiek te controleren. Een bipartiete grafiek mag geen oneven cyclus bevatten.
BFS is ook beter in het vinden van het kortste pad in de grafiek kan worden gezien als een netwerk.
definitie van DFS
Depth First Search (DFS) traversing methode gebruikt de stack voor het opslaan van de bezochte hoekpunten. DFS is de edge-gebaseerde methode en werkt op de recursieve manier waarbij de hoekpunten worden onderzocht langs een pad (edge). De exploratie van een knoop wordt opgeschort zodra een andere onontgonnen knoop wordt gevonden en de diepste onontgonnen knopen in de eerste plaats worden doorkruist. DFS doorkruisen / bezoeken elk hoekpunt precies één keer en elke rand wordt precies twee keer geïnspecteerd.
voorbeeld
vergelijkbaar met BFS laten we dezelfde grafiek nemen voor het uitvoeren van DFS-bewerkingen, en de betrokken stappen zijn:
- beschouwt A als het startpunt dat wordt verkend en opgeslagen in de stack.
- B opvolger vertex van A wordt opgeslagen in de stack.
- Vertex B heeft twee opvolgers E en F, waaronder Alfabetisch E wordt eerst onderzocht en opgeslagen in de stack.
- de opvolger van vertex E, d.w.z. G, wordt opgeslagen in de stack.
- Vertex G heeft twee verbonden hoekpunten, en beide zijn al bezocht, dus G wordt uit de stack geplakt.
- op dezelfde manier is E ook verwijderd.
- nu staat vertex B aan de top van de stack, het andere knooppunt(vertex) F wordt onderzocht en opgeslagen in de stack.
- Vertex F heeft twee opvolger C en D, daartussen wordt C als eerste doorlopen en opgeslagen in de stack.
- Vertex C heeft slechts één voorganger die al bezocht is, dus het is verwijderd uit de stack.
- nu wordt vertex d verbonden met F bezocht en opgeslagen in de stack.
- aangezien vertex D geen niet-bezochte knooppunten heeft, wordt d verwijderd.
- op dezelfde manier worden F, B en A ook weergegeven.
- de gegenereerde output is-A, B, E, G, F, C, D.
toepassing
De toepassingen van DFS omvatten de inspectie van twee edge connected graph, strongly connected graph, acyclic graph en topological order.
een grafiek wordt twee verbonden randen genoemd als en alleen als het verbonden blijft, zelfs als een van de randen wordt verwijderd. Deze toepassing is zeer nuttig, in computernetwerken waar het falen van een link in het netwerk het resterende netwerk niet zal beïnvloeden, en het zou nog steeds verbonden zijn.
strongly connected graph is een grafiek waarin er een pad moet bestaan tussen geordend paar hoekpunten. DFS wordt gebruikt in de gerichte grafiek voor het zoeken van het pad tussen elk geordend paar hoekpunten. DFS kan gemakkelijk verbindingsproblemen oplossen.
belangrijke verschillen tussen BFS en DFS
- BFS is op vertex gebaseerd algoritme, terwijl DFS een op edge gebaseerd algoritme is.
- de gegevensstructuur van de wachtrij wordt gebruikt in BFS. Aan de andere kant gebruikt DFS stack of recursie.
- geheugenruimte wordt efficiënt gebruikt in DFS, terwijl ruimtegebruik in BFS niet effectief is.
- BFS is een optimaal algoritme, terwijl DFS niet optimaal is.
- DFS maakt smalle en lange bomen. Bfs construeert daarentegen een brede en korte boom.
conclusie
BFS en DFS, beide technieken voor het zoeken van grafieken hebben dezelfde draaitijd maar een verschillend ruimtegebruik, DFS neemt lineaire ruimte in omdat we één pad moeten onthouden met onontgonnen knopen, terwijl BFS elk knooppunt in het geheugen houdt.
DFS levert diepere oplossingen op en is niet optimaal, maar het werkt goed als de oplossing dicht is, terwijl BFS optimaal is, wat eerst het optimale doel zoekt.