第4章图的定义及遍历

🎯 本章学习目标

通过本章的学习，你将能够：

理解图的基本概念：掌握顶点、边、度、有向图、无向图等核心术语
掌握邻接矩阵：理解邻接矩阵的存储方式、适用场景和空间复杂度
掌握邻接表：理解邻接表的存储方式、适用场景和空间复杂度
精通DFS：能用递归实现深度优先搜索，掌握visited标记
精通BFS：能用队列实现广度优先搜索，掌握距离数组
对比DFS和BFS：清楚两者的区别、适用场景和复杂度
理解连通图概念：知道连通图、连通分量的含义
掌握图的度：能计算有向图和无向图的入度、出度、总度数
选择存储方式：能根据图的稀疏/稠密选择合适的存储方式
应对真题题型：能解决选择、判断、编程等各类图的题目

🗺️ 本章知识图谱

图的定义及遍历
├── 图的基本概念
│   ├── 顶点（Vertex）
│   ├── 边（Edge）
│   ├── 有向图 vs 无向图
│   ├── 度（Degree）
│   │   ├── 无向图：顶点的边数
│   │   └── 有向图：入度 + 出度
│   ├── 连通图 / 非连通图
│   ├── 连通分量
│   └── 完全图
├── 图的存储方式
│   ├── 邻接矩阵
│   │   ├── 二维数组 g[n][n]
│   │   ├── g[i][j]=1 表示有边
│   │   ├── 空间：O(n²)
│   │   └── 适合：稠密图
│   └── 邻接表
│       ├── vector<int> adj[n]
│       ├── 每个顶点存它的邻居
│       ├── 空间：O(n+m)
│       ├── 适合：稀疏图
│       └── 无向图：每条边存两次
├── DFS 深度优先搜索
│   ├── 核心思想：一条路走到黑，碰壁回头
│   ├── 实现：递归 / 栈
│   ├── 模板
│   │   ├── 标记 visited
│   │   ├── 遍历所有邻接点
│   │   └── 未访问则递归
│   ├── 适用场景
│   │   ├── 连通性检测
│   │   ├── 路径搜索
│   │   └── 连通块数量
│   └── 空间复杂度：O(深度)
├── BFS 广度优先搜索
│   ├── 核心思想：层序扩散，先近后远
│   ├── 实现：队列
│   ├── 模板
│   │   ├── 起点入队+标记
│   │   ├── 出队访问
│   │   └── 未访问邻接点入队
│   ├── 距离数组 dist[]
│   │   ├── 初始值 -1（未访问）
│   │   └── dist[邻居] = dist[当前] + 1
│   ├── 适用场景
│   │   ├── 无权图最短路径
│   │   └── 层序遍历
│   └── 空间复杂度：O(n)
├── DFS vs BFS 对比
│   ├── 数据结构：栈 vs 队列
│   ├── 空间：DFS通常更省
│   ├── 最短路径：BFS擅长
│   └── 所有方案：DFS擅长
└── visited 数组
    ├── 防止重复访问
    ├── DFS和BFS都需要
    └── 大小为顶点数

一、📖 为什么要学"图"？

如果说树是"一脉相承"的层级结构，那么图就是"万物互联"的网状结构。社交网络中谁认识谁、地图导航中城市间的路线、课程之间的先修关系……都是图的实际应用。

GESP七级考纲中，图的定义及遍历是图论模块的第一道门槛，也是后续最短路径、最小生成树等高级算法的基础。掌握好本章，后面会轻松很多。

二、🧱 图的基本概念

2.1 什么是图？

图（Graph） 由两部分组成：

顶点集合 V（Vertex）：图中的节点
边集合 E（Edge）：连接节点的线

记作 G = (V, E)。

2.2 有向图 vs 无向图

特性	无向图	有向图
边的方向	无方向，(u,v) 等价于 (v,u)	有方向，`<u,v>` 不等于 `<v,u>`
示例	好友关系、城市间公路	关注关系、课程先修
画法	普通线段	带箭头的线

2.3 度、入度、出度

度（Degree）：与某顶点相连的边数
入度（In-degree）：有向图中，指向该顶点的边数
出度（Out-degree）：有向图中，从该顶点出发的边数

