第 08 讲

图:术语与存储结构

线性表是「一对一」,树是「一对多」,图是「多对多」。这一讲只抓三件事: 图的常用术语、邻接矩阵与邻接表的取舍、以及 DFS / BFS 两种遍历。

预计 90 分钟 前置:第 07 讲树与二叉树入门、二维数组 关键词:G=(V,E) · 度 · 握手定理 · 邻接矩阵 · DFS · BFS

8.1 图是什么:定义、分类与规模

8.1.1 从线性表、树到图:逻辑结构的第三次跳跃

线性表是「一对一」,树是「一对多」,图是「多对多」: 任意两个顶点之间都可能有边,允许有环,也允许不连通。 社交网络、道路网、课程先修关系,都是图。

8.1.2 图的严格定义:G = (V, E)

图由顶点集 V 和边集 E 组成,记作 G = (V, E)。 无向边记 (v,w),有向边(弧)记 <v,w>。 顶点数记 n = |V|,边数记 e = |E|。

8.1.3 有向图、无向图、多重图、自环、简单图

8.1.4 稠密图与稀疏图

边数相对于 n² 很多,叫稠密图;边数远小于 n²,叫稀疏图。 两者没有绝对的分界,工程上常按 e 与 n² 的比例粗略判断。

这个区分很重要:本讲用的邻接矩阵要开 n×n 个格子,空间是 O(n²), 所以它更适合稠密图;稀疏图如果硬用矩阵,会浪费大量空间。

8.2 图的术语体系

8.2.1 邻接点与度

有边相连的两个顶点互为邻接点。无向图中,顶点 v 的度 d(v) 是与它相连的边数;自环对度的贡献是 2。 度为 0 的点叫孤立点,度为 1 的点叫悬挂点。

8.2.2 入度与出度

有向图中,入度是以该点为弧头的弧数,出度是以该点为弧尾的弧数。 出度为 0 的点叫汇点,入度为 0 的点叫源点; 所有点的入度之和 = 出度之和 = 弧数 e。

8.2.3 握手定理

无向图:Σd(v) = 2e,所有顶点的度数之和等于边数的两倍。 有向图:入度之和 = 出度之和 = e。

两个常用推论:度数之和一定是偶数;奇度顶点的个数一定是偶数。 例如「只有 1 个奇度顶点」的图不存在。

8.2.4 连通、连通图、连通分量、强连通分量

无向图中,两点之间能沿着边走通就叫连通;任意两点都连通叫连通图; 极大的连通子图叫连通分量。 有向图中,若两点可以互相到达,叫强连通;对应的极大子图叫强连通分量。

8.2.5 子图与生成树

子图:从原图中取一部分顶点和一部分边组成的图。 连通无向图的生成树,是包含全部 n 个顶点、恰好 n−1 条边、 并且仍然连通的子图。

8.3 存储结构:邻接矩阵

8.3.1 定义:用二维数组记录「谁和谁相邻」

用 n×n 的二维数组 A 存图: 有边 (i,j) 时 A[i][j] = 1,否则为 0。 无向图的矩阵关于主对角线对称;有向图一般不对称。 带权图把 1 换成边权,没有边用一个很大的数表示。

8.3.2 从矩阵能读出什么

8.3.3 空间复杂度 O(n²)

邻接矩阵固定占 n² 个单元,与边数 e 无关。 所以稠密图用它很合适,稀疏图会浪费大量空间。

8.3.4 邻接矩阵的 C++ 实现

#include <iostream>
using namespace std;

const int N = 8;
int g[N][N];

int main() {
    int edges[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},
                       {3,4},{4,5},{5,6},{5,7}};

    for (int i = 0; i < 9; ++i) {
        int u = edges[i][0], v = edges[i][1];
        g[u][v] = g[v][u] = 1;          // 无向图:一条边写两格
    }

    cout << "0 的度 = ";
    int deg = 0;
    for (int j = 0; j < N; ++j) deg += g[0][j];
    cout << deg << "\n";               // 2

    cout << "0 和 1 相邻吗? " << (g[0][1] ? "是" : "否") << "\n";
    return 0;
}

8.4 邻接表:只存真正存在的边

邻接矩阵把不存在的边也记成 0,稀疏图会浪费很多格子。 邻接表换一个思路:给每个顶点挂一个列表,列表里只放它真正相连的邻接点。

8.5 邻接矩阵 vs 邻接表

