BFS vs DFS Complete Comparison | Graph Traversal Selection Guide

· 21분 읽기 · 수정 Beginner
BFS vs DFS Complete Comparison | Graph Traversal Selection Guide

이 글의 핵심

BFS vs DFS complete comparison - working principles, complexity, and practical selection criteria

Introduction

“Should I use BFS or DFS?” This is the most common question when solving graph problems. In this article, we’ll clearly understand the differences between BFS and DFS and learn how to choose the right algorithm for different problem types.

To use an analogy, BFS is like an elevator guide that checks all the same distance (floor) first, while DFS is like maze exploration or backtracking that follows one branch to the end before returning. If shortest distance is important, use the level-spreading approach (BFS); if you need to deeply test all branches, use the one-branch-at-a-time approach (DFS).

What You’ll Learn

  • Understand the working principles of BFS and DFS
  • Compare time and space complexity differences
  • Learn selection criteria for problem types like shortest path and cycle detection
  • Follow the flow of practical implementation code

Table of Contents

  1. Quick Comparison
  2. How It Works
  3. Time/Space Complexity
  4. Selection by Problem Type
  5. Implementation Code
  6. Practical Examples
  7. Conclusion

1. Quick Comparison

FeatureBFSDFS
Data StructureQueueStack or Recursion
Traversal OrderLevel order (nearest first)Depth first (to the end)
Shortest Path✅ Guaranteed (unweighted graph)❌ Not guaranteed
MemoryO(w) (width)O(h) (height)
ImplementationIterationRecursion or Iteration
Use CasesShortest path, level traversalCycle detection, path existence

Performance, Usability, and Application Scenarios (At a Glance)

CategoryBFSDFS
Performance (Time)Both traverse the entire graph once, O(V+E) levelSame
Performance (Space)Queue can hold one level’s worth of nodes, burden in wide graphsRecursion stack or explicit stack depth. Be careful of stack limits in very deep graphs
UsabilityDistance/level concept directly appears in code, intuitive for shortest distance problemsEasy to dive in with one recursion, convenient for backtracking and connected components
Application ScenariosUnweighted shortest path, bipartite graph check, level traversalTopological sort, cycle/strongly connected components, “all cases” exploration

When to Use BFS, When to Use DFS?

  • Consider BFS when: You need minimum moves or minimum edges from a starting point, or when you need to process nearest vertices first.
  • Consider DFS when: Rather than shortest distance, reachability, all paths/combinations, or structural properties of trees/graphs (cycles, topological order) are key.
  • For problems where both work, consider implementation difficulty and memory constraints (DFS may be more favorable for wide graphs).

2. How It Works

Code Flow: Put the starting vertex in the queue and mark it as visited, then take vertices from the front of the queue and add unvisited adjacent vertices to the queue. This visits nearest distances first in order.

Graph:
    1
   / \
  2   3
 / \   \
4   5   6

BFS Order: 1 → 2 → 3 → 4 → 5 → 6
(Level 0) (Level 1) (Level 2)
void BFS(int start) {
    queue<int> q;
    vector<bool> visited(n, false);
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        cout << u << " ";
        
        // Explore adjacent vertices
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

Code Flow: Mark the current vertex as visited, then recursively dive first into unvisited adjacent vertices. Since it goes to the end of one branch before moving to other siblings, the visit order differs from BFS.

Graph:
    1
   / \
  2   3
 / \   \
4   5   6

DFS Order: 1 → 2 → 4 → 5 → 3 → 6
(Depth first)
void DFS(int u, vector<bool>& visited) {
    visited[u] = true;
    cout << u << " ";
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            DFS(v, visited);
        }
    }
}

3. Time/Space Complexity

Time Complexity

Both O(V + E)

  • V: Number of vertices
  • E: Number of edges
  • Visit all vertices and edges once

Space Complexity

Graph (Complete Binary Tree):
        1
       / \
      2   3
     / \ / \
    4  5 6  7

BFS Queue Max Size: 4 (last level)
DFS Stack Max Size: 3 (tree height)

BFS: O(w) - w is the maximum width of the graph
DFS: O(h) - h is the maximum depth of the graph

Memory Comparison

Graph ShapeBFS MemoryDFS MemoryFavorable
Complete Binary Tree (height h)O(2^h)O(h)DFS
Linear (1→2→3→…→n)O(1)O(n)BFS
General GraphO(V)O(V)Similar

4. Selection by Problem Type

When to Use BFS

  1. Shortest Path (unweighted graph)

    // Minimum moves to escape maze
int shortestPath(int start, int end) {
    queue<pair<int,int>> q; // {vertex, distance}
    q.push({start, 0});
    visited[start] = true;
    
    while (!q.empty()) {
        auto [u, dist] = q.front();
        q.pop();
        
        if (u == end) return dist; // Shortest distance guaranteed
        
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push({v, dist + 1});
            }
        }
    }
    return -1;
}

  2. Level Order Traversal

    // Print tree by level
void levelOrder(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            
            cout << node->val << " ";
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << "\n"; // Level separator
    }
}