💡 握手定理：无向图中所有顶点的度数之和 = 2 × 边数。有向图中，入度之和 = 出度之和 = 边数。

2.4 连通图与连通分量

连通图：无向图中任意两个顶点之间都有路径相通
连通分量：无向图中的极大连通子图（不能再加入更多顶点仍保持连通）

📚 拓展 · 超纲：本节出现的拓扑排序、强连通分量、最小生成树（Kruskal）、带权图最短路（Dijkstra）均超出七级考纲（七级只要求图的定义、存储与 DFS/BFS 遍历 + 泛洪算法）。了解名词即可，不要求实现。

强连通：有向图中任意两个顶点互相可达，称为强连通图
强连通分量：有向图中的极大强连通子图

2.5 常见图论术语速查表

术语	含义	考法提示
完全图	任意两个顶点之间都有边。无向完全图有 n(n-1)/2 条边；有向完全图有 n(n-1) 条边	选择题常考边数计算
稀疏图	边数远小于 n²（或 E = O(n)，与顶点数同阶）的图	决定用邻接表存储
稠密图	边数接近 n² 的图	决定用邻接矩阵存储
子图	顶点和边都是原图子集的图	判断题常考定义
路径	顶点序列，相邻顶点间有边相连	—
简单路径	路径中除起点终点外不重复经过同一顶点	常考概念辨析
环	起点与终点相同的路径	DFS 环检测的考点基础
带权图	每条边有一个权值（如距离、费用）	后续最短路径的基础

⚠️ 高频易错点：判断题中常出现"连通分量是极小连通子图"——错误！ 连通分量是极大连通子图，"极大"指不能再加入更多顶点。

三、💾 图的存储方式

3.1 邻接矩阵

用二维数组 g[i][j] 表示顶点 i 到 j 是否有边（或边的权值）。

cpp

const int MAXN = 1005;
int g[MAXN][MAXN];  // g[i][j] = 1表示有边，0表示无边（带权图则存权值）
int n, m;           // n个顶点，m条边

void initGraph() {
    memset(g, 0, sizeof(g));
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = w;       // 有向图
        // g[v][u] = w;    // 无向图需加这一行
    }
}

// 遍历顶点u的所有邻接点
void traverseNeighbors(int u) {
    for (int v = 1; v <= n; v++) {
        if (g[u][v] != 0) {
            cout << u << " -> " << v << " (w=" << g[u][v] << ")" << endl;
        }
    }
}

对比项	说明
✅ 优点	实现简单；查边 O(1)；适合稠密图
❌ 缺点	空间 O(n²)；稀疏图浪费严重；遍历邻接点 O(n)
🎯 适用	稠密图、顶点数较少（n ≤ 1000）的场景

⚠️ 考试易错：邻接矩阵存储无向图时，矩阵是对称的。选择题常考"无向图的邻接矩阵性质"。

3.2 邻接表（链式前向星实现）

链式前向星是竞赛和考试中最常用的邻接表实现方式，用数组模拟链表，高效且不依赖指针。

cpp

const int MAXN = 100005;
const int MAXM = 200005;  // 无向图边数×2

int head[MAXN];  // head[u]指向u的第一条边
int to[MAXM];    // to[i]表示第i条边的终点
int nxt[MAXM];   // nxt[i]表示与第i条边同起点的下一条边
int weight[MAXM];// 边的权值
int cnt = 0;     // 边的计数器

void addEdge(int u, int v, int w) {
    to[cnt] = v;
    weight[cnt] = w;
    nxt[cnt] = head[u];  // 新边指向原来的第一条边
    head[u] = cnt++;     // head[u]更新为新边
}

void initGraph() {
    memset(head, -1, sizeof(head));  // -1表示无边
    cnt = 0;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        // addEdge(v, u, w);  // 无向图需加这一行
    }
}

// 遍历顶点u的所有邻接点
void traverseNeighbors(int u) {
    for (int i = head[u]; i != -1; i = nxt[i]) {
        cout << u << " -> " << to[i] << " (w=" << weight[i] << ")" << endl;
    }
}

