【GESP】C++七级考试大纲知识点梳理 (3) 图论基础与遍历算法

发表于 2026/01/21

作者 OneCoder

次浏览 16 分钟阅读

GESP C++七级考试大纲的第 3 条考点正式引入了图论 (Graph Theory)。图论是计算机科学中极其重要的数据结构，用来解决大量的“关系”问题（如地图导航、社交网络）。七级要求掌握图的基本概念、存储方式以及最核心的两种遍历算法：DFS 和 BFS。

（3）图的定义及及基本图论算法。包括图的定义、图的种类（有向图、无向图），图节点的度的概念。掌握编程时图的数据结构表示，以及基于深度优先搜索（DFS）和广度优先搜索（BFS）的图搜索与遍历方法，图的泛洪（flood fill）算法。

图论看似复杂，其实核心就两点：怎么存（建图） 和 怎么走（遍历）。掌握了邻接表和DFS/BFS，就拿到了图论世界的入场券。

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。

一、图的基本概念

1.1 图的定义

图 (Graph) 是由顶点 (Vertex) 和连接顶点的边 (Edge) 组成的集合，通常记为 $G = (V, E)$。

V：顶点集合。比如地图上的城市。
E：边集合。比如连接城市的道路。

1.2 图的种类

无向图 (Undirected Graph)：
- 边没有方向。边 $(u, v)$ 表示 $u$ 和 $v$ 互通。
- 例子：社交网络中的“好友关系”（A是B的好友，B也一定是A的好友）。
有向图 (Directed Graph)：
- 边有方向。边 $\langle u, v \rangle$ 表示从 $u$ 指向 $v$，不代表 $v$ 能回 $u$。
- 例子：微博的“关注关系”（A关注B，B不一定关注A）。
权值 (Weight)：边上可以带有数值，称为“权”。带权的图叫网 (Network)。

1.3 节点的度 (Degree)

无向图：一个顶点的度就是连接该顶点的边的数量。
有向图：分入度和出度。
- 入度 (In-degree)：有多少条边指向该顶点（箭头指进来）。
- 出度 (Out-degree)：该顶点发出多少条边（箭头指出去）。
- 总度数 = 入度 + 出度。

二、图的存储（代码实现）

在编程中，我们怎么告诉计算机“这张图长什么样”？主要有两种方式：邻接矩阵和邻接表。

2.1 邻接矩阵 (Adjacency Matrix)

使用一个二维数组 G[N][N] 来存图。

G[i][j] = 1 表示 $i$ 和 $j$ 之间有边。
G[i][j] = 0 (或 INF) 表示无边。
如果是带权图，G[i][j] 就存权值。

优缺点：

✅ 优点：查询两点是否有边非常快 $O(1)$。
❌ 缺点：太浪费空间。如果是稀疏图（点多边少），大部分空间都存了 0。空间复杂度 $O(N^2)$。如果 $N > 5000$，通常就开不下了（会爆内存）。

  
// 邻接矩阵示例
int g[1005][1005];

// 加边 (u -> v)
g[u][v] = 1; 

// 如果是无向图，记得反向也要加
g[v][u] = 1; 

2.2 邻接表 (Adjacency List) —— 推荐

使用 vector 数组来存。adj[i] 里面存的是“所有从 $i$ 出发能到达的顶点”。

优缺点：

✅ 优点：节省空间。只存实际存在的边。空间复杂度 $O(V+E)$。
❌ 缺点：查询两点是否有边稍微慢一点（需要遍历 adj[u]）。

这是七级考试和竞赛中最常用的存图方式。

  
#include <vector>
using namespace std;

const int N = 10005;
vector<int> adj[N]; // adj[u] 存储 u 的所有邻居

int main() {
    int n, m; // n个点，m条边
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        // 有向图 u -> v
        adj[u].push_back(v);
        
        // 如果是无向图，加上 v -> u
        // adj[v].push_back(u); 
    }
    return 0;
}

三、图的搜索与遍历

图建立好后，最重要的就是从某个点出发，把图里的点都走一遍。这就引出了 DFS 和 BFS。

3.1 深度优先搜索 (DFS)

1. 算法定位：

DFS 是图论中最基础、最重要的遍历算法之一。它不仅仅是“遍历”，更是许多高级算法的基石。它利用了递归的特性，能够非常方便地维护“路径”信息。

2. 核心逻辑：

策略：一条路走到黑，撞了南墙才回头。
过程：从起点出发，随意选择一条未走过的边深入，直到无路可走，然后回溯（Backtrack）到上一个节点，继续选择另一条路深入。
数据结构：栈 (Stack)。通常我们直接使用函数的递归调用（系统栈）来实现，代码极其简洁。

3. 代码实现与详解：

  
// 全局变量，记录节点访问状态
// vis[i] = true 表示节点 i 已经被访问过，防止在环中死循环
bool vis[N]; 

// u 表示当前所在的节点
void dfs(int u) {
    // 1. 【标记与访问】
    vis[u] = true;    // 进门第一件事：标记当前点已访问，表示“我来过了”
    cout << u << " "; // 在这里处理访问节点的逻辑（比如输出、计数等）

    // 2. 【遍历邻居】
    // 遍历当前节点 u 的所有邻居 v (从邻接表 adj[u] 中取出)
    for (int v : adj[u]) {
        
        // 3. 【判断与递归】
        if (!vis[v]) { // 如果邻居 v 还没有被访问过
            // 继续深入！从 v 开始继续 DFS
            // 这行代码执行完后，会一直等到以 v 为起点的所有路都走完，才会返回这里
            dfs(v); 
        }
    }
    
    // 4. 【回溯（可选）】
    // 如果需要搜索所有路径（而不是只遍历点），通常在这里把 vis[u] 改回 false
    // vis[u] = false; 
}

