BFS和DFS学习笔记

上课上完要交代码，结果根本写不出来，必须狠狠学一波了

什么是BFS和DFS

BFS：广度优先搜索
DFS：深度优先搜索

BFS和DFS的基本原理

BFS使用队列来实现节点遍历，按层次遍历
DFS使用栈或递归来实现节点遍历，深度优先遍历

DFS的实现

DFS的基本思路

DFS全称为“深度优先搜索”，它是一种用于遍历或搜索树或图的算法。其基本思路是从图的一个顶点开始，深度优先地遍历整个图。具体来说，DFS从某个节点出发，沿着一条路径一直往下走，直到不能再走为止，然后回溯到上一个节点，再沿着另一条路径往下走，直到遍历完整张图为止。

DFS的基本思路可以用以下几个步骤概括：

  1. 从起点出发，将起点标记为已访问。
  2. 找到起点的所有未被访问的邻居节点，并对每个邻居节点进行如下操作：
    1. 标记该邻居节点为已访问。
    2. 以该邻居节点为起点递归进行DFS。
  3. 如果所有邻居节点都被访问过，则回溯到上一个节点，重复步骤2，直到所有节点都被访问。

DFS的基本思路比较简单，但要正确实现DFS还需要注意一些细节问题，比如如何储存图、如何避免重复访问等。接下来将详细介绍DFS的实现过程。

递归实现DFS

实现步骤：

  1. 定义一个函数dfs，接受当前节点和已访问节点的集合作为参数。

  2. 首先将当前节点标记为已访问，并输出该节点。

  3. 遍历当前节点的所有未访问过的子节点，对每个子节点进行递归调用dfs函数。

  4. 如果当前节点没有未访问过的子节点，返回上一个节点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 10005; // 最大节点数
vector<int> graph[MAXN]; // 邻接表表示图
bool visited[MAXN]; // 记录节点是否已被访问过