对比项	说明
✅ 优点	空间 O(n+m)；遍历邻接点高效 O(度数)；适合稀疏图
❌ 缺点	查特定边 O(度数)；实现稍复杂
🎯 适用	稀疏图、顶点数大的场景（n 可达 10⁵+）

💡 记忆口诀：链式前向星 = "头插法建链表"。新边总是插到链表头部，所以遍历时边的顺序与输入顺序相反。

3.3 邻接表（vector 实现）

链式前向星虽然高效，但写起来略繁琐。在实际编程和日常刷题中，用 vector 数组实现的邻接表更常见——写法简洁、不用手动管理数组大小，C++ STL 帮你搞定一切。

基本原理

用一个一维数组（其实是 vector 数组），每个位置 u 对应一个 vector，里面存着从 u 出发的所有邻居。

🍎 生活比喻：就像一个班级有 n 个小组，每个小组有一本"好友通讯录"。想知道 3 号同学的朋友有哪些？直接翻开 3 号的通讯录挨个看就行。通讯录可以随时添加新朋友，不用提前知道有多少人。

代码实现（带权图）

cpp

#include <vector>
using namespace std;

const int MAXN = 100005;

// 每个顶点对应一个 vector，存 pair<终点, 权值>
vector<pair<int, int>> adj[MAXN];

int n, m;  // 顶点数、边数

// 添加一条从 u 到 v、权值为 w 的边
void addEdge(int u, int v, int w) {
    adj[u].push_back({v, w});
}

// 初始化图
void initGraph() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);  // 无向图：反向再加一条
    }
}

// 遍历顶点 u 的所有邻接点
void traverseNeighbors(int u) {
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].first;   // 邻接点编号
        int w = adj[u][i].second;  // 边权
        cout << u << " -> " << v << " (w=" << w << ")" << endl;
    }
}

更简洁的写法：范围 for 循环

C++11 以后，可以用范围 for 遍历 vector，代码更清爽：

cpp

// 遍历顶点 u 的所有邻接点（C++11 推荐写法）
for (auto &edge : adj[u]) {
    int v = edge.first;
    int w = edge.second;
    cout << u << " -> " << v << " (w=" << w << ")" << endl;
}

不带权图的简化版

如果图没有权值，可以直接存 int，代码更短：

cpp

vector<int> adj[MAXN];  // 每个顶点的邻居列表

void addEdge(int u, int v) {
    adj[u].push_back(v);
}

对比项	说明
✅ 优点	写法最简单直观；不用手动管理内存；边的顺序与输入一致；可以随机访问第 k 条边
❌ 缺点	速度略慢于链式前向星（但绝大多数场景感觉不到）；顶点编号必须是连续整数
🎯 适用	日常刷题、算法竞赛、教学演示；绝大多数图论题都够用

🔥 高频考点：GESP 七级考试中，vector 邻接表和链式前向星都可能出现。选择题常考两者的区别，编程题写哪种都行——推荐 vector 版，写得快不容易错。

💡 链式前向星 vs vector 邻接表怎么选？
平时刷题/考试：首选 vector 版，写得快、不易错、调试方便
顶点数特别大（10⁵+）且卡常：用链式前向星，速度略快
需要反向遍历：链式前向星遍历顺序与输入相反，vector 与输入相同

3.4 边集数组

最简单的存储方式：直接用一个数组存所有边。

cpp

const int MAXM = 200005;

struct Edge {
    int u, v, w;  // 起点、终点、权值
} edges[MAXM];

int n, m;

void initGraph() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
}

对比项	说明
✅ 优点	实现最简单；适合按边处理的算法（如 Kruskal、Bellman-Ford）
❌ 缺点	查邻接点需遍历所有边 O(m)；不适合遍历操作
🎯 适用	需要对边排序或逐边处理的算法

3.5 四种存储方式总结

存储方式	空间复杂度	查边	遍历邻接点	实现难度	适用场景
邻接矩阵	O(n²)	O(1)	O(n)	⭐ 最简单	稠密图、小图（n≤500）
邻接表（链式前向星）	O(n+m)	O(度数)	O(度数)	⭐⭐⭐ 较难	稀疏图、大图、卡常场景
邻接表（vector 版）	O(n+m)	O(度数)	O(度数)	⭐⭐ 简单	日常刷题、考试、绝大多数场景
边集数组	O(m)	O(m)	O(m)	⭐ 最简单	按边处理算法（Kruskal 等）

