Căutare în lățime (BFS)
Explorează un graf strat cu strat. O coadă decide care nod urmează, așa că nodurile cele mai apropiate sunt vizitate mereu primele.
- timp O(V + E)
- memorie O(V)
- folosește o coadă
Ce înseamnă acești termeni?
- Nod: un punct al grafului, desenat aici ca un cerc cu o literă.
- Muchie: o linie care unește două noduri. Aici o poți parcurge în ambele sensuri.
- Vecini: nodurile legate de un nod printr-o muchie. Sunt verificați în ordine alfabetică.
- Coadă: primul intrat, primul ieșit. BFS ia mereu nodul care a așteptat cel mai mult.
- Stivă: ultimul intrat, primul ieșit. DFS continuă mereu din nodul la care a ajuns ultima dată.
- V și E: numărul de noduri (vertices) și de muchii (edges). O(V + E) înseamnă că fiecare nod și fiecare muchie sunt tratate de un număr fix de ori.
- în coadă
- curent
- gata
- muchie din arborele de căutare
- muchie sărită
Începe de la A. Apasă pe redare sau parcurge căutarea pas cu pas.
Space: redă sau pauză. Săgețile stânga și dreapta: pas cu pas. Home și End: salt.
Încearcă: Alege graful cu două părți. La nodurile care nu sunt legate de start nu se ajunge niciodată.
Cum funcționează
BFS pune nodul de start într-o coadă. Apoi, iar și iar, ia nodul din fața cozii și adaugă vecinii lui noi la capătul ei. O coadă servește în ordinea sosirii, așa că toate nodurile aflate la o muchie distanță sunt gata înainte de orice nod aflat la două muchii. Numărul de lângă un nod e distanța lui față de start: cele mai puține muchii necesare ca să ajungi la el.
Când este o alegere bună
Folosește BFS când ai nevoie de drumul cel mai scurt în pași: cele mai puține mutări într-un puzzle, cele mai puține salturi într-o rețea, oamenii aflați la cel mult două cunoștințe distanță de tine. Pe un graf mare coada poate deveni lungă, pentru că ține un strat întreg deodată.