void bfs(int start) {
    queue<int> q; // 定义一个队列
    q.push(start); // 将起始节点加入队列
    visited[start] = true; // 标记起始节点已访问

    while (!q.empty()) { // 只要队列不为空就继续循环
        int cur = q.front(); // 取出队头节点
        q.pop(); // 弹出队头节点

        cout << cur << " "; // 访问节点

        // 将未访问过的邻居节点加入队列
        for (int i = 0; i < graph[cur].size(); i++) {
            int neighbor = graph[cur][i];
            if (!visited[neighbor]) {
                visited[neighbor] = true; // 标记节点已访问
                q.push(neighbor); // 将邻居节点加入队列
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数

    // 输入m条边，构建邻接表
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入一条边的两个端点
        graph[u].push_back(v); // 添加一条u->v的边
        graph[v].push_back(u); // 添加一条v->u的边
    }

    // 从节点1开始进行BFS遍历
    bfs(1);

    return 0;
}

非递归实现DFS

实现步骤：

  1. 定义一个布尔型数组visited，记录每个节点是否已经被访问过；
  2. 将起始节点的序号或指针入栈，并将其对应的visited值置为true；
  3. 循环执行以下操作：
    1. 判断栈是否为空，若为空则结束循环；
    2. 取出栈顶元素，并访问该节点；
    3. 遍历该节点的所有邻居节点，若该邻居节点未被访问过，则将其序号或指针入栈，并将对应的visited值置为true；
  4. 重复以上步骤，直到栈为空

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 1000; // 最大节点数
vector<int> graph[MAXN]; // 邻接表
bool visited[MAXN]; // 标记节点是否访问过

void dfs(int start) {
    stack<int> s;
    s.push(start); // 先把起点压入栈中
    while (!s.empty()) {
        int cur = s.top(); // 取出栈顶元素
        s.pop(); // 弹出栈顶元素
        if (visited[cur]) continue; // 如果当前节点已经访问过了，就继续弹出下一个节点
        visited[cur] = true; // 标记当前节点已经被访问过
        cout << cur << " "; // 输出当前节点的值
        for (int i = graph[cur].size() - 1; i >= 0; i--) { // 从后往前遍历邻接表
            int next = graph[cur][i]; // 取出下一个邻居节点
            if (!visited[next]) s.push(next); // 如果下一个邻居节点还没有访问过，就将其压入栈中
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数
    // 输入m条边，构建邻接表
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入一条边的两个端点
        graph[u].push_back(v); // 添加一条u->v的边
        graph[v].push_back(u); // 添加一条v->u的边
    }
    int start;
    cin >> start; // 输入起点
    dfs(start); // 从起点开始进行DFS遍历
    cout << endl;
    return 0;
}

DFS的时间复杂度

DFS 的时间复杂度是 O(N+M)，其中 N 表示节点数，M 表示边数。这个复杂度的计算方式是基于以下两点：

  1. 每个节点最多被访问一次。
  2. 每个边最多被访问一次。

因此，遍历整个图需要的时间复杂度为 O(N+M)。

DFS 的时间复杂度可以理解为每个节点和每条边被访问的总次数之和，每个节点最多被访问一次，每条边也最多被访问一次，因此总的访问次数就是 N+M。所以，DFS 的时间复杂度为 O(N+M)。

BFS的实现

BFS全称为“广度优先搜索”，它是一种用于遍历或搜索树或图的算法。其基本思路是从图的一个顶点开始，广度优先地遍历整个图。具体来说，BFS从某个节点出发，依次访问其所有未被访问的邻居节点，再依次访问邻居节点的邻居节点，直到遍历完整张图为止。

BFS的基本思路可以用以下几个步骤概括：

  1. 将起点入队。
  2. 从队列头部取出一个节点，将其标记为已访问。
  3. 找到该节点的所有未被访问的邻居节点，并对每个邻居节点进行如下操作：
    1. 将该邻居节点入队。
    2. 标记该邻居节点为已访问。
  4. 重复步骤2和3，直到队列为空。

BFS的基本思路比较简单，但要正确实现BFS还需要注意一些细节问题，比如如何储存图、如何避免重复访问等。接下来将详细介绍BFS的实现过程。

实现步骤：

  1. 定义一个布尔型数组visited，记录每个节点是否已经被访问过；
  2. 将起始节点的序号或指针入队列，并将其对应的visited值置为true；
  3. 循环执行以下操作：
    1. 判断队列是否为空，若为空则结束循环；
    2. 取出队头元素，并访问该节点；
    3. 遍历该节点的所有未被访问过的邻居节点，若该邻居节点未被访问过，则将其序号或指针入队列，并将对应的visited值置为true；
  4. 重复以上步骤，直到队列为空。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 10005; // 最大节点数
vector<int> graph[MAXN]; // 邻接表表示图
bool visited[MAXN]; // 记录节点是否已被访问过

void bfs(int start) {
    queue<int> q; // 定义一个队列
    q.push(start); // 将起始节点加入队列
    visited[start] = true; // 标记起始节点已访问

    while (!q.empty()) { // 只要队列不为空就继续循环
        int cur = q.front(); // 取出队头节点
        q.pop(); // 弹出队头节点

        cout << cur << " "; // 访问节点

        // 将未访问过的邻居节点加入队列
        for (int i = 0; i < graph[cur].size(); i++) {
            int neighbor = graph[cur][i];
            if (!visited[neighbor]) {
                visited[neighbor] = true; // 标记节点已访问
                q.push(neighbor); // 将邻居节点加入队列
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数

    // 输入m条边，构建邻接表
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入一条边的两个端点
        graph[u].push_back(v); // 添加一条u->v的边
        graph[v].push_back(u); // 添加一条v->u的边
    }

    // 从节点1开始进行BFS遍历
    bfs(1);

    return 0;
}

BFS的时间复杂度

和DFS相同理解

DFS和BFS时间复杂度的比较（GPT的回答

分几种情况：

  1. 对于一个有N个节点、M条边的图而言，BFS和DFS都需要访问每个节点和每条边一次，因此它们的时间复杂度都是O(N+M)。在这种情况下，BFS和DFS的时间复杂度是相同的。
  2. 当图是一个稠密图（E~V^2）时，BFS的时间复杂度可能会高于DFS，因为BFS需要维护一个队列，并且需要遍历所有的邻居节点。而DFS只需要维护一个栈，所以空间复杂度较小，更容易实现。
  3. 在一个深度很大的树中，DFS可能需要遍历整个深度，而BFS只需要遍历每个节点的子节点。因此，在这种情况下，DFS的时间复杂度可能会高于BFS。

一些要注意的点

节点是否已经被访问过：在遍历过程中，需要记录每个节点是否已经被访问过，避免重复访问同一节点，造成死循环。在DFS中，可以使用一个布尔型数组visited记录每个节点是否已经被访问过，在BFS中，可以使用一个队列queue存储已访问过的节点，避免重复入队。

图是否连通：DFS和BFS都是基于图的遍历算法，如果图不连通，那么有些节点可能无法被遍历到。在实际应用中，需要对图进行连通性检测，确保所有节点都能被遍历到。

有向图和无向图：在有向图中，遍历方向是有限制的，需要特别注意遍历顺序。在无向图中，遍历方向没有限制，需要考虑重复遍历同一节点的情况。

总结

BFS和DFS是搜索算法的基础，需要熟练掌握，尽量能亲自多打几次

需要注意DFS和BFS中的细节问题，如边界情况和标记已访问节点等