图：邻接矩阵与邻接表

概念

图（Graph）G 由顶点集 V（Vertex）和边集 E（Edge）组成，记作 $G = (V, E)$ 。

边没有方向 → 无向图，边记作 $(u, v)$ ；
边有方向 → 有向图，边叫弧，记作 $⟨ u, v ⟩$ ，u 为弧尾、v 为弧头；
边带权值 → 网（Network）。

| V | = n 表示顶点数，| E | = e 表示边数。

一句话理解：线性表是"一对一"、树是"一对多"、图是"多对多"——图是前两种结构的推广，也是唯一没有"天然层次"的结构，所以必须额外考虑"从哪儿开始遍历"。

原理

术语速查

术语	定义
度 TD(v)	无向图中与 v 相连的边数
入度 ID(v) / 出度 OD(v)	有向图中指向 v / 从 v 出发的弧数，TD(v) = ID(v) + OD(v)
完全图（无向）	任意两点之间都有一条边，边数 $\frac{n (n - 1)}{2}$
完全图（有向）	任意两点之间都有两条反向弧，弧数 $n (n - 1)$
路径 / 简单路径	顶点序列 / 顶点不重复的路径
回路（环）	起点与终点相同的路径
连通 / 连通图（无向）	两点间有路径 / 任意两点都连通
连通分量	无向图的极大连通子图
强连通 / 强连通分量（有向）	两点互相可达 / 极大强连通子图
生成树	连通图的极小连通子图，含全部 n 个顶点、n − 1 条边
稀疏图 / 稠密图	大致以 $e < n \log_{2} n$ 为界

三条恒等式（选择/填空常客）

无向图： $\sum_{v \in V} T D (v) = 2 e$ ——每条边被它的两个端点各数一次。
有向图： $\sum I D (v) = \sum O D (v) = e$ ——每条弧贡献一个出度和一个入度。
连通图的生成树恰有 n − 1 条边；再加一条边必成回路，减一条边必不连通。

存储一：邻接矩阵

用 n × n 的二维数组 A：

