Graph traversals
Graph traversal betekent dat elk hoekpunt en elke rand precies één keer in een put wordt bezocht -gedefinieerde volgorde. Wanneer u bepaalde grafiekalgoritmen gebruikt, moet u ervoor zorgen dat elk hoekpunt van de grafiek precies één keer wordt bezocht. De volgorde waarin de hoekpunten worden bezocht, is belangrijk en kan afhangen van het algoritme of de vraag die u oplost.
Tijdens een traversal is het belangrijk dat u bijhoudt welke vertices zijn bezocht. De meest gebruikelijke manier om hoekpunten te volgen, is door ze te markeren.
Breadth First Search (BFS)
Er zijn veel manieren om door grafieken te bladeren. BFS is de meest gebruikte benadering.
BFS is een doorkruisend algoritme waarbij u moet beginnen met het doorlopen van een geselecteerd knooppunt (bron- of startknooppunt) en de grafiek laagsgewijs doorkruist, zodat u de aangrenzende knooppunten (knooppunten die rechtstreeks met het bronknooppunt zijn verbonden) verkent. U moet dan naar de aangrenzende knooppunten op het volgende niveau gaan.
Zoals de naam BFS suggereert, moet u de grafiek als volgt in de breedte doorlopen:
- Verplaats eerst horizontaal en bezoek alle knooppunten van de huidige laag
- Ga naar de volgende laag
Beschouw het volgende diagram. 
De afstand tussen de knooppunten in laag 1 is relatief kleiner dan de afstand tussen de knooppunten in laag 2. Daarom moet je in BFS alle knooppunten in laag 1 doorkruisen voordat je naar de knooppunten in laag 2 gaat.
Doorkruisen van onderliggende knooppunten
Een grafiek kan cycli bevatten, die u mogelijk weer naar hetzelfde knooppunt brengen terwijl u door de grafiek loopt. Om te voorkomen dat hetzelfde knooppunt opnieuw wordt verwerkt, gebruikt u een booleaanse array die het knooppunt markeert nadat het is verwerkt. Terwijl u de knooppunten in de laag van een grafiek bezoekt, slaat u ze zo op dat u de corresponderende onderliggende knooppunten in een vergelijkbare volgorde kunt doorlopen.
Om dit proces gemakkelijk te maken, gebruikt u een wachtrij om het knooppunt op te slaan en het als “bezocht” te markeren totdat al zijn buren (hoekpunten die er rechtstreeks mee verbonden zijn) gemarkeerd zijn. De wachtrij volgt de FIFO-wachtrijmethode (First In First Out) en daarom worden de buren van het knooppunt bezocht in de volgorde waarin ze in het knooppunt zijn ingevoegd, dwz het knooppunt dat als eerste is ingevoegd, wordt als eerste bezocht, en dus Aan.
Pseudocode
Verplaatsingsproces 
Het doorkruisen start vanaf het bronknooppunt en duwt s in de wachtrij. s worden gemarkeerd als “bezocht”.
Eerste iteratie
- s worden uit de wachtrij gehaald
- Buren van s ie 1 en 2 zullen worden doorlopen
- 1 en 2, die niet eerder zijn doorkruist, worden doorlopen. Ze worden:
- In de wachtrij geduwd
- 1 en 2 worden gemarkeerd als bezocht
Tweede iteratie
- 1 wordt uit de wachtrij gehaald
- Buren van 1 dwz s en 3 worden doorkruist
- s wordt genegeerd omdat het is gemarkeerd als “bezocht”
- 3, die nog niet eerder is doorlopen, wordt doorlopen. Het is:
- In de wachtrij geduwd
- Gemarkeerd als bezocht
Derde iteratie
- 2 wordt uit de wachtrij gehaald
- Buren van 2, dwz s, 3 en 4 worden doorkruist
- 3 en s worden genegeerd omdat ze zijn gemarkeerd als “bezocht”
- 4, die niet eerder is doorlopen, wordt doorlopen. Het is:
- In de wachtrij geduwd
- Gemarkeerd als bezocht
Vierde iteratie
- 3 wordt uit de wachtrij gehaald
- Buren van 3, dwz 1, 2 en 5 worden doorkruist
- 1 en 2 worden genegeerd omdat ze zijn gemarkeerd als “bezocht”
- 5, die nog niet eerder is doorlopen, wordt doorlopen. Het is:
- In de wachtrij geduwd
- Gemarkeerd als bezocht
Vijfde iteratie
- 4 wordt uit de wachtrij gehaald
- Buren van 4, dwz 2 wordt doorkruist
- 2 wordt genegeerd omdat het al is gemarkeerd als “bezocht”
Zesde iteratie
- 5 wordt uit de wachtrij gehaald
- Buren van 5, dwz 3 wordt doorlopen
- 3 wordt genegeerd omdat het is al gemarkeerd als “bezocht”
De wachtrij is leeg en komt uit de lus. Alle knooppunten zijn doorlopen met BFS.
Als alle randen in een grafiek hetzelfde gewicht hebben, dan kan BFS ook worden gebruikt om de minimale afstand tussen de knooppunten in een grafiek te vinden.
Voorbeeld
Begin, zoals in dit diagram, bij het bronknooppunt om de afstand tussen de bronknooppunten te vinden knooppunt en knooppunt 1. Als u het BFS-algoritme niet volgt, kunt u van het bronknooppunt naar knooppunt 2 en vervolgens naar knooppunt 1 gaan. Deze benadering berekent de afstand tussen het bronknooppunt en knooppunt 1 als 2, terwijl het minimum afstand is eigenlijk 1. De minimale afstand kan correct worden berekend met behulp van het BFS-algoritme.
Complexiteit
De tijdcomplexiteit van BFS is O (V + E), waarbij V het aantal knooppunten is en E het aantal randen.
Toepassingen
1. Hoe bepaal je het niveau van elk knooppunt in de gegeven boom?
Zoals je weet in BFS, loop je niveaugewijs door. U kunt ook BFS gebruiken om het niveau van elk knooppunt te bepalen.
Implementatie
Deze code is vergelijkbaar met de BFS-code met alleen het volgende verschil:
level] = level + 1;
In deze code wordt, terwijl u elk knooppunt bezoekt, het niveau van dat knooppunt ingesteld met een toename in het niveau van het bovenliggende knooppunt. Dit is hoe het niveau van elk knooppunt wordt bepaald.
2 . 0-1 BFS
Dit type BFS wordt gebruikt om de kortste afstand tussen twee knooppunten in een grafiek te vinden, op voorwaarde dat de randen in de grafiek de gewichten 0 of 1 hebben. Als u de BFS toepast die eerder in in dit artikel krijg je een onjuist resultaat voor de optimale afstand tussen 2 knooppunten.
In deze benadering wordt geen booleaanse array gebruikt om het knooppunt te markeren, omdat de conditie van de optimale afstand wordt gecontroleerd wanneer je bezoek elk knooppunt. Er wordt een dubbele wachtrij gebruikt om het knooppunt op te slaan. In 0-1 BFS, als het gewicht van de rand = 0, wordt het knooppunt naar de voorkant van de wachtrij geduwd. Als het gewicht van de rand = 1, wordt het knooppunt naar de achterkant van de wachtrij geduwd.
Implementatie
Q is een dubbele wachtrij. De afstand is een array waarin afstand de afstand van het startknooppunt tot het v-knooppunt bevat. Aanvankelijk is de afstand die is gedefinieerd van het bronknooppunt tot elk knooppunt oneindig.
Laten we deze code begrijpen met de volgende grafiek:
De aangrenzende lijst van de grafiek zal er als volgt uitzien:
Hier wordt “s” beschouwd als 0 of bronknooppunt.
0 – > 1 – > 3 – > 2
randen.first = 1, randen.seconde = 1
randen.first = 3, randen.seconde = 0
randen.first = 2, randen.seconde = 1
1 – > 0 – > 4
randen.first = 0, randen.second = 1
randen.first = 4 , randen.second = 0
2 – > 0 – > 3
randen.first = 0 , randen.second = 0
randen.first = 3, randen.second = 0
3 – > 0 – > 2 – > 4
randen.first = 0, randen.second = 0
randen.first = 2, randen.seconde = 0
randen.first = 4, randen.second = 0
4 – > 1 – > 3
randen.first = 1, randen.second = 0
randen.first = 3, randen.second = 0
Als u het BFS-algoritme gebruikt, is het resultaat onjuist omdat het u laat zien de optimale afstand tussen s en knooppunt 1 en s en knooppunt 2 respectievelijk als 1. Dit komt doordat het de kinderen van s bezoekt en de afstand tussen s en zijn kinderen berekent, namelijk 1. De werkelijke optimale afstand is in beide gevallen 0.
Verwerking
Beginnend vanaf het bronknooppunt, dwz 0, zal het naar 1, 2 en 3 gaan. Aangezien het randgewicht tussen 0 en 1 en 0 en 2 respectievelijk 1 is , 1 en 2 worden naar de achterkant van de wachtrij geschoven. Omdat het randgewicht tussen 0 en 3 echter 0 is, wordt 3 naar de voorkant van de wachtrij geduwd. De afstand wordt dienovereenkomstig in afstandsmatrix gehandhaafd.
3 wordt dan uit de wachtrij gehaald en hetzelfde proces wordt toegepast op de buren, enzovoort.