Przeszukiwanie wszerz (BFS)
Przechodzenie grafu, które odwiedza wszystkie węzły na jednej głębokości, zanim przejdzie do następnej. Realizowane kolejką FIFO.
Gwarantuje najkrótszą ścieżkę w grafie bez wag. Klasyczne zastosowania: najmniejsza liczba skoków między węzłami („3 stopnie” na LinkedIn), crawling stron, przechodzenie drzewa poziomami, SI w grach typu „wygraj w jak najmniejszej liczbie ruchów”.
Złożoność czasowa O(V+E), pamięciowa w najgorszym razie O(V). Konkurenci: DFS (stos zamiast kolejki, najpierw w głąb), Dijkstra (gdy krawędzie mają wagi).