💡 一句话选型：
题目说"顶点数 n ≤ 500" → 邻接矩阵就行
题目说"n ≤ 10⁵, m ≤ 2×10⁵" → vector 邻接表，又快又稳
算法需要按边排序（如 Kruskal） → 边集数组
实在卡时间卡空间 → 链式前向星

四、🔍 DFS 深度优先搜索

4.1 核心思想

"一条路走到黑，碰壁再回头" —— 沿着一条路尽可能深入，走到死路就回溯，尝试其他分支。

4.2 递归实现模板

cpp

const int MAXN = 100005;
int head[MAXN], to[MAXM], nxt[MAXM], cnt;
bool visited[MAXN];

void addEdge(int u, int v) {
    to[cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt++;
}

// 递归DFS
void dfs(int u) {
    visited[u] = true;       // 标记当前顶点已访问
    cout << u << " ";        // 访问操作（按需修改）

    for (int i = head[u]; i != -1; i = nxt[i]) {
        int v = to[i];
        if (!visited[v]) {
            dfs(v);          // 递归访问未访问的邻接点
        }
    }
}

// 遍历整个图（处理非连通图）
void dfsAll(int n) {
    memset(visited, false, sizeof(visited));
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
}

4.3 非递归（栈）实现

当图很深时，递归可能栈溢出，需要用显式栈实现：

cpp

#include <stack>

void dfsStack(int start, int n) {
    memset(visited, false, sizeof(visited));
    stack<int> stk;
    stk.push(start);
    visited[start] = true;

    while (!stk.empty()) {
        int u = stk.top();
        stk.pop();
        cout << u << " ";

        for (int i = head[u]; i != -1; i = nxt[i]) {
            int v = to[i];
            if (!visited[v]) {
                visited[v] = true;   // 入栈即标记，避免重复入栈
                stk.push(v);
            }
        }
    }
}

⚠️ 高频易错点：非递归 DFS 中，入栈时就要标记 visited，而不是出栈时才标记！否则同一顶点可能被多次入栈，导致重复访问。

4.4 DFS 应用场景

① 连通性判断

cpp

// 判断u和v是否连通：从u出发DFS，看能否到达v
bool isConnected(int u, int v, int n) {
    memset(visited, false, sizeof(visited));
    dfs(u);
    return visited[v];
}

// 统计连通分量个数
int countComponents(int n) {
    memset(visited, false, sizeof(visited));
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            count++;
            dfs(i);
        }
    }
    return count;
}

② 环检测（无向图）

cpp

// parent记录来源顶点，避免走回头路造成误判
bool hasCycleDFS(int u, int parent) {
    visited[u] = true;
    for (int i = head[u]; i != -1; i = nxt[i]) {
        int v = to[i];
        if (!visited[v]) {
            if (hasCycleDFS(v, u)) return true;
        } else if (v != parent) {
            // 访问到的不是父节点，说明有环
            return true;
        }
    }
    return false;
}

⚠️ 考试易错：无向图环检测必须传 parent 参数！否则 u→v→u 会被误判为环。

③ 拓扑排序（有向无环图） 📚 拓展 · 超纲

cpp

// DFS实现拓扑排序：逆后序序列即为拓扑序
int topoOrder[MAXN];
int topoIdx;

void dfsTopo(int u) {
    visited[u] = true;
    for (int i = head[u]; i != -1; i = nxt[i]) {
        int v = to[i];
        if (!visited[v]) {
            dfsTopo(v);
        }
    }
    topoOrder[--topoIdx] = u;  // 逆后序：函数返回前记录
}

void topologicalSort(int n) {
    memset(visited, false, sizeof(visited));
    topoIdx = n;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfsTopo(i);
        }
    }
    // topoOrder[0] ~ topoOrder[n-1] 即为拓扑序
}

五、🌊 BFS 广度优先搜索

5.1 核心思想

"一圈一圈往外扩" —— 先访问起点，再访问所有相邻顶点，然后访问下一层，层层推进。

