BFS і DFS: алгоритми обходу графа і їх складність

BFS і DFS — два фундаментальні алгоритми обходу графа. Обидва відвідують кожну вершину рівно один раз, але роблять це в різному порядку і через різні структури даних. Саме порядок обходу визначає, яка задача буде вирішена коректно, а яка ні.

Як працює BFS

BFS алгоритм (Breadth-First Search, обхід у ширину) обходить граф рівень за рівнем. Спочатку всі сусіди стартової вершини, потім їхні сусіди, і так далі. Для цього використовується черга (queue) — структура FIFO: першою обробляється вершина, яка була додана раніше за всіх.

void bfs(int src, vector<vector<int>>& adj, int V) {
    vector<bool> visited(V, false);
    queue<int> q;

    visited[src] = true;
    q.push(src);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

Черга гарантує, що вершини обробляються в порядку зростання відстані від старту. Саме це робить BFS оптимальним для пошуку найкоротшого шляху в незваженому графі.

Як працює DFS

DFS алгоритм (Depth-First Search, обхід у глибину) іде якомога глибше по одній гілці, перш ніж повернутися і спробувати іншу. Натурально реалізується рекурсивно — через стек викликів. Ітеративна версія використовує явний стек (stack) — структуру LIFO.

void dfs(int src, vector<vector<int>>& adj, int V) {
    vector<bool> visited(V, false);
    stack<int> s;

    s.push(src);

    while (!s.empty()) {
        int u = s.top();
        s.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (int v : adj[u]) {
            if (!visited[v]) {
                s.push(v);
            }
        }
    }
}

На відміну від BFS, DFS не гарантує найкоротшого шляху. Натомість він природно моделює рекурсивні структури — дерева, ієрархії, залежності.

Складність

Обидва алгоритми мають однакову часову складність: O(V + E), де V — кількість вершин, E — кількість ребер. Кожна вершина і кожне ребро обробляються рівно один раз.

Просторова складність відрізняється на практиці, хоча асимптотично теж O(V).

BFS зберігає в черзі цілий рівень графа. У широкому графі це може бути значна частина вершин одночасно. DFS зберігає лише поточний шлях від кореня до активної вершини — у вузькому глибокому графі це суттєво менше пам'яті. Але у рекурсивній реалізації DFS глибина рекурсії обмежена стеком виклику, що на великих графах може призвести до stack overflow.

BFS vs DFS

	BFS	DFS
Структура даних	Queue (FIFO)	Stack (LIFO) / рекурсія
Порядок обходу	Рівень за рівнем	Якомога глибше
Найкоротший шлях (незважений граф)	✅	❌
Time complexity	O(V + E)	O(V + E)
Space complexity	O(V)	O(V)
Практична пам'ять	Більше на широких графах	Більше на глибоких графах

Типові задачі

BFS оптимальний там, де важлива відстань або рівень досяжності: найкоротший шлях у незваженому графі, перевірка дводольності, обхід по рівнях у дереві, пошук усіх вершин на відстані k від стартової.

DFS підходить для задач, де важлива структура досяжності або порядок завершення: виявлення циклів, топологічне сортування, пошук компонент зв'язності, генерація лабіринтів, задачі на backtracking.

***

BFS і DFS вирішують одну задачу — обхід графа — але оптимізовані під різні питання. BFS відповідає на питання «як близько», DFS — на питання «чи досяжно і в якому порядку». Розуміння різниці між чергою і стеком під капотом пояснює, чому це так.

Детальніше BFS, DFS і суміжні алгоритми розбираються в модулі Graphs and Trees курсу Algorithms in Practice.