BFS/DFS Graph Traversal Visualization - Breadth-First and Depth-First

BFS (Breadth-First Search) and DFS (Depth-First Search) are two fundamental graph traversal algorithms. BFS uses a queue, expanding layer by layer; DFS uses a stack (or recursion), exploring as deep as possible.

BFS vs DFS Comparison

Feature	BFS	DFS
Data Structure	Queue (FIFO)	Stack (LIFO) / Recursion
Visit Order	Layer by layer (near to far)	Go deep, then backtrack
Shortest Path	Guaranteed (unweighted)	Not guaranteed
Space Usage	Can be large (stores entire layer)	Usually smaller

Time and Space Complexity

Metric	BFS	DFS
Time Complexity	O(V + E)	O(V + E)
Space Complexity	O(V)	O(V)

V is vertices, E is edges. Both have same time complexity, but actual space depends on graph structure.

Applications

BFS is good for:

Shortest path in unweighted graphs
'Six degrees of separation' in social networks
Shortest path in mazes
Web crawlers

DFS is good for:

Topological sorting
Cycle detection
Finding connected components
Maze solving (all paths)
Backtracking algorithms

Shortest Path Topological Sort Connectivity Maze Solving

Implementation

from collections import deque

def bfs(graph, start):
    """广度优先搜索"""
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return order


def dfs(graph, start, visited=None):
    """深度优先搜索（递归）"""
    if visited is None:
        visited = set()
    
    visited.add(start)
    order = [start]
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            order.extend(dfs(graph, neighbor, visited))
    
    return order


# 使用示例
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'], 'E': ['B'], 'F': ['C']
}
print("BFS:", bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']
print("DFS:", dfs(graph, 'A'))  # ['A', 'B', 'D', 'E', 'C', 'F']

import java.util.*;

public class BfsDfs {
    
    /**
     * 广度优先搜索
     */
    public static List<String> bfs(
            Map<String, List<String>> graph, 
            String start) {
        
        List<String> order = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        
        queue.offer(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            String node = queue.poll();
            order.add(node);
            
            for (String neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        return order;
    }
    
    /**
     * 深度优先搜索
     */
    public static void dfs(
            Map<String, List<String>> graph,
            String node,
            Set<String> visited,
            List<String> order) {
        
        visited.add(node);
        order.add(node);
        
        for (String neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited, order);
            }
        }
    }
}