图的遍历

遍历一张图，即遍历所有点和出边的情况。

🌲 DFS（深度优先搜索）简介¶

DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是每次都尝试向更深的节点走。

DFS 常常与 BFS 并列讲解，但两者的应用场景通常不同。虽然它们都能用于遍历图的连通块，但很少能互相替代。

DFS 常用于：

连通块遍历
图染色
拓扑排序
强连通分量
搜索状态空间（如回溯）

需要注意的是：DFS 常常用递归实现，但“递归”和“DFS”并不等价，递归只是 DFS 的一种实现方式。

🧩 DFS 过程说明¶

DFS 最大的特点是递归地访问每个未访问的相邻节点，同时为避免重复访问，会使用一个 visited 数组做标记。伪代码如下：

DFS(v):
  vis[v] = true
  for u in adj[v]:
    if not vis[u]:
      DFS(u)

DFS 可以对图、树、二维网格等结构进行遍历，也可扩展为处理状态图（如动态规划状态转移图）。

⏱ DFS 的时间与空间复杂度¶

时间复杂度：O(n + m)，其中 n 是节点数，m 是边数。
空间复杂度：O(n)（包含递归栈空间）。

图结构若用邻接矩阵表示，边遍历复杂度变为 O(n^2)，所以推荐使用邻接表或前向星结构以实现线性时间遍历。

📌 注意：在本地调试 DFS 时，深递归可能造成栈溢出，可通过如下方式解除栈限制：

Windows: 编译选项添加 -Wl,--stack=1000000000

Linux/macOS: 终端输入 ulimit -s unlimited

🔁 DFS 实现方式¶

✅ 递归实现（邻接表）¶

vector<int> adj[N];
bool vis[N];

void dfs(int u)
{
    vis[u] = true;
    for (int v : adj[u])
    {
        if (!vis[v])
            dfs(v);
    }
}

✅ 链式前向星实现¶

void dfs(int u)
{
    vis[u] = true;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (!vis[v])
            dfs(v);
    }
}

🌊 BFS（广度优先搜索）简介¶

BFS 全称是 Breadth First Search，中文名是广度优先搜索。

BFS 每次尝试访问所有“同一层”的节点，之后再访问下一层。由于这样的层次性，它常被用来寻找最短路径（边权为 1）。

BFS 可用于：

求无权图的最短路径
连通块计数
二分图判定
拓扑排序
状态空间最短路径（如游戏最小步数）

🧩 BFS 过程说明¶

初始化队列 q，将起点 s 入队，标记为访问。
每次取出队头节点 u，访问其所有未访问的邻接点 v：
vis[v] = true
dis[v] = dis[u] + 1，记录到每个节点的距离。
pre[v] = u，记录每个结点的前驱。
入队 v
队列空时搜索结束。

✅ BFS 示例代码：¶

void bfs(int s)
{
    queue<int> q;
    q.push(s);
    vis[s] = true;
    dis[s] = 0;
    pre[s] = -1;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int v : e[u])
        {
            if (!vis[v])
            {
                vis[v] = true;
                dis[v] = dis[u] + 1;
                pre[v] = u;
                q.push(v);
            }
        }
    }
}

🔄 路径还原函数¶

void restore(int x)
{
    vector<int> res;
    for (int v = x; v != -1; v = pre[v])
        res.push_back(v);
    reverse(res.begin(), res.end());
    for (int v : res)
        cout << v << ' ';
}

⏱ BFS 的时间与空间复杂度¶

时间复杂度：O(n + m)（每个点和边各访问一次）
空间复杂度：O(n)（vis[] + 队列）

🛠 BFS 典型应用场景¶

✅ 求最短路径（边权=1）
✅ 求图的连通块数量
✅ 求最短路上的所有边/点
✅ 判断状态是否可达（例如解迷宫）
✅ 无权有向图中求最小环（从每个点做 BFS）
✅ 找一条偶数长度最短路（拆点建新图）
✅ 0/1 权图求最短路（见下文）

⚖️ 双端队列 BFS（0-1 BFS）¶

适用于边权为 0 或 1 的最短路问题。其核心思想是：

若边权为 0，将新节点加入队首
若边权为 1，将新节点加入队尾

这样可以确保队列中节点的代价单调递增，从而确保正确的最短路径。

🔀 模板伪代码：¶

while (!dq.empty())
{
    u = dq.front();
    dq.pop_front();
    for (邻居 v)
    {
        if (用 0 花费更新 v): 
        dq.push_front(v);
        else
            dq.push_back(v);
    }
}

📌 例题：洛谷 P4554 小明的游戏¶

题意：小明最近喜欢玩一个游戏。给定一个 $n \times m$ 的棋盘，上面有两种格子 # 和 @。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是 $0$，否则费用是 $1$。请编程计算从起始位置移动到目标位置的最小花费。

代码采用 0-1 BFS：下一个位置和当前相同代价为 $0$，改变则代价为 $1$。

#include <bits/stdc++.h>
using namespace std;
char a[505][505];
int dis[505][505];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int main()
{
    while (1)
    {
        memset(dis, -1, sizeof(dis));
        int n, m;
        cin >> n >> m;
        if (n == 0 && m == 0)
        {
            return 0;
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> a[i][j];
            }
        }
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        deque<array<int, 2>> q;
        q.push_front({x1, y1});
        dis[x1][y1] = 0;
        while (q.size())
        {
            auto b = q.front();
            q.pop_front();
            for (int i = 0; i < 4; i++)
            {
                int nx = b[0] + dx[i];
                int ny = b[1] + dy[i];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m && dis[nx][ny] == -1)
                {
                    dis[nx][ny] = dis[b[0]][b[1]];
                    if (a[nx][ny] == a[b[0]][b[1]])
                    {
                        q.push_front({nx, ny});
                    }
                    else
                    {
                        q.push_back({nx, ny});
                        dis[nx][ny]++;
                    }
                }
            }
        }
        cout << dis[x2][y2] << '\n';
    }
    return 0;
}

🧮 优先队列 BFS（堆优化）¶

优先队列 BFS 使用最小堆来选择当前总代价最小的节点进行扩展，具有贪心性质。

其原理与 Dijkstra 十分相似，区别在于可以扩展到某些状态图问题（例如多维状态转移），并非要求边权非负图。

优先队列的 BFS 中，每个节点可能多次入队，但只在第一次出队时处理。

✅ 优势¶

可处理复杂状态最短路径问题
常用于拓展 Dijkstra 之外的问题模型

⏱ 复杂度¶

时间复杂度：O((n + m) * log n)（每个节点入队一次 + log 操作）

✅ 总结：

DFS：适用于深度搜索、树形结构、回溯等

BFS：适用于无权图的最短路径、层次遍历

0-1 BFS：适用于边权为 0/1 的最短路径

优先队列 BFS：状态图最短路径、复杂建模

欢迎在实践中根据题意灵活选择最适合的搜索策略 🌟