5.2 队列实现模板

cpp

#include <queue>

void bfs(int start, int n) {
    memset(visited, false, sizeof(visited));
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";

        for (int i = head[u]; i != -1; i = nxt[i]) {
            int v = to[i];
            if (!visited[v]) {
                visited[v] = true;  // 入队即标记
                q.push(v);
            }
        }
    }
}

// BFS遍历整个图（处理非连通图）
void bfsAll(int n) {
    memset(visited, false, sizeof(visited));
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            bfs(i, n);
        }
    }
}

5.3 BFS 应用：无权图最短路径

cpp

int dist[MAXN];

// 求start到各点的最短路径（边权均为1）
void bfsShortestPath(int start, int n) {
    memset(visited, false, sizeof(visited));
    memset(dist, -1, sizeof(dist));

    queue<int> q;
    q.push(start);
    visited[start] = true;
    dist[start] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = nxt[i]) {
            int v = to[i];
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;  // 距离 = 上一层 + 1
                q.push(v);
            }
        }
    }
    // dist[v]即为start到v的最短边数，-1表示不可达
}

5.4 BFS 应用：层序遍历

cpp

// 按层输出BFS结果
void bfsByLevel(int start, int n) {
    memset(visited, false, sizeof(visited));
    queue<int> q;
    q.push(start);
    visited[start] = true;
    int level = 0;

    while (!q.empty()) {
        int size = q.size();  // 当前层的节点数
        cout << "第" << level << "层: ";
        for (int i = 0; i < size; i++) {
            int u = q.front();
            q.pop();
            cout << u << " ";
            for (int j = head[u]; j != -1; j = nxt[j]) {
                int v = to[j];
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
        cout << endl;
        level++;
    }
}

六、⚔️ DFS vs BFS 全面对比

对比项	DFS（深度优先）	BFS（广度优先）
数据结构	栈（递归调用栈或显式栈）	队列
遍历策略	一条路走到底再回溯	一层一层向外扩展
时间复杂度	O(n + m)	O(n + m)
空间复杂度	O(n)（递归深度）	O(n)（队列最大宽度）
最短路径	❌ 不保证	✅ 无权图可求最短路径
连通性判断	✅	✅
环检测	✅（更直观）	✅（但稍复杂）
拓扑排序	✅（逆后序）	✅（Kahn算法，入度法）
层序信息	❌ 不直观	✅ 天然分层
适合深搜	迷宫求解、路径枚举	—
适合广搜	—	最少步数、最近距离

💡 选择口诀：
要找所有路径或深层数据 → 用 DFS
要找最短/最少步数 → 用 BFS
两者时间复杂度相同，区别在于遍历顺序和适用场景

七、🛡️ visited 数组使用技巧

visited 数组是图遍历的灵魂，用好它能避免无数 bug：

7.1 基本原则

原则	说明
何时标记	BFS：入队时标记；DFS递归：进入函数时标记；DFS非递归：入栈时标记
为何不能延后	延后标记会导致同一顶点被多次加入队列/栈，影响正确性和效率
非连通图	必须外层循环遍历所有顶点，对未访问的起点分别启动 DFS/BFS

7.2 进阶用法

cpp

// 用不同状态值替代bool，支持更复杂的逻辑
// 0=未访问, 1=正在访问(在当前DFS路径上), 2=已完成访问
int state[MAXN];

// 有向图环检测（三色标记法）
bool hasCycleDirected(int u) {
    state[u] = 1;  // 正在访问
    for (int i = head[u]; i != -1; i = nxt[i]) {
        int v = to[i];
        if (state[v] == 0) {
            if (hasCycleDirected(v)) return true;
        } else if (state[v] == 1) {
            return true;  // 遇到正在访问的节点，说明有环
        }
    }
    state[u] = 2;  // 完成访问
    return false;
}

⚠️ 高频考点：有向图环检测用三色标记法（0/1/2），无向图环检测用parent参数。两者不能混用！

八、📝 考试常见考法总结

选择题高频考点

考点	典型题目	答题技巧
完全图边数	n个顶点的无向完全图有几条边？	n(n-1)/2
度数与边数关系	无向图所有顶点度数之和为20，有几条边？	20/2=10
邻接矩阵性质	无向图的邻接矩阵有什么特点？	对称矩阵
DFS/BFS遍历序列	给定图和起点，输出遍历顺序	画图模拟，注意邻接点顺序
时间复杂度	邻接表存储下DFS的时间复杂度？	O(n+m)
存储方式选择	10000个顶点、5000条边的图用什么存储？	邻接表（稀疏图）

判断题高频陷阱

陷阱	正误	解析
连通分量是极小连通子图	❌	是极大连通子图
BFS能找到无权图最短路径	✅	这是BFS的核心优势
邻接矩阵适合存储稀疏图	❌	适合稠密图，稀疏图用邻接表
有向图的入度之和等于出度之和	✅	都等于边数
DFS非递归实现中，出栈时才标记visited	❌	入栈时就要标记

九、📝 实战练习

练习题 1（单选题）

题目： 一个有6个顶点的无向连通图，至少需要____条边，至多可以有____条边。

A. 5, 15 B. 6, 15
C. 5, 30
D. 6, 30

🔑 点击查看答案与解析

答案： A

至少：n个顶点的连通图至少需要 n-1 条边（构成一棵生成树），6-1=5条。
至多：无向完全图有 n(n-1)/2 = 6×5/2 = 15 条边。

练习题 2（单选题）

题目： 对如下有向图进行DFS遍历（从顶点1出发，邻接点按编号从小到大访问），遍历序列为：
边集：1→2, 1→3, 2→4, 3→4, 4→1
A. 1 2 4 3 B. 1 3 4 2 C. 1 2 3 4 D. 1 3 2 4

🔑 点击查看答案与解析

答案： A

从顶点1出发，标记1已访问。1的邻接点为{2,3}，按编号从小到大，先访问2。
到达顶点2，标记2已访问。2的邻接点为{4}，访问4。
到达顶点4，标记4已访问。4的邻接点为{1}，但1已访问，回溯。
回溯到2，2无其他未访问邻接点，回溯到1。
回溯到顶点1后，发现顶点3尚未访问，因此访问顶点3。
到达顶点3，标记3已访问。3的邻接点为{4}，4已访问，回溯。
遍历结束。序列为：1 2 4 3。

练习题 3（判断题）

题目： 用邻接表存储有向图，所有顶点的邻接表中存储的边数总和等于图的边数。用邻接表存储无向图，所有顶点的邻接表中存储的边数总和等于图的边数的两倍。

🔑 点击查看答案与解析

答案： ✅ 正确

有向图：每条边只在一个顶点的邻接表中出现，总和 = 边数 m。
无向图：每条边 (u,v) 会在 u 的邻接表和 v 的邻接表中各出现一次，总和 = 2m。

这是邻接表存储的基本性质，考试中经常出现。

练习题 4（单选题）

题目： 一个有 5 个顶点的无向完全图，总共有多少条边？（）

A. 5
B. 10
C. 20
D. 25

🔑 点击查看答案与解析

答案： B

解析： 无向完全图：每两个顶点之间都有一条边。

n 个顶点的无向完全图的边数 = C(n, 2) = n × (n-1) / 2

代入 n = 5：边数 = 5 × 4 / 2 = 10

选 B。

💡 记忆公式：完全图边数 = n(n-1)/2。每个顶点和其他 n-1 个顶点相连，每条边被算了两次，所以除以 2。

---

练习题 5（单选题）

题目： 对于一个有 n 个顶点的图，邻接矩阵的空间复杂度是？（）

A. O(n)
B. O(n²)
C. O(n + m)
D. O(m)

🔑 点击查看答案与解析

答案： B

解析： 邻接矩阵用 n × n 的二维数组存储图中所有顶点之间的关系，所以空间复杂度是 O(n²)。

邻接矩阵：O(n²)，适合稠密图
邻接表：O(n+m)，适合稀疏图

选 B。

⚠️ 注意：邻接矩阵的空间只和顶点数有关，和边数无关。即使图中只有几条边，也要开 n² 的空间。

---

练习题 6（判断题）

题目： BFS（广度优先搜索）可以求任意图中的单源最短路径。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： BFS 求最短路径只适用于无权图（所有边的权值相同）。

原因：BFS 是按"层"扩散的，先访问距离为 1 的所有点，再访问距离为 2 的所有点……所以第一次到达某个点时，一定走的是最短路径。

如果图中边的权值不同（有权图），BFS 就不适用了，需要用 Dijkstra 等算法。

🔥 高频考点："BFS求最短路径"前面一定要加"无权图"这个前提！

---

练习题 7（单选题）

题目： 关于 DFS 和 BFS，下列说法正确的是？（）

A. DFS 用队列实现，BFS 用栈实现
B. DFS 适合求无权图的最短路径
C. BFS 的空间复杂度通常比 DFS 大
D. DFS 一定比 BFS 快

🔑 点击查看答案与解析

答案： C

解析：

A 错误 ❌：DFS 用栈（或递归），BFS 用队列
B 错误 ❌：BFS 适合求无权图最短路径，DFS 不擅长
C 正确 ✅：BFS 队列里可能存很多节点，DFS 递归栈的深度通常较浅（但最坏情况都是 O(n)）
D 错误 ❌：时间复杂度都是 O(n+m)，各有适用场景

选 C。

💡 记忆口诀：DFS = 栈 = 深入；BFS = 队列 = 扩散。

---

练习题 8（编程题）

题目： 给定一个无向图，求连通分量的个数（即有多少个不连通的块）。

输入：第一行两个整数 n, m（顶点数和边数），接下来 m 行每行两个整数 u, v 表示一条边
输出：连通分量的个数

样例输入：

样例输出：

🔑 点击查看答案与解析

答案： 参考代码（DFS 实现）：

cpp

#include <iostream>
#include <vector>
using namespace std;

vector<int> adj[105];  // 邻接表
bool visited[105];     // 访问标记

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

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);  // 无向图，双向加边
    }
    
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            cnt++;  // 发现一个新的连通分量
            dfs(i); // 把这个连通分量全部标记
        }
    }
    
    cout << cnt << endl;
    return 0;
}

