GESP 7级

图的DFS/BFS

7级 · DP/图论/搜索

📖 一句话理解

前面学了DFS和BFS的基本思想，这里把它们应用到图上。图的DFS就是"从一个节点出发，沿着边尽量深地走，走不通就回溯"；图的BFS就是"从一个节点出发，一层一层地扩展"。它们是图论算法的基础工具。
💡 为什么重要？
图的DFS/BFS能解决很多实际问题：判断两个节点是否连通、统计连通分量个数、求无权图最短路、拓扑排序等。它们是Dijkstra、Kruskal等高级算法的前置知识。GESP 7级必考。
📋 前置知识

📐 图的DFS

💻 图的DFS代码（逐行注释）
#include <iostream>
#include <vector>
using namespace std;

const int N = 105;
vector<pair<int,int>> adj[N];  // 邻接表存图
bool vis[N];                     // vis[i] = true 表示节点i已访问过
int n;                           // 节点总数

// 从节点u开始DFS
void dfs(int u) {
    vis[u] = true;        // 标记当前节点已访问

    // 遍历u的所有邻居
    for (auto [v, w] : adj[u]) {   // v是邻居节点，w是边权
        if (!vis[v]) {             // 如果邻居v还没被访问
            dfs(v);                // 递归访问v
        }
    }
}

// 调用：从某个起点开始DFS
// dfs(1);  // 从节点1开始

// 统计连通分量个数
int countComponents() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {     // 如果节点i还没被访问
            dfs(i);        // 从i开始DFS，访问整个连通分量
            cnt++;         // 连通分量数+1
        }
    }
    return cnt;
}

📐 图的BFS（无权图最短路）

💻 图的BFS代码（逐行注释）
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N = 105;
vector<pair<int,int>> adj[N];  // 邻接表存图
int dist[N];                     // dist[i] = 从起点到i的最短距离
int n;

void bfs(int start) {
    memset(dist, -1, sizeof(dist));  // 初始化为-1，表示未访问
    queue<int> q;                    // BFS用队列
    q.push(start);                   // 起点入队
    dist[start] = 0;                 // 起点距离为0

    while (!q.empty()) {             // 队列不为空就继续
        int u = q.front();           // 取出队头
        q.pop();                     // 出队

        // 遍历u的所有邻居
        for (auto [v, w] : adj[u]) {
            if (dist[v] == -1) {     // 如果v还没被访问
                dist[v] = dist[u] + 1;  // 距离 = u的距离 + 1
                q.push(v);              // v入队
            }
        }
    }
}

📊 DFS vs BFS 在图上的应用

📝 各自擅长什么？
  • DFS擅长：
    • 判断连通性：从u能到达v吗？
    • 统计连通分量
    • 找所有路径
    • 拓扑排序（配合入度）
  • BFS擅长：
    • 求最短路径（无权图）
    • 按层遍历
    • 找离起点最近的目标

🔢 例：判断二分图

给定一个图，判断能否将节点分成两组，使得每条边都连接不同组的节点。

💻 二分图判断代码
const int N = 105;
vector<int> adj[N];
int color[N];  // color[i] = 0未着色, 1红色, -1蓝色

bool dfs(int u, int c) {
    color[u] = c;  // 给当前节点着色

    for (int v : adj[u]) {
        if (color[v] == 0) {
            // 邻居未着色，递归着相反颜色
            if (!dfs(v, -c)) return false;
        } else if (color[v] == c) {
            // 邻居颜色相同 → 不是二分图
            return false;
        }
    }
    return true;
}

// 调用
// memset(color, 0, sizeof(color));
// bool isBipartite = dfs(1, 1);

🚨 易错点

⚠️ 常见错误汇总
  1. 忘记标记visited：图可能有环，不标记visited会导致无限递归或死循环！
  2. BFS中visited在入队时标记：出队时才标记会导致同一节点多次入队。
  3. 连通分量要遍历所有节点：不能只从一个节点开始DFS就完事，要遍历所有未访问的节点。
  4. 有向图和无向图的区别：无向图的邻接表每条边要存两次（正向和反向）。
  5. BFS求最短路只适用于无权图：如果边有权重，需要用Dijkstra。
  6. dist数组初始化：用-1表示未访问，不能用0（因为起点距离也是0，会搞混）。

🎯 练习建议

📝 循序渐进练习路径
  1. 先练邻接表建图：确保能熟练用vector邻接表读入图。
  2. 做基础题目：
    • P5318 查找文献（图的DFS/BFS遍历）
    • P1331 海战（连通分量计数）
    • P3366 最小生成树（后续学）
  3. 理解visited的必要性：在有环图上手动模拟不标记visited的后果。
  4. BFS求最短路练习：P1443 马的遍历（本质是图的BFS）。
← 上一个：图的存储 📖 返回主目录 下一个：最短路 · Dijkstra →