两种存法没有绝对的好坏,关键看图是稠密还是稀疏、最常做什么操作。 设图有 n 个顶点、e 条边:

对比项邻接矩阵邻接表
空间O(n²),与边数无关O(n+e)
判断 u、v 是否相邻O(1)O(deg(u))
枚举 u 的所有邻接点O(n)O(deg(u))
求无向图某点的度第 u 行求和,O(n)链表长度,O(1) 或 O(deg(u))
适合的图稠密图稀疏图
代码难度最简单稍多一层列表

本讲的 DFS / BFS 代码统一用邻接表,因为它枚举邻接点更快; 如果图很稠密,或者经常要判断“两点是否直接相连”,用邻接矩阵更合适。

8.6 图的遍历(一):深度优先搜索 DFS

8.6.1 一句话本质:一条路走到黑,撞墙再回头

从起点出发,访问它并标记;然后依次看它的每个邻接点: 没访问过就递归进去;走不通就退回上一个点,换下一个邻接点。

8.6.2 手推过程

仍用示例图 G(8 个顶点、9 条边),从 0 出发, 约定邻接点按编号从小到大访问,得到 DFS 序列: 0 1 2 3 4 5 6 7。 每次走到新点就继续深入,走不动再回溯。

8.6.3 完整递归代码

#include <bits/stdc++.h>
using namespace std;

const int N = 8;
vector<int> g[N];
bool vis[N];

void dfs(int u) {
    vis[u] = true;
    cout << u << " ";
    for (int v : g[u]) {
        if (!vis[v]) dfs(v);
    }
}

int main() {
    int edges[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},
                       {3,4},{4,5},{5,6},{5,7}};

    for (int i = 0; i < 9; ++i) {
        int u = edges[i][0], v = edges[i][1];
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 0; i < N; ++i) sort(g[i].begin(), g[i].end());

    dfs(0);                         // 输出:0 1 2 3 4 5 6 7
    cout << "\n";
    return 0;
}

DFS 用递归(系统栈),所以会先往深处走,走不通再回溯。

8.6.4 复杂度

用邻接表存图时,每个顶点访问一次、每条边检查两次,时间复杂度是 O(n+e);空间是 O(n)(visited 数组 + 递归栈)。 如果改用邻接矩阵,复杂度会变成 O(n²)。

8.6.5 DFS 能做什么

8.7 图的遍历(二):广度优先搜索 BFS

8.7.1 一句话本质:一圈一圈向外扩散

把起点入队并标记;每次从队头取出一个点,把它所有未访问的邻接点入队并标记; 队列空为止。DFS 用栈,BFS 用队列。

8.7.2 手推过程与分层

从 0 出发,BFS 的层次是: L0 = {0}、L1 = {1,6}、 L2 = {2,7,5}、L3 = {3,4}。 每个点第一次被访问时,所在的层就是它到 0 的最短边数。

8.7.3 复杂度

邻接表下,每个顶点入队出队各一次、每条边检查常数次,时间复杂度是 O(n+e);队列、visited 数组占 O(n) 空间。 如果改用邻接矩阵,复杂度会变成 O(n²)。

8.7.4 无权图的单源最短路

BFS 第一次到达某个点时,经过的边数就是最短距离。 下面用 dist[] 记录距离、pre[] 记录前驱, 并给出从 0 到 7 的一条最短路径。

#include <bits/stdc++.h>
using namespace std;

const int N = 8;
vector<int> g[N];
int dist[N], pre[N];

int main() {
    int edges[9][2] = {{0,1},{0,6},{1,2},{1,7},{2,3},
                       {3,4},{4,5},{5,6},{5,7}};

    for (int i = 0; i < 9; ++i) {
        int u = edges[i][0], v = edges[i][1];
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 0; i < N; ++i) sort(g[i].begin(), g[i].end());

    fill(dist, dist + N, -1);
    fill(pre, pre + N, -1);
    queue<int> q;

    dist[0] = 0;
    q.push(0);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";                 // BFS 序列
        for (int v : g[u]) {
            if (dist[v] != -1) continue;  // 已经入过队
            dist[v] = dist[u] + 1;
            pre[v] = u;
            q.push(v);
        }
    }
    cout << "\n";

    /* 从 7 倒推到 0,再反转,就是一条最短路 */
    vector<int> path;
    for (int x = 7; x != -1; x = pre[x]) path.push_back(x);
    reverse(path.begin(), path.end());
    for (int x : path) cout << x << " ";
    cout << "\n";                       // 0 1 7
    return 0;
}