新手学习BFS与DFS ? 用时4小时整理了BFS (广度优先搜索） DFS（深度优先搜索）字数已超4000字

学习C++中的BFS（广度优先搜索）与DFS（深度优先搜索）是掌握图论算法的重要一步。这两种算法在解决图遍历、路径搜索等问题时具有广泛的应用。以下是一个详细的学习指南，旨在帮助新手正确理解和应用BFS与DFS。

一、引言

在计算机科学中，BFS和DFS是两种基本的图遍历算法。它们分别通过不同的策略来访问图中的节点，适用于解决不同类型的问题。在学习这两种算法之前，了解它们的基本概念、工作原理和应用场景是非常重要的。

二、深度优先搜索（DFS）

2.1 DFS的基本概念

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。它从根（或任意节点）开始，并尽可能深地搜索树的分支，当该分支到达尽头时，它回溯到上一个节点，并继续搜索下一个分支。这种搜索方式被称为深度优先，因为它会尽可能深地搜索每个分支。

DFS常用于解决迷宫问题、图的连通性检测、拓扑排序等问题。它的工作原理可以概括为：从根（或任意节点）开始访问，标记为已访问；递归地访问当前节点的所有未访问邻居节点；当没有未访问的邻居节点时，回溯到上一个节点，继续访问其未访问的邻居节点；重复以上步骤，直到所有节点都被访问过为止。

2.2 DFS的实现方式

DFS的实现方式主要有两种：递归和迭代（使用栈）。递归方式更直观、易于理解，但可能导致栈溢出；迭代方式则通过显式地维护一个栈来避免递归带来的风险。

2.2.1 递归方式

递归方式的DFS实现相对简单。以下是一个典型的递归DFS算法代码：

#include<iostream>  
#include<vector>  
using namespace std;  
  
const int MAXN = 100; // 定义节点数量的最大值  
bool visited[MAXN]; // 记录节点是否被访问过  
vector<int> adj[MAXN]; // 邻接表，存储图的边  
  
// 递归的DFS函数  
void dfs(int node) {  
    visited[node] = true; // 标记当前节点为已访问  
    cout << node << " "; // 输出当前节点  
      
    // 递归访问当前节点的所有未访问邻居节点  
    for (int i = 0; i < adj[node].size(); i++) {  
        int neighbor = adj[node][i];  
        if (!visited[neighbor]) {  
            dfs(neighbor);  
        }  
    }  
}  
  
int main() {  
    // 初始化图（以邻接表形式）  
    // 例如，添加一条从节点0到节点1的边  
    adj[0].push_back(1);  
    adj[1].push_back(0); // 如果是无向图，需要添加反向边  
    // 添加更多边...  
      
    // 初始化visited数组为false，表示所有节点都未被访问过  
    fill(visited, visited + MAXN, false);  
      
    // 从节点0开始进行DFS遍历  
    dfs(0);  
      
    return 0;  
}

2.2.2 迭代方式

迭代方式的DFS通过显式地维护一个栈来避免递归带来的风险。以下是一个典型的迭代DFS算法：

#include<iostream>  
#include<vector>  
#include<stack>  
using namespace std;  
  
const int MAXN = 100; // 定义节点数量的最大值  
bool visited[MAXN]; // 记录节点是否被访问过  
vector<int> adj[MAXN]; // 邻接表，存储图的边  
  
// 迭代的DFS函数  
void dfs(int startNode) {  
    stack<int> stk; // 用于存储待访问的节点  
    stk.push(startNode); // 将起始节点压入栈中  
      
    while (!stk.empty()) {  
        int node = stk.top(); // 取出栈顶节点  
        stk.pop(); // 弹出栈顶节点  
          
        if (!visited[node]) {  
            visited[node] = true; // 标记当前节点为已访问  
            cout << node << " "; // 输出当前节点  
              
            // 将当前节点的所有未访问邻居节点压入栈中  
            for (int i = adj[node].size() - 1; i >= 0; i--) { // 注意这里是从后往前遍历邻接表，以避免重复压栈  
                int neighbor = adj[node][i];  
                if (!visited[neighbor]) {  
                    stk.push(neighbor);  
                }  
            }  
        }  
    }  
}  
  
int main() {  
    // 初始化图（以邻接表形式）  
    // 例如，添加一条从节点0到节点1的边  
    adj[0].push_back(1);  
    adj[1].push_back(0); // 如果是无向图，需要添加反向边  
    // 添加更多边...  
      
    // 初始化visited数组为false，表示所有节点都未被访问过  
    fill(visited, visited + MAXN, false);  
      
    // 从节点0开始进行DFS遍历  
    dfs(0);  
      
    return 0;  
}

2.3 DFS的应用场景

DFS的应用场景非常广泛，包括但不限于以下几个方面：

2.4 DFS的优缺点

DFS的优点包括：

• 简单易懂：递归方式的DFS实现简单易懂，易于理解和实现。
• 适用性广：DFS可以用于解决多种类型的问题，包括迷宫问题、图的连通性检测、拓扑排序等。
• 空间效率高：在某些情况下，DFS可以通过递归或迭代的方式实现较高的空间效率。

DFS的缺点包括：

• 可能导致栈溢出：递归方式的DFS在节点数量较多时可能导致栈溢出，需要特别注意。
• 时间复杂度高：DFS在遍历所有节点时需要回溯到上一个节点继续搜索，因此时间复杂度较高。
• 可能生成大量无效路径：在路径搜索问题中，DFS可能会生成大量无效的路径，需要通过其他条件进行筛选。

三、广度优先搜索（BFS）

3.1 BFS的基本概念

广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历或搜索树或图的算法。它从根（或任意节点）开始，首先访问根节点的所有邻居节点，然后对每个邻居节点重复此过程，直到访问完所有节点。这种搜索方式被称为广度优先，因为它会首先访问当前节点的所有邻居节点，然后再访问这些邻居节点的邻居节点。

BFS常用于解决最短路径问题、层序遍历等问题。它的工作原理可以概括为：从根（或任意节点）开始访问，将其所有未访问邻居节点加入队列；然后依次从队列中取出节点进行访问，并将其所有未访问邻居节点加入队列；重复以上步骤，直到队列为空且所有节点都被访问过为止。

3.2 BFS的实现方式

BFS的实现方式通常使用队列（Queue）来实现。以下是一个典型的BFS算法代码：

#include<iostream>  
#include<vector>  
#include<queue>  
using namespace std;  
  
const int MAXN = 100; // 定义节点数量的最大值  
bool visited[MAXN]; // 记录节点是否被访问过  
vector<int> adj[MAXN]; // 邻接表，存储图的边  
  
// BFS函数  
void bfs(int startNode) {  
    queue<int> q; // 用于存储待访问的节点  
    q.push(startNode); // 将起始节点加入队列  
    visited[startNode] = true; // 标记起始节点为已访问  
      
    while (!q.empty()) {  
        int node = q.front(); // 取出队列头节点  
        q.pop(); // 弹出队列头节点  
          
        cout << node << " "; // 输出当前节点  
          
        // 访问当前节点的所有未访问邻居节点  
        for (int i = 0; i < adj[node].size(); i++) {  
            int neighbor = adj[node][i];  
            if (!visited[neighbor]) {  
                visited[neighbor] = true; // 标记邻居节点为已访问  
                q.push(neighbor); // 将邻居节点加入

我们讲完了DFS与BFS的概念与实现方式代码，那肯定就有人会问了BFS与DFS有什么区别呢听我下面解析：
 

DFS（深度优先搜索）与BFS（广度优先搜索）是两种用于遍历或搜索树或图的算法，它们之间存在一些关键的区别。以下是对这两种算法区别的详细阐述：

一、搜索策略

1. DFS：尽可能深地搜索图的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这种策略可以形象地理解为“不撞南墙不回头”，即深入搜索一个分支直到无法继续，然后再回溯到上一个节点继续搜索其他分支。
2. BFS：从根（或某个任意节点）开始访问，并探索最近邻的节点。如果所有最近邻的节点都已被访问过，搜索将回溯到发现最近邻节点的节点。这种策略是按照层级进行遍历，先访问离起始节点最近的节点，再访问离起始节点稍远一层的节点，以此类推。

二、数据结构

1. DFS：通常使用栈（stack）来实现。因为栈是后进先出（LIFO）的数据结构，与DFS的回溯策略相匹配。在递归实现中，DFS的空间复杂度可能取决于递归调用的深度（或栈的大小）；在迭代实现中，DFS的空间复杂度通常较低。
2. BFS：通常使用队列（queue）来实现。因为队列是先进先出（FIFO）的数据结构，可以确保先访问的节点的邻居节点在后续被访问。BFS的空间复杂度可能更高，因为它需要存储当前层次的所有节点，这通常需要一个与节点数量成比例的队列空间。

三、遍历顺序

1. DFS：遍历顺序取决于搜索树的深度，通常不是按照节点的层次顺序。遍历结果可能因遍历顺序的不同而有所不同，因为DFS会深入搜索一个分支直到无法继续，然后再回溯。
2. BFS：按照节点的层次顺序遍历，即先访问所有与根节点相邻的节点，然后访问与这些节点相邻的未访问节点，以此类推。遍历结果通常是唯一的，因为BFS按照节点的层次顺序遍历，确保每个节点只被访问一次。

四、时间复杂度与适用场景

1. DFS：对于某些图，DFS可能需要更长的时间才能访问所有节点，因为它会深入搜索一个分支直到无法继续，然后再回溯。DFS适用于需要找到所有解或需要回溯的场景，如迷宫问题、图的连通性问题、拓扑排序等。
2. BFS：对于某些图，特别是当目标节点距离根节点较近时，BFS可能更快找到目标节点，因为它会首先访问所有与根节点相邻的节点。BFS适用于需要找到最短路径或最小值的场景，如网络路由、社交网络分析、最短路径问题等。

五、算法特性

1. DFS：在递归实现中，可能会遇到栈溢出的问题，特别是当图的节点数量非常多时。此外，DFS的遍历结果可能不是唯一的，因为遍历顺序可能因实现方式或图的结构而异。
2. BFS：由于需要存储当前层次的所有节点，因此空间复杂度可能较高。但是，BFS可以保证每个节点只被访问一次，且遍历结果通常是唯一的。此外，BFS还可以用于解决一些特定的问题，如最短路径问题、连通分量问题等。

综上所述，DFS与BFS在搜索策略、数据结构、遍历顺序、时间复杂度与适用场景以及算法特性等方面都存在明显的区别。在实际应用中，需要根据具体问题的特点和需求来选择合适的算法，