When to Use DFS

  1. Path Existence

    // Check if path exists (shortest path not needed)
bool hasPath(int start, int end) {
    if (start == end) return true;
    visited[start] = true;
    
    for (int v : adj[start]) {
        if (!visited[v] && hasPath(v, end)) {
            return true;
        }
    }
    return false;
}

  2. Cycle Detection

    bool hasCycle(int u, int parent) {
    visited[u] = true;
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (hasCycle(v, u)) return true;
        } else if (v != parent) {
            return true; // Cycle found
        }
    }
    return false;
}

  3. Topological Sort

    void topologicalSort(int u) {
    visited[u] = true;
    
    for (int v : adj[u]) {
        if (!visited[v]) {
            topologicalSort(v);
        }
    }
    
    result.push_back(u); // Post-order
}

5. Implementation Code

BFS Template

#include <queue>
#include <vector>

void BFS(int start) {
    queue<int> q;
    vector<bool> visited(n, false);
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        // Process
        process(u);
        
        // Adjacent vertices
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

DFS Template (Recursive)

void DFS(int u, vector<bool>& visited) {
    visited[u] = true;
    
    // Process
    process(u);
    
    // Adjacent vertices
    for (int v : adj[u]) {
        if (!visited[v]) {
            DFS(v, visited);
        }
    }
}

DFS Template (Iterative)

#include <stack>

void DFS_iterative(int start) {
    stack<int> stk;
    vector<bool> visited(n, false);
    
    stk.push(start);
    
    while (!stk.empty()) {
        int u = stk.top();
        stk.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        
        // Process
        process(u);
        
        // Adjacent vertices (push in reverse order for same order as recursion)
        for (int i = adj[u].size() - 1; i >= 0; i--) {
            int v = adj[u][i];
            if (!visited[v]) {
                stk.push(v);
            }
        }
    }
}

6. Practical Examples

Example 1: Maze Escape (BFS)

// Shortest path → BFS
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int shortestPath(vector<vector<int>>& maze) {
    int n = maze.size(), m = maze[0].size();
    queue<tuple<int,int,int>> q; // {x, y, distance}
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    
    q.push({0, 0, 0});
    visited[0][0] = true;
    
    while (!q.empty()) {
        auto [x, y, dist] = q.front();
        q.pop();
        
        if (x == n-1 && y == m-1) return dist; // Arrived
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                !visited[nx][ny] && maze[nx][ny] == 0) {
                visited[nx][ny] = true;
                q.push({nx, ny, dist + 1});
            }
        }
    }
    
    return -1; // No path
}

Example 2: Number of Islands (DFS)

// Number of connected components → DFS
void DFS(vector<vector<int>>& grid, int x, int y) {
    int n = grid.size(), m = grid[0].size();
    
    if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
        return;
    }
    
    grid[x][y] = 0; // Mark as visited
    
    // Explore four directions
    DFS(grid, x+1, y);
    DFS(grid, x-1, y);
    DFS(grid, x, y+1);
    DFS(grid, x, y-1);
}

int numIslands(vector<vector<int>>& grid) {
    int count = 0;
    
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == 1) {
                DFS(grid, i, j);
                count++;
            }
        }
    }
    
    return count;
}

7. Selection Criteria Summary

Flowchart

graph TD
    A[Graph Traversal Problem] --> B{Shortest Path?}
    B -->|Yes| C[BFS]
    B -->|No| D{Explore All Paths?}
    D -->|Yes| E[DFS]
    D -->|No| F{Memory Constraint?}
    F -->|Wide Graph| E
    F -->|Deep Graph| C

Selection Table by Problem Type

Problem TypeAlgorithmReason
Shortest Path (unweighted)BFSLevel order guarantee
Shortest Path (weighted)DijkstraBFS variant
Path ExistenceDFSMemory efficient
Find All PathsDFSBacktracking
Cycle DetectionDFSUse recursion stack
Topological SortDFSPost-order
Number of Connected ComponentsDFSSimple implementation
Bipartite Graph CheckBFSLevel distinction

Conclusion

The key points when choosing between BFS and DFS:

  1. If you need shortest path (unweighted) → BFS is correct.
  2. If reachability or structural exploration is central → DFS is often easier to handle.
  3. For memory, queue (BFS) and stack (DFS) burdens differ depending on whether the graph is wide or deep, so always check constraints.
  4. For implementation convenience, match it to the problem type (backtracking uses DFS, etc.).

Summary: Both have the same time O(V+E), but if shortest distance is the answer condition, prioritize BFS.

FAQ

Q1. Does BFS always guarantee the shortest path?

Only in unweighted graphs. For weighted graphs, use Dijkstra.

Q2. Is DFS only implemented with recursion?

It can also be implemented with iteration using a stack. Recursion is simpler but watch for stack overflow.

Q3. Which one to use for problems where both work?

Choose the one that’s easier to implement. Performance difference is minimal.

  • Graph Basics
  • Shortest Path Algorithms
  • Topological Sort

Keywords

Algorithm, BFS, DFS, Graph, Traversal, Shortest Path, Cycle, Topological Sort, Comparison, Selection Guide