Depth-first search, DFS) один із методів обходу графа. Стратегія пошуку в глибину, як і випливає з назви, полягає в тому, щоб йти вглиб графа, наскільки це можливо. Алгоритм пошуку описується рекурсивно: перебираємо всі вихідні з аналізованої
ребра.
Чим відрізняється BFS від DFS?
DFS рухається по краях туди й назад, а BFS поширюється сусідами у пошуках мети. DFS використовує стек, а BFS – черга. Час виконання обох становить O(V + E), а просторова складність – O(V). Дані алгоритми мають різну філософію, але однаково важливі до роботи з графами. Збережена копія
Навіщо потрібен BFS?
Для чого потрібний BFS Класичним завданням вважається автоматизований пошук виходу з лабіринту. Для вирішення завдань, пов'язаних безпосередньо з теорією графів, наприклад, для пошуку компонент зв'язності. Ці завдання своєю чергою вирішуються в Data Science, теорії мереж та електроніці.