Which algorithm finds the shortest distance in an unweighted graph, BFS or DFS?

If all weights are equal, BFS gives the shortest path in level order. DFS does not guarantee the shortest distance.

What problem types favor DFS?

DFS is often used when "going deep and coming back" is natural, such as exploring all paths, backtracking, cycle detection, and some topological sorting.

Does BFS have worse space complexity?

In the worst case, the queue must hold all nodes at one level, which can consume more memory in wide graphs. DFS depends on stack depth.

Do both need a visited array?

In graphs with cycles, visit marking is generally necessary. In trees with clear direction, it can sometimes be omitted.

[2026] BFS vs DFS Complete Comparison | Graph Traversal Selection Complete Guide

2026년 3월 30일 · 21분 읽기 · 수정 2026년 4월 7일 Beginner

이 글의 핵심

Compare BFS and DFS from the perspective of working principles, time complexity, and space complexity. Learn selection criteria for shortest path, cycle detection, and more in real-world scenarios.

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

Quick Comparison
How It Works
Time/Space Complexity
Selection by Problem Type
Implementation Code
Practical Examples
Conclusion

1. Quick Comparison

Feature	BFS	DFS
Data Structure	Queue	Stack or Recursion
Traversal Order	Level order (nearest first)	Depth first (to the end)
Shortest Path	✅ Guaranteed (unweighted graph)	❌ Not guaranteed
Memory	O(w) (width)	O(h) (height)
Implementation	Iteration	Recursion or Iteration
Use Cases	Shortest path, level traversal	Cycle detection, path existence

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

Category	BFS	DFS
Performance (Time)	Both traverse the entire graph once, O(V+E) level	Same
Performance (Space)	Queue can hold one level’s worth of nodes, burden in wide graphs	Recursion stack or explicit stack depth. Be careful of stack limits in very deep graphs
Usability	Distance/level concept directly appears in code, intuitive for shortest distance problems	Easy to dive in with one recursion, convenient for backtracking and connected components
Application Scenarios	Unweighted shortest path, bipartite graph check, level traversal	Topological 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

BFS: Breadth-First Search

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. 아래 코드는 code를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 실행 예제
Graph:
    1
   / \
  2   3
 / \   \
4   5   6
BFS Order: 1 → 2 → 3 → 4 → 5 → 6
(Level 0) (Level 1) (Level 2)

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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);
            }
        }
    }
}

DFS: Depth-First Search

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. 아래 코드는 code를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 실행 예제
Graph:
    1
   / \
  2   3
 / \   \
4   5   6
DFS Order: 1 → 2 → 4 → 5 → 3 → 6
(Depth first)

아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

아래 코드는 code를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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 Shape	BFS Memory	DFS Memory	Favorable
Complete Binary Tree (height h)	O(2^h)	O(h)	DFS
Linear (1→2→3→…→n)	O(1)	O(n)	BFS
General Graph	O(V)	O(V)	Similar

4. Selection by Problem Type

When to Use BFS

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;
   }

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

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;
   }

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;
   }

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

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

#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

아래 코드는 mermaid를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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 Type	Algorithm	Reason
Shortest Path (unweighted)	BFS	Level order guarantee
Shortest Path (weighted)	Dijkstra	BFS variant
Path Existence	DFS	Memory efficient
Find All Paths	DFS	Backtracking
Cycle Detection	DFS	Use recursion stack
Topological Sort	DFS	Post-order
Number of Connected Components	DFS	Simple implementation
Bipartite Graph Check	BFS	Level distinction

Conclusion

The key points when choosing between BFS and DFS:

If you need shortest path (unweighted) → BFS is correct.
If reachability or structural exploration is central → DFS is often easier to handle.
For memory, queue (BFS) and stack (DFS) burdens differ depending on whether the graph is wide or deep, so always check constraints.
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.

Keywords

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