A [i] [j] = {\begin{cases} 1 或 w_{i j}, & 存在边 (v_{i}, v_{j}) 或弧 ⟨ v_{i}, v_{j} ⟩ \\ 0 或 \infty, & 不存在 \end{cases}

项	结论
空间	$Θ (n^{2})$ ，与边数无关
无向图	矩阵关于主对角线对称，可只存上/下三角压缩
无向图求度	第 i 行（或列）非零元素个数 = TD(v_i)
有向图求度	第 i 行之和 = OD(v_i)，第 i 列之和 = ID(v_i)
判边存在	O(1)
适合	稠密图；需要频繁判边的算法（如 Floyd）

缺点：稀疏图下大量空间被 0/∞ 浪费；遍历时对每个点都要扫整行，时间 O(n²)。

存储二：邻接表

对每个顶点建一条单链表，链上挂它的所有邻接顶点：

顶点表                边链表
[1] -> 2 -> 3
[2] -> 1 -> 4 -> 5
[3] -> 1 -> 5
[4] -> 2 -> 6
[5] -> 2 -> 3 -> 6
[6] -> 4 -> 5

项	结论
空间	无向图 $O (n + 2 e)$ （每条边存两次）；有向图 $O (n + e)$
无向图求度	第 i 条链表的结点数 = TD(v_i)
有向图求度	出度 = 链表长度；入度须遍历全表（或另建逆邻接表）
判边存在	最坏 O(TD(v))，需扫链表
适合	稀疏图；需要枚举所有邻接点的算法（BFS/DFS/Dijkstra）

注意：同一个图的邻接表不唯一（链表插入顺序不同，表就不同），但邻接矩阵唯一。这与树的孩子表示法同理。

存储三、四（了解）

结构	针对	特点
十字链表（Orthogonal List）	有向图	把邻接表与逆邻接表合二为一，一条弧结点同时挂在"出弧链"和"入弧链"上，入度出度都好求
邻接多重表	无向图	一条边只用一个边结点表示（不像邻接表存两次），便于删除边与标记访问过的边

408 对这两种只要求"知道存在、知道针对谁"，不要求手写代码。

两种主结构的对比

	邻接矩阵	邻接表
空间	$O (n^{2})$	$O (n + e)$
判边 (u,v)	$O (1)$	$O (T D (u))$
枚举 u 的所有邻接点	$O (n)$	$O (T D (u))$
遍历全图	$O (n^{2})$	$O (n + e)$
求入度	扫第 v 列， $O (n)$	需扫全表 $O (n + e)$ 或建逆邻接表
唯一性	唯一	不唯一
适用	稠密图	稀疏图

示例

例：同一个图，两种表示

无向图 G 有 6 个顶点，边集为： (1,2), (1,3), (2,4), (2,5), (3,5), (4,6), (5,6) 画出它，写出邻接矩阵与邻接表，求各顶点度数并验证恒等式，判断它是否稀疏。

图：

     1 ──────── 2 ──────── 4
     │          │  ╲       │
     │          │    ╲     │
     │          │      ╲   │
     3 ──────── 5 ──────── 6

七条边：(1,2) 顶横、(1,3) 左竖、(2,4) 右上横、(2,5) 斜线、(3,5) 底左横、(4,6) 右竖、(5,6) 底右横。

邻接矩阵（6 × 6，对称）：

	1	2	3	4	5	6	行和 = 度
1	0	1	1	0	0	0	2
2	1	0	0	1	1	0	3
3	1	0	0	0	1	0	2
4	0	1	0	0	0	1	2
5	0	1	1	0	0	1	3
6	0	0	0	1	1	0	2

邻接表（顶点编号升序链接）：

[1] -> 2 -> 3 ^
[2] -> 1 -> 4 -> 5 ^
[3] -> 1 -> 5 ^
[4] -> 2 -> 6 ^
[5] -> 2 -> 3 -> 6 ^
[6] -> 4 -> 5 ^

验证恒等式：

\sum T D = 2 + 3 + 2 + 2 + 3 + 2 = 14 = 2 e \Rightarrow e = 7 ✓

与题面给出的 7 条边一致。边链表结点总数 = 2e = 14（每条无向边在两个顶点的链表里各占一个结点），数一数上面确实是 14 个。

是否稀疏：n = 6 时完全图有 $\frac{6 \times 5}{2} = 15$ 条边，本图只有 7 条； $n \log_{2} n = 6 \times 2.585 \approx 15.5 > 7$ ，故属于稀疏图，用邻接表更省空间。

生成树：本图连通，任一生成树恰有 $n - 1 = 5$ 条边。例如保留 (1,2), (1,3), (2,4), (2,5), (5,6) 即得一棵生成树。

C 语言：邻接表建图与遍历度

#include <stdio.h>
#include <stdlib.h>

#define MAXV 10

typedef struct ArcNode {          /* 边（弧）结点 */
    int adjvex;                   /* 邻接点下标 */
    struct ArcNode *next;
} ArcNode;

typedef struct {                  /* 顶点表结点 */
    int data;
    ArcNode *first;
} VNode, AdjList[MAXV];

typedef struct {
    AdjList v;
    int n, e;
} ALGraph;

/* 无向图加边：要挂两次；头插法，故链表顺序与输入顺序相反 */
void addEdge(ALGraph *g, int u, int v) {
    ArcNode *a = (ArcNode *)malloc(sizeof(ArcNode));
    a->adjvex = v; a->next = g->v[u].first; g->v[u].first = a;
    ArcNode *b = (ArcNode *)malloc(sizeof(ArcNode));
    b->adjvex = u; b->next = g->v[v].first; g->v[v].first = b;
    g->e++;
}

/* 无向图求度：数链表长度 */
int degree(ALGraph *g, int u) {
    int d = 0;
    for (ArcNode *p = g->v[u].first; p; p = p->next) d++;
    return d;
}

int main(void) {
    ALGraph g;
    g.n = 6; g.e = 0;
    for (int i = 0; i < g.n; i++) { g.v[i].data = i + 1; g.v[i].first = NULL; }

    /* 顶点在数组中从 0 号下标存起，故边 (1,2) 写作 (0,1)；
       因采用头插法，按邻接点降序输入可使链表呈升序，与上文表格一致 */
    int E[][2] = {{4,5},{2,4},{3,5},{1,4},{0,2},{1,3},{0,1}};
    for (int i = 0; i < 7; i++) addEdge(&g, E[i][0], E[i][1]);

    int sum = 0, nodes = 0;
    for (int i = 0; i < g.n; i++) {
        printf("顶点 %d:", g.v[i].data);
        for (ArcNode *p = g.v[i].first; p; p = p->next) {
            printf(" -> %d", g.v[p->adjvex].data);
            nodes++;
        }
        int d = degree(&g, i);
        sum += d;
        printf("   度 = %d\n", d);
    }
    printf("度之和 = %d, 2e = %d, 边链表结点数 = %d\n", sum, 2 * g.e, nodes);
    /* 度之和 = 14, 2e = 14, 边链表结点数 = 14 */
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

Python 对照

# 邻接表：{顶点: [邻接点, ...]}
g = {1: [2, 3], 2: [1, 4, 5], 3: [1, 5],
     4: [2, 6], 5: [2, 3, 6], 6: [4, 5]}
n = len(g)
deg = {u: len(g[u]) for u in g}
e = sum(deg.values()) // 2
print("度:", deg, " 度之和:", sum(deg.values()), " e:", e)   # 14 7
print("边链表结点数 = 2e =", 2 * e)                          # 14

# 邻接矩阵
M = [[1 if j in g[i] else 0 for j in range(1, n + 1)] for i in range(1, n + 1)]
for row in M: print(row)
print("对称?", all(M[i][j] == M[j][i] for i in range(n) for j in range(n)))  # True

# 判边：邻接矩阵 O(1)，邻接表需扫链表
def has_edge_matrix(i, j): return M[i - 1][j - 1] == 1
def has_edge_list(i, j):   return j in g[i]
print(has_edge_matrix(1, 4), has_edge_list(1, 4))   # False False
print(has_edge_matrix(2, 5), has_edge_list(2, 5))   # True  True

# 求生成树（DFS 树）：连通图恰取 n-1 条边
seen, tree = {1}, []
def dfs(u):
    for v in g[u]:
        if v not in seen:
            seen.add(v); tree.append((u, v)); dfs(v)
dfs(1)
print("DFS 生成树边:", tree, " 边数:", len(tree))   # 5 = n-1

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

1. 必背结论

无向完全图边数 $\frac{n (n - 1)}{2}$ ；有向完全图弧数 $n (n - 1)$ 。
$\sum T D = 2 e$ （无向）； $\sum I D = \sum O D = e$ （有向）。
连通图的生成树含 n − 1 条边；n 个顶点的图若边数 < n − 1 必不连通。
邻接矩阵空间 $Θ (n^{2})$ ，无向图矩阵对称；邻接表无向图 $O (n + 2 e)$ 、有向图 $O (n + e)$ 。
邻接表不唯一（取决于插入顺序），邻接矩阵唯一。
有向图用邻接表求入度需遍历全表，这是选择题最爱设的陷阱。

2. 解题套路

看到"求度数之和"立刻想到 $2 e$ （无向）或 $e$ （有向），不用逐个点去数。
判断用哪种存储：给 n 与 e，比较 $n^{2}$ 与 $n + e$ ；稠密用矩阵、稀疏用表。
判断"用邻接矩阵时某算法的时间复杂度"：遍历全图是 O(n²)；"用邻接表"则是 O(n+e)。

3. 易错点

邻接表存无向图时，一条边要挂两个边结点。数边链表结点数时算成 e 而不是 2e，是最常见的算错。
邻接矩阵中主对角线：无自环的简单图，A[i][i] = 0；带权图常写作 0，但 Floyd 等算法里要注意与"权值为 0"的语义区分。
无向图的邻接矩阵"对称"A[i][j] = A[j][i]；有向图不对称，别默认。
连通（无向）与强连通（有向）不可混用：有向图"任意两点有路径"仍不等于强连通，必须互相可达。
极大连通子图 = 连通分量；极小连通子图 = 生成树。"极大""极小"指的是"再加入/删除就破坏性质"，不是边数最多/最少。
顶点数与边数的关系： $n - 1 \leq e \leq \frac{n (n - 1)}{2}$ （连通无向图），别把生成树的 n−1 当成图的边数。

小结

图是"多对多"结构，术语围绕度、连通性、生成树展开，三条恒等式是填空送分点。
邻接矩阵 O(n²) 适合稠密图、判边 O(1)；邻接表 O(n+e) 适合稀疏图、枚举邻接点快；有向图求入度是邻接表的短板。
同一个图的邻接表不唯一，但邻接矩阵唯一。
下一步：有了存储结构，就可以在图上跑深度优先与广度优先遍历。

下一篇：图的遍历：DFS 与 BFS

图：邻接矩阵与邻接表

概念

原理

术语速查

三条恒等式（选择/填空常客）

存储一：邻接矩阵

存储二：邻接表

存储三、四（了解）

两种主结构的对比

示例

例：同一个图，两种表示

C 语言：邻接表建图与遍历度

Python 对照

考点

小结

我的笔记

评论（0）

图：邻接矩阵与邻接表 ​

概念 ​

原理 ​

术语速查 ​

三条恒等式（选择/填空常客） ​

存储一：邻接矩阵 ​

存储二：邻接表 ​

存储三、四（了解） ​

两种主结构的对比 ​

示例 ​

例：同一个图，两种表示 ​

C 语言：邻接表建图与遍历度 ​

Python 对照 ​

考点 ​

小结 ​

我的笔记

评论（0）

图：邻接矩阵与邻接表

概念

原理

术语速查

三条恒等式（选择/填空常客）

存储一：邻接矩阵

存储二：邻接表

存储三、四（了解）

两种主结构的对比

示例

例：同一个图，两种表示

C 语言：邻接表建图与遍历度

Python 对照

考点

小结