depth first search c program traverse graph
Deze tutorial behandelt Depth First Search (DFS) in C ++ waarin een grafiek of boom in de diepte wordt doorlopen. Je leert ook DFS-algoritme en implementatie:
Diepte-eerst zoeken (DFS) is nog een andere techniek die wordt gebruikt om door een boom of een grafiek te lopen.
DFS begint met een hoofdknooppunt of een startknooppunt en verkent vervolgens de aangrenzende knooppunten van het huidige knooppunt door dieper in de grafiek of een boom te gaan. Dit betekent dat in DFS de knooppunten in de diepte worden verkend totdat een knooppunt zonder kinderen wordt aangetroffen.
Zodra het leaf-knooppunt is bereikt, loopt DFS terug en begint het op een vergelijkbare manier nog meer knooppunten te verkennen.
Bekijk hier de Beginners C ++ Trainingsgids.
Wat je leert:
Depth First Search (DFS) in C ++
In tegenstelling tot BFS waarin we de knooppunten in de breedte verkennen, verkennen we in DFS de knooppunten in de diepte. In DFS gebruiken we een stapelgegevensstructuur voor het opslaan van de knooppunten die worden verkend. De randen die ons naar onontgonnen knooppunten leiden, worden ‘ontdekkingsranden’ genoemd, terwijl de randen die naar reeds bezochte knooppunten leiden ‘blokranden’ worden genoemd.
Vervolgens zullen we het algoritme en de pseudo-code voor de DFS-techniek zien.
DFS-algoritme
- Stap 1: Voeg het hoofdknooppunt of startknooppunt van een boom of een grafiek in de stapel in.
- Stap 2: Haal het bovenste item uit de stapel en voeg het toe aan de bezochte lijst.
- Stap 3: Zoek alle aangrenzende knooppunten van het knooppunt dat is gemarkeerd als bezocht en voeg de knooppunten die nog niet zijn bezocht toe aan de stapel.
- Stap 4 : Herhaal stap 2 en 3 totdat de stapel leeg is.
Pseudocode
De pseudo-code voor DFS wordt hieronder gegeven.
Uit de bovenstaande pseudo-code merken we dat het DFS-algoritme recursief wordt aangeroepen op elk hoekpunt om ervoor te zorgen dat alle hoekpunten worden bezocht.
Doorlopen met illustraties
Laten we nu de DFS-doorgang van een grafiek illustreren. Voor de duidelijkheid zullen we dezelfde grafiek gebruiken die we in de BFS-illustratie hebben gebruikt.
Laat 0 het startknooppunt of bronknooppunt zijn. Eerst markeren we het als bezocht en voegen we het toe aan de bezochte lijst. Vervolgens duwen we alle aangrenzende knooppunten in de stapel.
Vervolgens nemen we een van de aangrenzende knooppunten om te verwerken, d.w.z. de bovenkant van de stapel is 1. We markeren het als bezocht door het toe te voegen aan de bezochte lijst. Zoek nu naar de aangrenzende knooppunten van 1. Aangezien 0 al in de bezochte lijst staat, negeren we deze en bezoeken we 2 die bovenaan de stapel staat.
Vervolgens markeren we knooppunt 2 als bezocht. Het aangrenzende knooppunt 4 wordt aan de stapel toegevoegd.
Vervolgens markeren we 4, de bovenkant van de stapel zoals bezocht. Knooppunt 4 heeft alleen knooppunt 2 als de aangrenzende die al is bezocht, daarom negeren we het.
In dit stadium is alleen knooppunt 3 aanwezig in de stapel. Het aangrenzende knooppunt 0 is al bezocht, daarom negeren we het. Nu markeren we 3 als bezocht.
Nu is de stapel leeg en de bezochte lijst toont de volgorde van de diepte-eerste verplaatsing van de gegeven grafiek.
Als we de gegeven grafiek en de traversale volgorde bekijken, merken we dat we voor het DFS-algoritme inderdaad de grafiek in de diepte doorlopen en dan weer teruggaan om nieuwe knooppunten te verkennen.
Implementatie van Depth-First Search
Laten we de DFS-traversal-techniek implementeren met C ++.
Uitgang:
Diepte-eerste verplaatsing voor de gegeven grafiek:
0 1 2 4 3
We hebben de grafiek in het programma weer gebruikt die we ter illustratie hebben gebruikt. We zien dat het DFS-algoritme (gescheiden in twee functies) recursief wordt aangeroepen op elk hoekpunt in de grafiek om ervoor te zorgen dat alle hoekpunten worden bezocht.
Runtime-analyse
De tijdcomplexiteit van DFS is hetzelfde als BFS, d.w.z. O (| V | + | E |) waarbij V het aantal hoekpunten is en E het aantal randen in een bepaalde grafiek.
Net als bij BFS, is de dominante factor, afhankelijk van of de grafiek dunbevolkt of dichtbevolkt is, respectievelijk hoekpunten of randen bij de berekening van tijdcomplexiteit.
Iteratieve DFS
De implementatie die hierboven wordt getoond voor de DFS-techniek is recursief van aard en gebruikt een functieaanroepstapel. We hebben nog een variant voor het implementeren van DFS, namelijk ' Iteratieve diepte eerst zoeken Hierin gebruiken we de expliciete stapel om de bezochte hoekpunten vast te houden.
We hebben de implementatie voor iteratieve DFS hieronder getoond. Merk op dat de implementatie hetzelfde is als BFS, behalve de factor dat we de stapelgegevensstructuur gebruiken in plaats van een wachtrij.
Uitgang:
Uitvoer van Iteratieve Diepte-eerste traversal:
0 3 2 4 1
We gebruiken dezelfde grafiek die we hebben gebruikt in onze recursieve implementatie. Het verschil in output is dat we de stack gebruiken in de iteratieve implementatie. Aangezien de stapels de LIFO-volgorde volgen, krijgen we een andere volgorde van DFS. Om dezelfde volgorde te krijgen, willen we de hoekpunten misschien in omgekeerde volgorde invoegen.
BFS versus DFS
Tot dusver hebben we zowel de doorgangstechnieken voor grafieken besproken, d.w.z. BFS en DFS.
Laten we nu eens kijken naar de verschillen tussen de twee.
BFS | DFS |
---|---|
Staat voor 'Breedte eerst zoeken' | Staat voor 'Diepte eerst zoeken' |
De knooppunten worden niveau voor niveau in de breedte onderzocht. | De knooppunten worden in de diepte onderzocht totdat er alleen bladknooppunten zijn en worden vervolgens teruggetrokken om andere niet-bezochte knooppunten te verkennen. |
BFS wordt uitgevoerd met behulp van de datastructuur van de wachtrij. | DFS wordt uitgevoerd met behulp van de datastructuur van de stapel. |
Langzamer in prestaties. | Sneller dan BFS. |
Handig bij het vinden van het kortste pad tussen twee knooppunten. | Meestal gebruikt om cycli in grafieken te detecteren. |
Toepassingen van DFS
- Cycli in de grafiek detecteren: Als we een achterrand vinden tijdens het uitvoeren van DFS in een grafiek, kunnen we concluderen dat de grafiek een cyclus heeft. Daarom wordt DFS gebruikt om de cycli in een grafiek te detecteren.
- Padvinden: Gegeven twee hoekpunten x en y, kunnen we het pad tussen x en y vinden met DFS. We beginnen met hoekpunt x en duwen vervolgens alle hoekpunten op weg naar de stapel totdat we y tegenkomen. De inhoud van de stapel geeft het pad tussen x en y weer.
- Minimale overspanningsboom en kortste pad: DFS-traversal van de niet-gewogen grafiek geeft ons een minimale spanning tree en het kortste pad tussen knooppunten.
- Topologische sortering: We gebruiken topologische sortering wanneer we de taken moeten plannen op basis van de gegeven afhankelijkheden tussen taken. In de informatica gebruiken we het voornamelijk voor het oplossen van symboolafhankelijkheden in linkers, dataserialisatie, instructieplanning, enz. DFS wordt veel gebruikt bij topologische sortering.
Gevolgtrekking
In de laatste paar tutorials hebben we meer onderzocht over de twee doorgangstechnieken voor grafieken, namelijk BFS en DFS. We hebben zowel de verschillen als de toepassingen van beide technieken gezien. BFS en DFS bereiken in principe hetzelfde resultaat als alle knooppunten van een grafiek worden bezocht, maar ze verschillen in de volgorde van de uitvoer en de manier waarop het wordt gedaan.
We hebben ook de implementatie van beide technieken gezien. Terwijl BFS een wachtrij gebruikt, maakt DFS gebruik van stapels om de techniek te implementeren. Hiermee sluiten we de tutorial over verplaatsingstechnieken voor grafieken af. We kunnen ook BFS en DFS op bomen gebruiken.
extraheer e-mailadressen van website gratis
We zullen meer leren over spanning trees en een aantal algoritmen om het kortste pad tussen de knooppunten van een grafiek te vinden in onze komende tutorial.
Zie hier om de volledige lijst met C ++ - zelfstudies te verkennen.
Aanbevolen literatuur
- Breadth First Search (BFS) C ++ - programma om een grafiek of boomstructuur te doorlopen
- Binaire zoekboom C ++: BST-implementatie en bewerkingen met voorbeelden
- B Tree en B + Tree gegevensstructuur in C ++
- Diepgaande Eclipse-zelfstudies voor beginners
- Binaire boomgegevensstructuur in C ++
- Grafiekimplementatie in C ++ met behulp van aangrenzende lijst
- AVL Tree and Heap-gegevensstructuur in C ++
- 12 beste tools voor het maken van lijngrafieken voor het maken van verbluffende lijngrafieken [2021 RANKINGS]