Graph traversals
Graph traversal betyder at besøge hvert toppunkt og kant nøjagtigt en gang i en brønd -defineret rækkefølge. Når du bruger bestemte grafalgoritmer, skal du sikre dig, at hvert toppunkt i grafen besøges nøjagtigt en gang. Den rækkefølge, hvorpå hjørnerne er besøgt, er vigtig og kan afhænge af algoritmen eller spørgsmålet, du løser.
Under en gennemkørsel er det vigtigt, at du sporer, hvilke hjørner der er besøgt. Den mest almindelige måde at spore hjørner på er at markere dem.
Første søgning efter bredde (BFS)
Der er mange måder at krydse grafer på. BFS er den mest anvendte tilgang.
BFS er en traverseringsalgoritme, hvor du skal begynde at krydse fra en valgt node (kilde eller startknude) og krydse grafen lagvis og således udforske naboknuderne (noder, der er direkte forbundet med kildeknudepunktet). Du skal derefter bevæge dig mod nabo-noder på næste niveau.
Som navnet BFS antyder, skal du krydse grafen i bredden som følger:
- Først skal du flytte vandret og besøg alle knudepunkter i det aktuelle lag
- Gå til det næste lag
Overvej følgende diagram. 
Afstanden mellem noderne i lag 1 er sammenligneligt mindre end afstanden mellem noderne i lag 2. Derfor skal du i BFS krydse alle noderne i lag 1, før du flytter til noderne i lag 2.
Traversering af underordnede noder
En graf kan indeholde cyklusser, som kan bringe dig til den samme node igen, mens du krydser grafen. For at undgå behandling af samme node igen skal du bruge et boolsk array, der markerer noden, efter at den er behandlet. Mens du besøger noderne i laget af en graf, skal du gemme dem på en sådan måde, at du kan krydse de tilsvarende underordnede noder i en lignende rækkefølge.
For at gøre denne proces let, skal du bruge en kø til at gemme noden og markere den som “besøgt”, indtil alle dens naboer (hjørner, der er direkte forbundet med den) er markeret. Køen følger metoden First In First Out (FIFO) kø, og derfor vil nodenes havne blive besøgt i den rækkefølge, som de blev indsat i noden, dvs. noden, der blev indsat først, vil blive besøgt først, og så på.
Pseudokode
Trafikproces 
Traversering starter fra kildeknudepunktet og skubber s i kø. s vil blive markeret som “besøgt”.
Første iteration
- s poppes fra køen
- Naboerne til s dvs. 1 og 2 vil blive krydset
- 1 og 2, som ikke er gennemgået tidligere, krydses. De vil være:
- Skubbet i køen
- 1 og 2 markeres som besøgt
Anden iteration
- 1 poppes fra køen
- Naboer på 1 ie s og 3 krydses
- s ignoreres, fordi det er markeret som “besøgt”
- 3, der ikke er gennemgået tidligere, gennemkøres. Det er:
- Skubbet i køen
- Markeret som besøgt
Tredje iteration
- 2 poppes fra køen
- Naboer med 2 dvs. s, 3 og 4 krydses
- 3 og s ignoreres, fordi de er markeret som “besøgt”
- 4, der ikke er gennemgået tidligere, gennemkøres. Det er:
- Skubbet i køen
- Markeret som besøgt
Fjerde iteration
- 3 poppes fra køen
- Naboerne på 3 dvs. 1, 2 og 5 krydses
- 1 og 2 ignoreres, fordi de er markeret som “besøgt”
- 5, der ikke er gennemgået tidligere, gennemkøres. Det er:
- Skubbet i køen
- Markeret som besøgt
Femte iteration
- 4 poppes fra køen
- Naboerne på 4 dvs. 2 er krydset
- 2 ignoreres, fordi den allerede er markeret som “besøgt”
Sjette iteration
- 5 poppes fra køen
- Naboer på 5 dvs. 3 passeres
- 3 ignoreres, fordi det er allerede markeret som “besøgt”
Køen er tom, og den kommer ud af sløjfen. Alle knudepunkter er blevet krydset ved hjælp af BFS.
Hvis alle kanterne i en graf har samme vægt, kan BFS også bruges til at finde den mindste afstand mellem knudepunkterne i en graf.
Eksempel
Som i dette diagram skal du starte fra kildeknudepunktet for at finde afstanden mellem kilden node og node 1. Hvis du ikke følger BFS-algoritmen, kan du gå fra kildeknudepunktet til knudepunkt 2 og derefter til knudepunkt 1. Denne tilgang beregner afstanden mellem kildeknudepunktet og knudepunkt 1 som 2, hvorimod minimum afstand er faktisk 1. Minimumafstanden kan beregnes korrekt ved hjælp af BFS-algoritmen.
Kompleksitet
Tidskompleksiteten af BFS er O (V + E), hvor V er antallet af noder, og E er antallet af kanter.
Applikationer
1. Hvordan bestemmes niveauet for hver knude i det givne træ?
Som du ved i BFS, krydser du niveauvis. Du kan også bruge BFS til at bestemme niveauet for hver node.
Implementering
Denne kode svarer til BFS-koden med kun følgende forskel:
niveau] = niveau + 1;
I denne kode, mens du besøger hver node, indstilles niveauet for den node med en forøgelse i niveauet for dens overordnede node. Sådan bestemmes niveauet for hver node.
2 . 0-1 BFS
Denne type BFS bruges til at finde den korteste afstand mellem to noder i en graf, forudsat at kanterne i grafen har vægten 0 eller 1. Hvis du anvender BFS forklaret tidligere i denne artikel får du et forkert resultat for den optimale afstand mellem 2 noder.
I denne tilgang bruges et boolesk array ikke til at markere noden, fordi tilstanden for den optimale afstand kontrolleres, når du besøg hver knude. En dobbeltkø bruges til at gemme noden. I 0-1 BFS, hvis vægten af kanten = 0, skubbes noden til forsiden af dequeue. Hvis vægten af kanten = 1, skubbes noden til bagsiden af dequeuen.
Implementering
Q er en kø med dobbelt ende. Afstanden er en matrix, hvor afstanden indeholder afstanden fra startknudepunktet til v-knudepunktet. Oprindeligt er afstanden, der er defineret fra kildeknudepunktet til hver knude, uendelig.
Lad os forstå denne kode med følgende graf:
Tilstødelisten i grafen vil være som følger:
Her betragtes “s” som 0 eller kildeknude.
0 – > 1 – > 3 – > 2
kanter.first = 1, kanter.sekund = 1
kanter.first = 3, kanter.sekund = 0
kanter.first = 2, kanter.sekund = 1
1 – > 0 – > 4
kanter.first = 0, kanter.sekund = 1
kanter.first = 4 , sides.second = 0
2 – > 0 – > 3
kanter.first = 0 , kanter.sekund = 0
kanter.first = 3, kanter.sekund = 0
3 – > 0 – > 2 – > 4
kanter.first = 0, kanter.sekund = 0
kanter.first = 2, kanter.sekund = 0
kanter.first = 4, kanter.sekund = 0
4 – > 1 – > 3
kanter.first = 1, kanter.sekund = 0
kanter.first = 3, kanter.sekund = 0
Hvis du bruger BFS-algoritmen, bliver resultatet forkert, fordi det viser dig den optimale afstand mellem s og knude 1 og s og knude 2 som henholdsvis 1. Dette skyldes, at det besøger børn af s og beregner afstanden mellem s og dets børn, hvilket er 1. Den faktiske optimale afstand er 0 i begge tilfælde.
Behandling
Fra kildeknudepunktet, dvs. 0, bevæger den sig mod 1, 2 og 3. Da kantvægten mellem 0 og 1 og 0 og 2 er henholdsvis 1 , 1 og 2 skubbes bagest i køen. Da kantvægten mellem 0 og 3 er 0, skubbes 3 imidlertid til køens forside. Afstanden opretholdes i afstandsarrangementet i overensstemmelse hermed.
3 poppes derefter fra køen, og den samme proces vil blive anvendt på dens naboer og så videre.