解析：

遍历每个顶点
如果这个顶点没被访问过，说明发现了一个新的连通分量
用 DFS 或 BFS 把这个连通分量里所有顶点都标记为已访问
统计发现了多少个连通分量

样例中：1-2-3 是一个连通分量，4-5 是一个连通分量，共 2 个。

💡 这道题用 BFS 实现也完全可以，把 dfs 换成 bfs 就行。

---

十、📊 考点总结表

考点	重要程度	出题形式	易错点
图的基本概念（顶点、边、度）	⭐⭐⭐⭐	选择/判断	有向图入度出度分开算
完全图边数计算	⭐⭐⭐⭐	选择/计算	n(n-1)/2，别忘除以2
邻接矩阵存储	⭐⭐⭐⭐⭐	选择/编程	空间O(n²)，适合稠密图
邻接表存储	⭐⭐⭐⭐⭐	选择/编程	空间O(n+m)，适合稀疏图
无向图邻接表边数	⭐⭐⭐⭐⭐	选择/判断	每条边存两次，总和=2m
DFS 深度优先搜索	⭐⭐⭐⭐⭐	编程题/选择	递归+visited标记
BFS 广度优先搜索	⭐⭐⭐⭐⭐	编程题/选择	队列+dist距离数组
BFS求最短路径	⭐⭐⭐⭐⭐	选择/判断	只适用于无权图
连通分量	⭐⭐⭐⭐	编程题/选择	多次DFS/BFS计数
DFS vs BFS对比	⭐⭐⭐⭐	选择/判断	栈vs队列，适用场景
visited数组	⭐⭐⭐⭐⭐	代码填空/选择	防止重复访问

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│       图的定义及遍历 · 必背速记卡           │
├─────────────────────────────────────────────┤
│  1. 完全图边数 = n(n-1)/2（无向）           │
│  2. 无向图总度数 = 2 × 边数                 │
│  3. 邻接矩阵：O(n²)空间，适合稠密图         │
│  4. 邻接表：O(n+m)空间，适合稀疏图          │
│  5. 无向图邻接表：每条边存两次              │
│  6. DFS = 深度优先 = 栈/递归 = 一条路走到黑  │
│  7. BFS = 广度优先 = 队列 = 层序扩散        │
│  8. BFS求最短路径只适用于无权图             │
│  9. DFS和BFS都需要visited数组               │
│ 10. 连通分量：多次DFS/BFS计数               │
│ 11. 有向图：出度好算入度难算（邻接表）       │
│ 12. BFS距离数组dist[]，初始-1               │
│ 13. dist[邻居] = dist[当前] + 1             │
│ 14. DFS空间：O(深度)，BFS空间：O(n)         │
│ 15. 时间复杂度：DFS和BFS都是O(n+m)          │
└─────────────────────────────────────────────┘

