Поиск в ширину (BFS)
Обход графа, который посещает все узлы одной глубины, прежде чем перейти к следующей. Реализуется с помощью очереди FIFO.
Гарантированно находит кратчайший путь в невзвешенном графе. Классические применения: минимальное число переходов между узлами («три рукопожатия» в LinkedIn), веб-краулинг, обход дерева по уровням, игровой ИИ, выигрывающий за наименьшее число ходов.
Временная сложность O(V+E), память в худшем случае O(V). Конкуренты: DFS (стек вместо очереди, сначала вглубь) и алгоритм Дейкстры (если у рёбер есть веса).