breadth first search c program traverse graph
Deze tutorial behandelt de breedte van de eerste zoekopdracht in C ++ waarin de grafiek of boom in de breedte wordt doorlopen. Je leert ook BFS-algoritme en implementatie:
Deze expliciete C ++ - zelfstudie geeft je een gedetailleerde uitleg van doorgangstechnieken die kunnen worden uitgevoerd op een boom of grafiek.
Traversal is de techniek waarmee we elk knooppunt van de grafiek of boom bezoeken. Er zijn twee standaardmethoden voor doorlopen.
- Breedte-eerste zoekopdracht (BFS)
- Diepte-eerste zoekopdracht (DFS)
Zie hier om de volledige lijst met C ++ - zelfstudies te verkennen.
gekoppelde lijst c ++ weergeven
Wat je leert:
Breadth First Search (BFS) -techniek in C ++
In deze tutorial zullen we in detail de breedte-eerst zoektechniek bespreken.
Bij de breedte-eerst-verplaatsingstechniek wordt de grafiek of boom in de breedte doorlopen. Deze techniek gebruikt de datastructuur van de wachtrij om de hoekpunten of knooppunten op te slaan en ook om te bepalen welk hoekpunt / knooppunt als volgende moet worden ingenomen.
Breedte-eerst-algoritme begint met het hoofdknooppunt en doorloopt vervolgens alle aangrenzende knooppunten. Vervolgens selecteert het het dichtstbijzijnde knooppunt en verkent het alle andere niet-bezochte knooppunten. Dit proces wordt herhaald totdat alle knooppunten in de grafiek zijn verkend.
Breedte-eerste zoekalgoritme
Hieronder wordt het algoritme voor de BFS-techniek weergegeven.
Beschouw G als een grafiek die we gaan doorlopen met behulp van het BFS-algoritme.
Laat S het wortel- / startknooppunt van de grafiek zijn.
- Stap 1: Begin met knooppunt S en zet het in de wachtrij.
- Stap 2: Herhaal de volgende stappen voor alle knooppunten in de grafiek.
- Stap 3: Dequeue S en verwerk het.
- Stap 4: Zet alle aangrenzende knooppunten van S in de wachtrij en verwerk ze.
- (EINDE VAN LUS)
- Stap 6: UITGANG
Pseudocode
De pseudo-code voor de BFS-techniek wordt hieronder gegeven.
Doorlopen met illustraties
Laat 0 het startknooppunt of bronknooppunt zijn. Eerst plaatsen we het in de bezochte wachtrij en alle aangrenzende knooppunten in de wachtrij.
Vervolgens nemen we een van de aangrenzende knooppunten om te verwerken, d.w.z. 1. We markeren het als bezocht door het uit de wachtrij te verwijderen en de aangrenzende knooppunten in de wachtrij te plaatsen (2 en 3 al in de wachtrij). Omdat 0 al bezocht is, negeren we het.
geavanceerde sql interviewvragen en antwoorden pdf
Vervolgens halen we knooppunt 2 uit de wachtrij en markeren het als bezocht. Vervolgens wordt het aangrenzende knooppunt 4 aan de wachtrij toegevoegd.
Vervolgens verwijderen we 3 van de wachtrij en markeren deze als bezocht. Knooppunt 3 heeft slechts één aangrenzend knooppunt, d.w.z. 0 dat al is bezocht. Daarom negeren we het.
In dit stadium is alleen knooppunt 4 aanwezig in de wachtrij. Het aangrenzende knooppunt 2 is al bezocht, daarom negeren we het. Nu markeren we 4 als bezocht.
Vervolgens is de reeks die aanwezig is in de bezochte lijst de breedte-eerste doorloop van de gegeven grafiek.
Als we de gegeven grafiek en de traversale volgorde bekijken, kunnen we opmerken dat we voor het BFS-algoritme inderdaad de grafiek in de breedte doorlopen en dan naar het volgende niveau gaan.
BFS-implementatie
Uitgang:
implementeren prioriteit wachtrij c ++
Breedte-eerste verplaatsing voor de gegeven graaf (met 0 als startknooppunt):
0 1 2 3 4
We hebben de BFS geïmplementeerd in het bovenstaande programma. Merk op dat de grafiek de vorm heeft van een aangrenzende lijst en dan gebruiken we een iterator om de lijst te doorlopen en BFS uit te voeren.
We hebben dezelfde grafiek gebruikt die we ter illustratie hebben gebruikt als invoer voor het programma om de doorloopsequentie te vergelijken.
Runtime-analyse
Als V het aantal hoekpunten is en E het aantal randen van een grafiek, dan kan de tijdcomplexiteit voor BFS worden uitgedrukt als O (| V | + | E |) Dit gezegd hebbende, hangt het ook af van de datastructuur die we gebruiken om de grafiek weer te geven.
Als we de aangrenzende lijst gebruiken (zoals in onze implementatie), dan is de tijdcomplexiteit O (| V | + | E |).
Als we de aangrenzende matrix gebruiken, dan is de tijdcomplexiteit O (V ^ 2)
Naast de datastructuren die worden gebruikt, speelt er ook een rol of de grafiek dichtbevolkt of dunbevolkt is.
Wanneer het aantal hoekpunten het aantal randen overschrijdt, dan wordt gezegd dat de grafiek schaars is verbonden, omdat er veel niet-verbonden hoekpunten zullen zijn. In dit geval is de tijdcomplexiteit van de grafiek O (V).
Aan de andere kant kan de grafiek soms een groter aantal randen hebben dan het aantal hoekpunten. In zo'n geval zou de grafiek dichtbevolkt zijn. De tijdcomplexiteit van zo'n grafiek is O (E).
Concluderend, wat de uitdrukking O (| V | + | E |) betekent, is afhankelijk van of de grafiek dicht of dunbevolkt is, de dominerende factor, d.w.z. randen of hoekpunten, zal de tijdcomplexiteit van de grafiek dienovereenkomstig bepalen.
Toepassingen van BFS Traversal
- Garbage Collection: De garbage collection-techniek, ‘Cheney’s algoritme’, maakt gebruik van de breedte-eerste traversal om garbagecollection te kopiëren.
- Uitzenden in netwerken: Een pakket reist van het ene knooppunt naar het andere met behulp van de BFS-techniek in het omroepnetwerk om alle knooppunten te bereiken.
- GPS navigatie: We kunnen BFS gebruiken in GPS-navigatie om alle aangrenzende of aangrenzende locatieknooppunten te vinden.
- Websites voor sociale netwerken: Gegeven een persoon ‘P’, kunnen we alle mensen binnen een afstand vinden, ‘d’ van p met behulp van BFS tot de d-niveaus.
- Peer-to-peer-netwerken: Opnieuw kan BFS worden gebruikt in peer-to-peer-netwerken om alle aangrenzende knooppunten te vinden.
- Kortste pad en minimale overspanningsboom in de niet-gewogen grafiek: De BFS-techniek wordt gebruikt om het kortste pad te vinden, d.w.z. het pad met het minste aantal randen in de niet-gewogen grafiek. Evenzo kunnen we ook een minimale spanning tree vinden met behulp van BFS in de niet-gewogen grafiek.
Gevolgtrekking
De breedte-eerst zoektechniek is een methode die wordt gebruikt om alle knooppunten van een grafiek of een boom in de breedte te doorlopen.
Deze techniek wordt meestal gebruikt om het kortste pad tussen de knooppunten van een grafiek te vinden of in toepassingen waarbij we elk aangrenzend knooppunt moeten bezoeken, zoals in netwerken.
Klik hier voor de gratis C ++ cursus.
Aanbevolen literatuur
- Binaire zoekboom C ++: BST-implementatie en bewerkingen met voorbeelden
- B Tree en B + Tree gegevensstructuur in C ++
- Grafiekimplementatie in C ++ met behulp van aangrenzende lijst
- Binaire boomgegevensstructuur in C ++
- 12 beste tools voor het maken van lijngrafieken voor het maken van verbluffende lijngrafieken (2021 RANKINGS)
- AVL Tree and Heap-gegevensstructuur in C ++
- Bomen in C ++: basisterminologie, verplaatsingstechnieken en C ++ boomsoorten
- Oorzaak en gevolg-grafiek - Dynamische schrijftechniek voor testcases voor maximale dekking met minder testcases