第4章 图的定义及遍历 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、📖 为什么要学"图"？ ​

二、🧱 图的基本概念 ​

2.1 什么是图？ ​

2.2 有向图 vs 无向图 ​

2.3 度、入度、出度 ​

2.4 连通图与连通分量 ​

2.5 常见图论术语速查表 ​

三、💾 图的存储方式 ​

3.1 邻接矩阵 ​

3.2 邻接表（链式前向星实现） ​

3.3 邻接表（vector 实现） ​

基本原理 ​

代码实现（带权图） ​

更简洁的写法：范围 for 循环 ​

不带权图的简化版 ​

3.4 边集数组 ​

3.5 四种存储方式总结 ​

四、🔍 DFS 深度优先搜索 ​

4.1 核心思想 ​

4.2 递归实现模板 ​

4.3 非递归（栈）实现 ​

4.4 DFS 应用场景 ​

① 连通性判断 ​

② 环检测（无向图） ​

③ 拓扑排序（有向无环图） 📚 拓展 · 超纲 ​

五、🌊 BFS 广度优先搜索 ​

5.1 核心思想 ​

5.2 队列实现模板 ​

5.3 BFS 应用：无权图最短路径 ​

5.4 BFS 应用：层序遍历 ​

六、⚔️ DFS vs BFS 全面对比 ​

