BFS en DFS zijn de verplaatsingsmethoden die worden gebruikt bij het doorzoeken van een grafiek. Grafiek doorlopen is het proces van het bezoeken van alle knooppunten van de grafiek. Een grafiek is een groep van Vertices 'V' en Edges 'E' die verbinding maken met de hoekpunten.
Vergelijkingstabel
| Basis voor vergelijking | BFS | DFS |
|---|---|---|
| basis- | Vertex-gebaseerd algoritme | Edge-gebaseerd algoritme |
| Gegevensstructuur die wordt gebruikt om de knooppunten op te slaan | Wachtrij | stack |
| Geheugen verbruik | Inefficiënt | doeltreffend |
| Structuur van de gebouwde boom | Breed en kort | Smal en lang |
| Doorkruisende mode | De oudste niet-bezichtigde hoekpunten worden eerst verkend. | Hoekpunten langs de rand worden in het begin verkend. |
| Optimaliteitstheorie | 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 een aan twee kanten verbonden grafiek, sterk verbonden grafiek, acyclische grafiek en topologische volgorde. |
Definitie van BFS
Breadth First Search (BFS) is de verplaatsingsmethode die in grafieken wordt gebruikt. Het gebruikt een wachtrij voor het opslaan van de bezochte hoekpunten. Bij deze methode ligt de nadruk op de hoekpunten van de grafiek, één hoekpunt wordt eerst geselecteerd en vervolgens bezocht en gemarkeerd. De hoekpunten naast de bezochte vertex worden vervolgens bezocht en achtereenvolgens in de wachtrij opgeslagen. Op dezelfde manier worden de opgeslagen hoekpunten één voor één behandeld en worden de aangrenzende hoekpunten bezocht. Een knooppunt is volledig verkend voordat een ander knooppunt in de grafiek wordt bezocht, met andere woorden, het gaat eerst over ondiepste, onontdekte knooppunten.
Voorbeeld
We hebben een grafiek waarvan de hoekpunten A, B, C, D, E, F, G zijn. Beschouw A als uitgangspunt. De stappen die bij het proces zijn betrokken zijn:
- Vertex A wordt uitgevouwen en in de wachtrij opgeslagen.
- Vertices B, D en G opvolgers van A, worden uitgevouwen en opgeslagen in de wachtrij ondertussen Vertex A verwijderd.
- Nu wordt B aan het vooreinde van de wachtrij verwijderd samen met het opslaan van zijn opvolgerhoekpunten E en F.
- Vertex D aan de voorkant van de wachtrij wordt verwijderd en het verbonden knooppunt F is al bezocht.
- Vertex G wordt uit de wachtrij verwijderd en heeft de opvolger E die al is bezocht.
- Nu worden E en F uit de wachtrij verwijderd en wordt de opvolgervertex C ervan doorlopen en in de wachtrij opgeslagen.
- Eindelijk wordt C ook verwijderd en is de wachtrij leeg, wat betekent dat we klaar zijn.
- De gegenereerde uitvoer is - A, B, D, G, E, F, C.
BFS kan handig zijn om te bepalen of de grafiek al dan niet componenten heeft aangesloten . En het kan ook worden gebruikt bij het detecteren van een bipartiete grafiek .
Een grafiek is tweeledig wanneer de grafiestoppunten zijn verdeeld in twee disjuncte sets; geen twee aangrenzende hoekpunten zouden in dezelfde reeks 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 dat als een netwerk kan worden beschouwd.
Definitie van DFS
Depth First Search (DFS) -doorgangsmethode gebruikt de stapel voor het opslaan van de bezochte hoekpunten. DFS is de randgebaseerde methode en werkt op recursieve wijze waarbij de hoekpunten langs een pad (rand) worden verkend. De verkenning van een knooppunt wordt opgeschort zodra een ander onontgonnen knooppunt wordt gevonden en de diepste onontgonnen knooppunten worden op de voorgrond doorlopen. DFS doorkruisen / bezoeken elke vertex precies één keer en elke rand wordt precies twee keer geïnspecteerd.
Voorbeeld
Vergelijkbaar met BFS kunt u dezelfde grafiek maken voor het uitvoeren van DFS-bewerkingen, en de betrokken stappen zijn:
- Beschouw A als de eerste vertex die wordt verkend en opgeslagen in de stapel.
- B de opvolgerhoek van A wordt opgeslagen in de stapel.
- Vertex B heeft twee opvolgers E en F, waarvan alfabetisch E eerst wordt verkend en in de stapel wordt opgeslagen.
- De opvolger van vertex E, dat wil zeggen G wordt opgeslagen in de stapel.
- Vertex G heeft twee verbonden hoekpunten en beide zijn al bezocht, dus G komt uit de stapel.
- Evenzo zijn E's ook verwijderd.
- Nu staat vertex B bovenaan de stapel, het andere knooppunt (vertex) F wordt verkend en opgeslagen in de stapel.
- Vertex F heeft twee opvolgers C en D, tussen hen wordt eerst C doorlopen en in de stapel opgeslagen.
- Vertex C heeft slechts één voorganger die al is bezocht, dus deze wordt van de stapel verwijderd.
- Nu wordt vertex D verbonden met F bezocht en opgeslagen in de stapel.
- Aangezien vertex D geen niet-bezochte knooppunten heeft, wordt D daarom verwijderd.
- Evenzo worden F, B en A ook gepoft.
- De gegenereerde uitvoer is - A, B, E, G, F, C, D.
De toepassingen van DFS omvatten de inspectie van twee aan de rand verbonden grafiek, sterk verbonden grafiek, acyclische grafiek en topologische volgorde .
Een grafiek wordt twee verbonden randen genoemd als en alleen als deze verbonden blijft, zelfs als een van de randen is verwijderd. Deze applicatie is erg handig, in computernetwerken waarbij het falen van één link in het netwerk geen invloed heeft op het resterende netwerk en het nog steeds verbonden is.
Sterk verbonden grafiek is een grafiek waarin er een pad moet zijn tussen het geordende paar hoekpunten. DFS wordt gebruikt in de gerichte grafiek voor het zoeken naar het pad tussen elk geordend paar hoekpunten. DFS kan verbindingsproblemen gemakkelijk oplossen.
Belangrijkste verschillen tussen BFS en DFS
- BFS is een op de opte gebaseerd algoritme, terwijl DFS een op randen gebaseerd algoritme is.
- Wachtrijgegevensstructuur wordt gebruikt in BFS. Aan de andere kant gebruikt DFS stack of recursie.
- Geheugenruimte wordt efficiënt gebruikt in DFS, terwijl het gebruik van de ruimte in BFS niet effectief is.
- BFS is een optimaal algoritme terwijl DFS niet optimaal is.
- DFS construeert smalle en lange bomen. Tegenovergesteld, BFS bouwt brede en korte boom.
Conclusie
BFS en DFS, beide van de grafiekzoektechnieken hebben een vergelijkbare looptijd, maar verschillende ruimteconsumptie, DFS neemt lineaire ruimte in beslag, omdat we een enkel pad moeten onthouden met onontgonnen knooppunten, terwijl BFS elk knooppunt in het geheugen houdt.
DFS levert diepere oplossingen op en is niet optimaal, maar het werkt goed wanneer de oplossing dicht is, terwijl BFS optimaal is en in eerste instantie het optimale doel doorzoekt.