3.2 广度优先搜索 (BFS)

1. 算法定位：

BFS 是另一种遍历图的方式。它的最大特点是按层遍历，因此它具有一个独特的性质：在边权为 1（或无权）的图中，BFS 第一次访问到某节点时，所经过的边数一定是起点到该点的最短距离。因此，BFS 经常被用来求最短路问题。

2. 核心逻辑：

策略：层层推进，地毯式搜索。如果是平静的水面上扔一颗石子，水波纹的扩散过程就是 BFS。
过程：从起点开始，先把所有“一步能到”的点走完，再走“两步能到”的点……以此类推。
数据结构：队列 (Queue)。遵循“先进先出”原则，保证了先被发现的节点（距离近），其邻居也会先被访问。

3. 代码实现与详解：

  
#include <queue>
using namespace std;

// BFS 不需要递归，而是使用队列进行迭代
void bfs(int start) {
    // 1. 【初始化】
    queue<int> q;       // 定义一个队列
    q.push(start);      // 起点入队
    vis[start] = true;  // ⚠️ 关键点：入队时立刻标记！防止重复入队
    
    // 2. 【循环处理】
    while (!q.empty()) { // 只要队列不空，就一直搜
        
        // 3. 【取出堆头】
        int u = q.front(); // 取出队首元素
        q.pop();           // 弹出
        cout << u << " ";  // 在这里处理访问节点的逻辑

        // 4. 【扩展邻居】
        // 遍历 u 的所有邻居 v
        for (int v : adj[u]) {
            if (!vis[v]) {     // 如果邻居 v 没去过
                vis[v] = true; // ⚠️ 标记：我已经在讲解室排队了，别再拉我了
                q.push(v);     // 入队：加入下一层的待办列表
            }
        }
    }
}

易错点：BFS 中 vis[v] = true 必须在入队 (push) 时标记，而不能在出队 (pop) 时标记。否则会导致同一个点被重复加入队列很多次，导致超时 (TLE)。

四、泛洪算法 (Flood Fill)

1. 算法定位： Flood Fill（泛洪填充）本质上就是 DFS 或 BFS 在二维网格 (Grid) 上的应用。它的最经典案例就是画图软件里的“油漆桶”工具：点击一个像素，所有颜色相同且相连的区域都会被染色。在算法竞赛中，它常用于求解“岛屿数量”、“连通块大小”等问题。

2. 核心逻辑：

种子点 (Seed)：选定一个起始坐标 $(x, y)$ 作为爆发点。
扩散 (Diffuse)：像洪水决堤一样，向上下左右四个方向蔓延。
终止条件：遇到边界、障碍物（如墙壁）或不同颜色的区域，就停止蔓延。

3. 代码实现与详解：

在二维网格中，最大的特点是“点”变成了坐标 $(x, y)$，“邻居”变成了上下左右四个格子。为了写起来方便，我们通常使用方向数组来简化四个方向的枚举。

  
// 方向数组：巧妙地表示 上、下、左、右 四个方向的坐标偏移量
// dx[0]=-1, dy[0]=0  -> (x-1, y) 上
// dx[1]=1,  dy[1]=0  -> (x+1, y) 下
// ...
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 假设地图大小为 n * m，grid[x][y] 存的是颜色或地形 (0/1)
void flood_fill_dfs(int x, int y) {
    // 1. 【标记】
    vis[x][y] = true; // 既然洪水流到了这里，标记为已淹没
    
    // 2. 【扩散】
    // 利用循环枚举四个方向，比写 4 个 if 优雅得多
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i]; // 计算新坐标 (Next X)
        int ny = y + dy[i]; // 计算新坐标 (Next Y)
        
        // 3. 【判断合法性】
        // 必须通过三重考验：
        // (1) 不越界：(nx, ny) 必须在地图范围内
        // (2) 没来过：!vis[nx][ny]
        // (3) 能通过：比如 grid[nx][ny] == 1 (是陆地/相同颜色)
        if (nx >= 0 && nx < n && ny >= 0 && ny < m  // 边界检查
            && !vis[nx][ny]                         // 未访问检查
            && grid[nx][ny] == 1) {                 // 颜色/性质检查
            
            // 4. 【递归】
            flood_fill_dfs(nx, ny);
        }
    }
}

五、备考总结

熟练写邻接表：考场上极大概率用 vector<int> adj[N] 存图。
分清 DFS 和 BFS：
- 找最短路（步数最少） -> BFS。
- 找连通块、遍历所有情况 -> DFS 写法通常更短。
注意 vis 数组：图中有环，不标记 vis 会死循环。
方向数组：二维网格题（Flood Fill）记得用 dx, dy 数组简化代码，不要写四个 if。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号

GESP, 七级

GESP C++ 考试大纲图论 DFS BFS

本文由作者按照 CC BY-NC-SA 4.0 进行授权

一、图的基本概念

1.1 图的定义

1.2 图的种类

1.3 节点的度 (Degree)

二、图的存储（代码实现）

2.1 邻接矩阵 (Adjacency Matrix)

2.2 邻接表 (Adjacency List) —— 推荐

三、图的搜索与遍历

3.1 深度优先搜索 (DFS)

3.2 广度优先搜索 (BFS)

四、泛洪算法 (Flood Fill)

五、备考总结

热门标签