以走迷宫来比喻：
深度优先搜索（DFS）：选择一条路（分支）一直走到底，直到死胡同。然后回溯到最近的一个岔路口，换另一条没走过的路继续深入。“不撞南墙不回头”。
广度优先搜索（BFS）：站在起点，先探索所有从起点能直接到达的地方（第一层）。然后从这些地方出发，再探索所有它们能直接到达的、且未被探索过的新地方（第二层）。“层层递进，地毯式搜索”。

深度优先搜索（DFS）

1. 核心思想：
   尽可能深地搜索图的分支。
   当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。
   这一过程一直进行到已发现从源节点可达的所有节点为止。
   如果还存在未被发现的节点，则选择其中一个作为新的源节点，重复上述过程。

2. 实现方式（通常）：
   递归：利用系统调用栈，代码简洁直观。
   显式栈：使用Stack数据结构手动模拟递归过程。

3. 代码框架（递归版）：

   // DFS 递归实现
    void dfsRecursive(const Graph& graph, int start, vector<bool>& visited) {
    //标记当前节点已访问
    visited[start] = true;
    cout << start << " "; //节点处理
    //递归访问所有未访问的邻居
    for (int neighbor : graph.getAdjacencyList()[start]) {
        if (!visited[neighbor]) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
   }
   //递归入口函数
    void dfsRecursive(const Graph& graph, int start) {
    vector<bool>   
    visited(graph.getVertexCount(), false);
    cout << "DFS Recursive (starting from " << start << "): ";
    dfsRecursive(graph, start, visited);
    cout << endl;
    }
   

4. 特点：
   数据结构：栈（Stack），后进先出。
   空间复杂度：在最坏情况下（一条链），需要存储整条路径上的节点，为 O(h)，其中h是图的最大深度。对于树，即树的高度。
   时间复杂度：访问每个节点和边一次，为 O(V+E)（V: 顶点数，E: 边数）。
   不保证找到最短路径。

广度优先搜索（BFS）

1. 核心思想：
   系统地展开并检查图中的所有节点，以寻找结果。
   从根节点开始，先访问所有相邻节点，再依次访问这些节点的相邻节点（即“波浪式”或“层级式”推进）。
2. 实现方式：
   队列：使用Queue数据结构（先进先出）。
3. 代码框架：

    void bfs(const Graph& graph, int start) {
    vector<bool>  
    visited(graph.getVertexCount(), false);
    queue<int> q;
    
    // 从起始节点开始
    visited[start] = true;
    q.push(start);
    
    cout << "BFS (starting from " << start << "): ";
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << current << " "; // 处理节点
        
        // 将未访问的邻居加入队列
        for (int neighbor : graph.getAdjacencyList()[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    cout << endl;
    }
   

4. 特点：
   数据结构：队列（Queue），先进先出。
   空间复杂度：在最坏情况下需要存储一整层的节点，对于一颗宽度为w的树，空间复杂度为 O(w)。对于图，在最坏情况下（如完全图）可能为 O(V)。
   时间复杂度：同样为 O(V+E)。
   天然适合寻找最短路径（在无权图中，BFS首次到达目标节点的路径就是最短路径）。

应用场景举例

DFS 典型场景：

查找图中两个节点是否连通。
拓扑排序（安排有依赖关系的任务顺序）。
查找图中的所有连通分量。
解决回溯问题（如数独、N皇后、排列组合），需要尝试所有可能性。
在二叉树中进行先序、中序、后序遍历。

BFS 典型场景：

寻找无权图中两点之间的最短路径。
二叉树的层序遍历。
广播消息/网络爬虫（从初始页面开始，一层层抓取链接）。
解决“最少步数”类问题（如华容道）。