Traversarea graficului
Traversarea graficului înseamnă vizitarea fiecărui vârf și margine exact o dată într-un puț -ordine definită. În timp ce utilizați anumiți algoritmi de grafic, trebuie să vă asigurați că fiecare vârf al graficului este vizitat exact o dată. Ordinea în care sunt vizitate vârfurile sunt importante și pot depinde de algoritmul sau întrebarea pe care o rezolvați.
În timpul unei traversări, este important să urmăriți ce vârfuri au fost vizitate. Cel mai comun mod de urmărire a vârfurilor este să le marcați.
Breadth First Search (BFS)
Există multe modalități de a parcurge grafice. BFS este cea mai frecvent utilizată abordare.
BFS este un algoritm de parcurgere în care ar trebui să începeți să treceți de la un nod selectat (sursă sau nod de pornire) și să parcurgeți graficul stratificat explorând astfel nodurile vecine (noduri care sunt conectate direct la nodul sursă). Apoi, trebuie să vă deplasați către nodurile vecine de la nivelul următor.
După cum sugerează numele BFS, vi se cere să parcurgeți graficul în funcție de lungime, după cum urmează:
- Mai întâi mișcați orizontal vizitați toate nodurile stratului curent
- Treceți la următorul strat
Luați în considerare următoarea diagramă. 
Distanța dintre nodurile din stratul 1 este comparativ mai mică decât distanța dintre nodurile din stratul 2. Prin urmare, în BFS, trebuie să traversați toate nodurile din stratul 1 înainte de a vă deplasa la nodurile din stratul 2.
Trecerea nodurilor copil
Un grafic poate conține cicluri, care vă pot aduce din nou la același nod în timp ce parcurgeți graficul. Pentru a evita din nou procesarea aceluiași nod, utilizați o matrice booleană care marchează nodul după ce este procesat. În timp ce vizitați nodurile din stratul unui grafic, stocați-le astfel încât să puteți traversa nodurile copil corespunzătoare într-o ordine similară.
Pentru a face acest proces ușor, utilizați o coadă pentru a stoca nodul și marcați-l ca „vizitat” până când toți vecinii săi (vârfurile care sunt conectate direct la acesta) sunt marcate. Coada urmează metoda de așteptare First In First Out (FIFO) și, prin urmare, vecinii nodului vor fi vizitați în ordinea în care au fost introduși în nod, adică nodul care a fost introdus primul va fi vizitat mai întâi, și așa pe.
Pseudocode
Procesul de traversare 
Traversarea va porni de la nodul sursă și va împinge s în coadă. s vor fi marcate ca „vizitate”.
Prima iterație
- s vor fi scoase din coadă
- Vecinii din s. 1 și 2 vor fi parcurși
- 1 și 2, care nu au fost parcurse anterior, sunt parcurse. Acestea vor fi:
- Apăsate în coadă
- 1 și 2 vor fi marcate ca vizitate
A doua iterație
- 1 este scos din coadă
- Vecinii cu 1 adică s și 3 sunt parcurși
- s este ignorat deoarece este marcat ca „vizitat”
- 3, care nu a fost parcurs anterior, este parcurs. Este:
- Apăsat în coadă
- Marcat ca vizitat
A treia iterație
- 2 este scos din coadă
- Vecinii de 2 adică s, 3 și 4 sunt parcurși
- 3 și s sunt ignorați deoarece sunt marcați ca „vizitați”
- 4, care nu a fost parcurs anterior, este parcurs. Este:
- Apăsat în coadă
- Marcat ca vizitat
A patra iterație
- 3 este scos din coadă
- Vecinii cu 3 adică 1, 2 și 5 sunt parcurși
- 1 și 2 sunt ignorate deoarece sunt marcate ca „vizitate”
- 5, care nu a fost parcurs anterior, este parcurs. Este:
- Apăsat în coadă
- Marcat ca vizitat
A cincea iterație
- 4 va fi scos din coadă
- Vecinii de la 4 adică 2 este parcurs
- 2 este ignorat deoarece este deja marcat ca „vizitat”
A șasea iterație
- 5 este scos din coadă
- Vecinii de la 5 adică 3 este parcurs
- 3 este ignorat deoarece este deja marcat ca „vizitat”
Coada este goală și iese din buclă. Toate nodurile au fost parcurse utilizând BFS.
Dacă toate muchiile dintr-un grafic au aceeași greutate, atunci BFS poate fi folosit și pentru a găsi distanța minimă dintre noduri într-un grafic.
Exemplu
Ca în această diagramă, începeți de la nodul sursă, pentru a găsi distanța dintre sursă nodul și nodul 1. Dacă nu urmați algoritmul BFS, puteți trece de la nodul sursă la nodul 2 și apoi la nodul 1. Această abordare va calcula distanța dintre nodul sursă și nodul 1 ca 2, în timp ce, valoarea minimă distanța este de fapt 1. Distanța minimă poate fi calculată corect utilizând algoritmul BFS.
Complexitate
Complexitatea în timp a BFS este O (V + E), unde V este numărul de noduri și E este numărul de muchii.
Aplicații
1. Cum să determinați nivelul fiecărui nod din arborele dat?
După cum știți în BFS, parcurgeți nivelul. De asemenea, puteți utiliza BFS pentru a determina nivelul fiecărui nod.
Implementare
Acest cod este similar cu codul BFS cu doar următoarea diferență:
nivel] = nivel + 1;
În acest cod, în timp ce vizitați fiecare nod, nivelul acelui nod este setat cu o creștere a nivelului nodului său părinte. Astfel se determină nivelul fiecărui nod.
2 . 0-1 BFS
Acest tip de BFS este utilizat pentru a găsi cea mai scurtă distanță între două noduri dintr-un grafic, cu condiția ca marginile din grafic să aibă greutățile 0 sau 1. Dacă aplicați BFS explicat anterior în în acest articol, veți obține un rezultat incorect pentru distanța optimă dintre 2 noduri.
În această abordare, nu se folosește o matrice booleană pentru a marca nodul, deoarece starea distanței optime va fi verificată atunci când vizitați fiecare nod. Pentru a memora nodul este utilizată o coadă dublă. În 0-1 BFS, dacă greutatea marginii este = 0, atunci nodul este împins în partea din față a colii. Dacă greutatea muchiei este = 1, atunci nodul este împins în spatele colii.
Implementare
Q este o coadă dublă. Distanța este o matrice în care, distanța va conține distanța de la nodul de pornire la nodul v. Inițial distanța definită de la nodul sursă la fiecare nod este infinită.
Să înțelegem acest cod cu următorul grafic:
Lista de adiacență a graficului va fi următoarea:
Aici „s” este considerat 0 sau nod sursă.
0 – > 1 – > 3 – > 2
margini.first = 1, margini.secund = 1
margini.first = 3, margini.secund = 0
margini.first = 2, margini.secund = 1
1 – > 0 – > 4
margini.first = 0, margini.second = 1
margini.first = 4 , margini.second = 0
2 – > 0 – > 3
margini.first = 0 , margini.secund = 0
margini.first = 3, margini.secund = 0
3 – > 0 – > 2 – > 4
margini.first = 0, margini.secund = 0
margini.first = 2, margini.secund = 0
margini.first = 4, margini.second = 0
4 – > 1 – > 3
margini.first = 1, margini.secund = 0
margini.first = 3, margini.secund = 0
Dacă utilizați algoritmul BFS, rezultatul va fi incorect deoarece vă va arăta distanța optimă între s și nodul 1 și s și nodul 2 ca 1 respectiv. Acest lucru se datorează faptului că vizitează copiii lui s și calculează distanța dintre s și copiii săi, care este 1. Distanța optimă reală este 0 în ambele cazuri.
Procesare
Pornind de la nodul sursă, adică 0, se va deplasa către 1, 2 și 3. Deoarece greutatea de la margine între 0 și 1 și 0 și 2 este respectiv 1 , 1 și 2 vor fi împinse în spatele cozii. Cu toate acestea, deoarece greutatea muchiei între 0 și 3 este 0, 3 va fi împins în partea din față a cozii. Distanța va fi menținută în matricea de distanță în consecință.
3 va fi apoi scos din coadă și același proces va fi aplicat vecinilor săi și așa mai departe.