Graph traversals
Graph traversal betyr å besøke hvert toppunkt og kant nøyaktig en gang i en brønn -definert rekkefølge. Mens du bruker visse grafalgoritmer, må du sørge for at hvert toppunkt i grafen besøkes nøyaktig en gang. Rekkefølgen som hjørnene besøkes i er viktig og kan avhenge av algoritmen eller spørsmålet du løser.
Under en traversering er det viktig at du sporer hvilke hjørner som har blitt besøkt. Den vanligste måten å spore hjørner på er å merke dem.
Første søk etter bredde (BFS)
Det er mange måter å krysse grafer på. BFS er den mest brukte tilnærmingen.
BFS er en traverseringsalgoritme der du bør begynne å krysse fra en valgt node (kilde eller startnode) og krysse grafen lagvis og dermed utforske nabo-nodene (noder som er direkte koblet til kildenoden). Du må deretter bevege deg mot nabo-noder på neste nivå.
Som navnet BFS antyder, må du krysse grafen i bredden som følger:
- Først flytt horisontalt og besøk alle nodene i det gjeldende laget
- Gå til neste lag
Vurder følgende diagram. 
Avstanden mellom nodene i lag 1 er forholdsvis mindre enn avstanden mellom nodene i lag 2. Derfor må du i BFS krysse alle nodene i lag 1 før du flytter til nodene i lag 2.
Gjennomgang av underordnede noder
En graf kan inneholde sykluser, som kan føre deg til samme node igjen mens du krysser grafen. For å unngå behandling av samme node igjen, bruk en boolsk matrise som markerer noden etter at den er behandlet. Mens du besøker nodene i laget av en graf, lagrer du dem på en slik måte at du kan krysse de tilsvarende barnodene i en lignende rekkefølge.
For å gjøre denne prosessen enkel, bruk en kø for å lagre noden og merk den som «besøkt» til alle naboene (toppunktene som er direkte koblet til den) er merket. Køen følger førstemetoden First In First Out (FIFO), og derfor vil nabohavene til noden besøkes i den rekkefølgen de ble satt inn i noden, dvs. noden som ble satt inn først vil bli besøkt først, og så på.
Pseudokode
Trafikkprosess 
Traversering vil starte fra kildekoden og skyve s i kø. s vil bli merket som «besøkt».
Første iterasjon
- s poppes fra køen
- Naboene til s dvs. 1 og 2 vil bli krysset
- 1 og 2, som ikke har blitt gjennomgått tidligere, krysses. De blir:
- Skyvet i køen
- 1 og 2 vil bli markert som besøkt
Andre iterasjon
- 1 poppes fra køen
- Naboene til 1 ie s og 3 krysses
- s ignoreres fordi den er merket som «besøkt»
- 3, som ikke har blitt gjennomgått tidligere, krysses. Det er:
- Skyvet i køen
- Merket som besøkt
Tredje iterasjon
- 2 poppes fra køen
- Naboene til 2 dvs. s, 3 og 4 krysses
- 3 og s ignoreres fordi de er merket som «besøkt»
- 4, som ikke har blitt gjennomgått tidligere, krysses. Det er:
- Skyvet i køen
- Merket som besøkt
Fjerde iterasjon
- 3 poppes fra køen
- Naboene til 3 dvs. 1, 2 og 5 krysses
- 1 og 2 ignoreres fordi de er merket som «besøkt»
- 5, som ikke har blitt gjennomgått tidligere, krysses. Det er:
- Skyvet i køen
- Merket som besøkt
Femte iterasjon
- 4 poppes fra køen
- Naboene til 4 dvs. 2 er krysset
- 2 ignoreres fordi den allerede er merket som «besøkt»
Sjette iterasjon
- 5 poppes fra køen
- Naboene til 5 dvs. 3 er krysset
- 3 ignoreres fordi det er allerede merket som «besøkt»
Køen er tom og den kommer ut av sløyfen. Alle nodene har blitt krysset ved å bruke BFS.
Hvis alle kantene i en graf har samme vekt, kan BFS også brukes til å finne den minste avstanden mellom nodene i en graf.
Eksempel
Som i dette diagrammet, start fra kildenoden for å finne avstanden mellom kilden node og node 1. Hvis du ikke følger BFS-algoritmen, kan du gå fra kildenoden til node 2 og deretter til node 1. Denne tilnærmingen vil beregne avstanden mellom kildenoden og node 1 som 2, mens minimum avstand er faktisk 1. Minimumsavstanden kan beregnes riktig ved bruk av BFS-algoritmen.
Kompleksitet
Tidskompleksiteten til BFS er O (V + E), hvor V er antall noder og E er antall kanter.
Søknader
1. Hvordan bestemme nivået på hver node i det gitte treet?
Som du vet i BFS, krysser du nivåvis. Du kan også bruke BFS til å bestemme nivået på hver node.
Implementering
Denne koden ligner på BFS-koden med bare følgende forskjell:
nivå] = nivå + 1;
I denne koden, mens du besøker hver node, blir nivået til den noden satt med en økning i nivået til den overordnede noden. Slik bestemmes nivået på hver node.
2 . 0-1 BFS
Denne typen BFS brukes til å finne den korteste avstanden mellom to noder i en graf, forutsatt at kantene i grafen har vektene 0 eller 1. Hvis du bruker BFS forklart tidligere i denne artikkelen vil du få et feil resultat for den optimale avstanden mellom to noder.
I denne tilnærmingen brukes ikke en boolsk matrise for å markere noden fordi tilstanden til den optimale avstanden vil bli sjekket når du besøk hver node. En dobbeltkø er brukt til å lagre noden. I 0-1 BFS, hvis vekten av kanten = 0, skyves noden til fronten av dequeue. Hvis vekten av kanten = 1, skyves noden til baksiden av dequeue.
Implementering
Q er en dobbeltkølet kø. Avstanden er en matrise der avstanden vil inneholde avstanden fra startnoden til v-noden. Opprinnelig er avstanden som er definert fra kildenoden til hver node, uendelig.
La oss forstå denne koden med følgende graf:
Nærhetslisten til grafen vil være som følger:
Her anses «s» for å være 0 eller kildeknute.
0 – > 1 – > 3 – > 2
kanter.first = 1, kanter.sekund = 1
kanter.first = 3, kanter.sekund = 0
kanter.forst = 2, kanter.sekund = 1
1 – > 0 – > 4
kanter.first = 0, kanter.sekund = 1
kanter.first = 4 , sides.second = 0
2 – > 0 – > 3
edge.first = 0 , sides.second = 0
sides.first = 3, sides.second = 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
Edge.first = 1, Edge.second = 0
Edge.first = 3, Edge.second = 0
Hvis du bruker BFS-algoritmen, blir resultatet feil fordi det viser deg den optimale avstanden mellom s og node 1 og s og node 2 som 1 henholdsvis. Dette er fordi den besøker barna til s og beregner avstanden mellom s og barna, som er 1. Den faktiske optimale avstanden er 0 i begge tilfeller.
Behandling
Fra og med kildekoden, dvs. 0, vil den bevege seg mot 1, 2 og 3. Siden kantvekten mellom 0 og 1 og 0 og 2 er henholdsvis 1 , 1 og 2 vil bli skjøvet på baksiden av køen. Siden kantvekten mellom 0 og 3 er 0, vil 3 imidlertid skyves til forsiden av køen. Avstanden vil bli opprettholdt i avstandsoppstillingen tilsvarende.
3 vil da poppes fra køen, og den samme prosessen vil bli brukt på naboene, og så videre.