DFS 与 BFS

C++ 深度优先搜索 (DFS) 和广度优先搜索 (BFS)

一、引言

在计算机科学中，深度优先搜索 (DFS) 和 广度优先搜索 (BFS) 是两种常用的图遍历算法。它们通常用于解决图论、树形结构的搜索问题，例如最短路径、连通性检测等。虽然这两种算法的基本思想都涉及到在图中遍历节点，但它们的遍历策略有很大的不同。

二、深度优先搜索（DFS）

2.1 DFS的基本概念

深度优先搜索（DFS，Depth First Search）是一种 递归 或 栈 支持的图遍历算法。它从图的一个节点开始，沿着一条路径尽可能深入直到到达叶子节点或没有未访问的相邻节点为止，然后回溯并继续尝试其他未访问的路径。

2.2 DFS的算法步骤

1. 初始化：选择一个起始节点，并将其标记为已访问。
2. 递归遍历：从当前节点出发，递归访问每个未访问的相邻节点。
3. 回溯：一旦一个节点的所有相邻节点都已访问，回溯到上一个节点，继续搜索未遍历的路径。
4. 结束条件：所有节点都被访问过时，搜索结束。

2.3 DFS的实现

DFS可以通过递归或使用显式栈来实现。下面是基于递归方式的实现：

代码示例：DFS

#include <iostream>
#include <vector>
using namespace std;
class Graph {
public:
    Graph(int V); // 构造函数，初始化图的节点数
    void addEdge(int u, int v); // 添加边
    void DFS(int start); // 从起始节点进行深度优先搜索
private:
    int V; // 节点数
    vector<vector<int>> adjList; // 邻接表表示图
    void DFSUtil(int v, vector<bool>& visited); // 辅助递归函数
};
Graph::Graph(int V) {
    this->V = V;
    adjList.resize(V);
}
void Graph::addEdge(int u, int v) {
    adjList[u].push_back(v);
    adjList[v].push_back(u); // 如果是无向图
}
void Graph::DFS(int start) {
    vector<bool> visited(V, false); // 记录节点是否访问过
    DFSUtil(start, visited);
}
void Graph::DFSUtil(int v, vector<bool>& visited) {
    visited[v] = true; // 标记当前节点为已访问
    cout << v << " "; // 访问并输出当前节点
    // 递归访问相邻节点
    for (int neighbor : adjList[v]) {
        if (!visited[neighbor]) {
            DFSUtil(neighbor, visited);
        }
    }
}
int main() {
    Graph g(5); // 创建一个有5个节点的图
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    cout << "DFS from node 0: ";
    g.DFS(0);
    return 0;
}

2.4 DFS的时间复杂度

• 时间复杂度：O(V + E)，其中V是节点数，E是边数。DFS需要访问每个节点和每条边一次。
• 空间复杂度：O(V)，需要存储每个节点的访问状态，递归调用栈的深度可能达到V。

2.5 DFS的应用场景

• 路径搜索：例如在迷宫中找到一条通路。
• 图的连通性：检测图是否是连通的。
• 拓扑排序：用于有向无环图（DAG）中的拓扑排序。
• 寻找强连通分量：用于寻找图的强连通分量。

三、广度优先搜索（BFS）

3.1 BFS的基本概念

广度优先搜索（BFS，Breadth First Search）是一种 队列 支持的图遍历算法。它从起始节点开始，首先访问该节点的所有邻居节点，然后依次访问每个邻居节点的邻居节点，直到所有可以到达的节点都被访问。

3.2 BFS的算法步骤

1. 初始化：选择一个起始节点，并将其标记为已访问，同时将其加入队列。
2. 遍历队列：从队列中取出一个节点，访问该节点并将所有未访问的相邻节点加入队列。
3. 重复：重复上述步骤，直到队列为空。
4. 结束条件：队列为空，所有节点都被访问。

3.3 BFS的实现

BFS通常使用队列来管理待访问的节点。下面是BFS的实现：

代码示例：BFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
public:
    Graph(int V); // 构造函数，初始化图的节点数
    void addEdge(int u, int v); // 添加边
    void BFS(int start); // 从起始节点进行广度优先搜索
private:
    int V; // 节点数
    vector<vector<int>> adjList; // 邻接表表示图
};
Graph::Graph(int V) {
    this->V = V;
    adjList.resize(V);
}
void Graph::addEdge(int u, int v) {
    adjList[u].push_back(v);
    adjList[v].push_back(u); // 如果是无向图
}
void Graph::BFS(int start) {
    vector<bool> visited(V, false); // 记录节点是否访问过
    queue<int> q; // 创建队列
    visited[start] = true; // 标记起始节点为已访问
    q.push(start); // 将起始节点加入队列
    while (!q.empty()) {
        int node = q.front(); // 获取队头元素
        q.pop(); // 弹出队头元素
        cout << node << " "; // 访问并输出当前节点
        // 将所有未访问的邻居加入队列
        for (int neighbor : adjList[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}
int main() {
    Graph g(5); // 创建一个有5个节点的图
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    cout << "BFS from node 0: ";
    g.BFS(0);
    return 0;
}

3.4 BFS的时间复杂度

• 时间复杂度：O(V + E)，与DFS相同，BFS也需要访问每个节点和每条边一次。
• 空间复杂度：O(V)，需要存储每个节点的访问状态和队列。

3.5 BFS的应用场景

• 最短路径问题：在无权图中，BFS可以用于寻找从起点到各个节点的最短路径。
• 图的层次遍历：例如，层次遍历树结构。
• 广度优先拓扑排序：用于有向图的拓扑排序。

四、DFS 与 BFS 的比较

4.1 选择依据

• DFS 更适用于需要深入探索的场景，如路径搜索、强连通分量检测等。
• BFS 更适用于需要找到最短路径或层次遍历的场景，如无权图的最短路径、层次遍历等。