七、🛡️ visited 数组使用技巧 ​

7.1 基本原则 ​

7.2 进阶用法 ​

八、📝 考试常见考法总结 ​

选择题高频考点 ​

判断题高频陷阱 ​

九、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（单选题） ​

练习题 3（判断题） ​

练习题 4（单选题） ​

练习题 5（单选题） ​

练习题 6（判断题） ​

练习题 7（单选题） ​

练习题 8（编程题） ​

十、📊 考点总结表 ​

⭐ 必背速记卡 ​

第4章图的定义及遍历

🎯 本章学习目标

🗺️ 本章知识图谱

一、📖 为什么要学"图"？

二、🧱 图的基本概念

2.1 什么是图？

2.2 有向图 vs 无向图

2.3 度、入度、出度

2.4 连通图与连通分量

2.5 常见图论术语速查表

三、💾 图的存储方式

3.1 邻接矩阵

3.2 邻接表（链式前向星实现）

3.3 邻接表（vector 实现）

基本原理

代码实现（带权图）

更简洁的写法：范围 for 循环

不带权图的简化版

3.4 边集数组

3.5 四种存储方式总结

四、🔍 DFS 深度优先搜索

4.1 核心思想

4.2 递归实现模板

4.3 非递归（栈）实现

4.4 DFS 应用场景

① 连通性判断

② 环检测（无向图）

③ 拓扑排序（有向无环图） 📚 拓展 · 超纲

五、🌊 BFS 广度优先搜索

5.1 核心思想

5.2 队列实现模板

5.3 BFS 应用：无权图最短路径

5.4 BFS 应用：层序遍历

六、⚔️ DFS vs BFS 全面对比

七、🛡️ visited 数组使用技巧

7.1 基本原则

7.2 进阶用法

八、📝 考试常见考法总结

选择题高频考点

判断题高频陷阱

九、📝 实战练习

练习题 1（单选题）

练习题 2（单选题）

练习题 3（判断题）

练习题 4（单选题）

练习题 5（单选题）

练习题 6（判断题）

练习题 7（单选题）

练习题 8（编程题）

十、📊 考点总结表

⭐ 必背速记卡