邻接矩阵

2026 大纲 五（二）图的存储及基本操作 1. 邻接矩阵（另两种见《邻接表》《十字链表与邻接多重表》）。

用一张方阵把"谁挨着谁"全记下来

《图的基本概念》里说过一句话：图没有顺序存储——不能靠元素在数组里的位置来表示边。既然位置不能承担这个任务，那就把边显式记下来。最直白的记法是：开一张 $n\times n$ 的方阵，第 $i$ 行第 $j$ 列那一格记"$v_i$ 到 $v_j$ 有没有边"。这就是邻接矩阵。

它简单到几乎不用解释，但有两处一开始就得说清楚，否则后面全是坑。

第一，它是两个数组，不是一个。 矩阵只记关系，不记顶点自身是谁。$A[0][1]=1$ 只告诉你"0 号和 1 号相邻"，可 0 号顶点叫什么名字、存了什么数据，矩阵里一个字都没有。所以必须另开一维顶点表 vex[n]，下标与矩阵的行列一一对应。真题的代码大题里，MGraph 的定义总是 VerticesList[] 加 Edge[][] 两截，就是这个原因——而且题目常常要求"输出顶点名而不是下标"，用的正是顶点表。

第二，同一个 0，在无权图和带权图里含义相反。 无权图的格子里记的是"有没有边"，$0$ 就是没有；带权图（网）的格子里记的是"代价"，$0$ 意味着免费直达。所以带权图绝不能用 0 表示无边，无边要填 $\mathrm{\infty }$（程序里取一个比所有可能路径长度和都大的有限常数，教材记作 MaxInt），而对角线要填 $0$。这不是洁癖：Floyd 的三重循环直接依赖"对角线为 0"，填成 $\mathrm{\infty }$ 第一轮松弛就全废。

先动手看一眼

加载可视化中...

建议这样拨：先建一张无向图，观察矩阵是不是沿主对角线对称；再把同一组顶点切成有向图，看对称性怎么塌掉。然后随便点一个顶点，分别沿它的行和列扫一遍，确认"行数出度、列数入度"。

读矩阵：度、边数与对称性

读一张矩阵，第一件事是看它对不对称。

无向图的边 $(v_i,v_j)$ 和 $(v_j,v_i)$ 是同一条，所以 $A[i][j]=A[j][i]$ 恒成立，矩阵必对称。这带来一个直接的省空间机会：只存上（或下）三角，${\displaystyle \frac{n(n-1)}{2}}$ 个元素（含对角线则 ${\displaystyle \frac{n(n+1)}{2}}$），下标换算方式与特殊矩阵的压缩存储完全一样。有向图的矩阵一般不对称，不能这么压。

看清对称性之后，度就能直接数出来：

• 无向图：顶点 $v_i$ 的度 = 第 $i$ 行的非零元个数（等于第 $i$ 列的，反正对称）。
• 有向图：第 $i$ 行的非零元个数 = 出度（以 $i$ 为弧尾），第 $i$ 列的非零元个数 = 入度（以 $i$ 为弧头），两者相加才是度。

🔴 只数一个方向就中招。有向图里问"某顶点的度"，答案是行和加列和；只数行得到的是出度，只数列得到的是入度。真题里给一张 $4\times 4$ 的矩阵问"各顶点的度依次是"，四个选项里就并排放着"只数列的结果"和"行列相加的结果"。

数边数同理：数非对角线上的非零（非 $\mathrm{\infty }$）元素，无向图要除以 2（每条边被记了两遍），有向图不用。

有一条自检可以顺手用：有向图的出度之和、入度之和、弧数三者必然相等。算完出入度先对一下这三个数，对不上说明数错了行或列。

一条被反复用到的结构判据：严格上三角 ⟺ DAG

有向图的矩阵不对称，那么"矩阵长成某种特定形状"能说明什么？有一条判据在真题里被直接考过：

🔴 一个有向图是 DAG（有向无环图）当且仅当存在一种顶点编号方式，使它的邻接矩阵成为严格上三角矩阵。

推理两句话就够。若矩阵严格上三角，则所有弧都从小编号指向大编号，沿任何一条路径走，顶点编号严格递增，永远回不到起点，故无环。反过来若无环，拓扑排序必然成功，把拓扑序列里的位置当作新编号，所有弧就都朝着编号增大的方向了。

⚠️ 但这里有个必须分清的地方：判据说的是"存在一种编号使它上三角"，不是"给定编号下它一定上三角"。所以反过来读要小心——题面直接给你一张主对角线以下全为 0 的矩阵，你能断定图无环、拓扑序列存在；但推不出拓扑序列唯一。唯一性要看每一步入度为 0 的顶点是不是只有一个，与矩阵形状无关。真题在这里设过一个四选一：存在且唯一 / 存在且不唯一 / 存在，可能不唯一 / 无法确定，正确的是第三个。

矩阵幂：$A^k[i][j]$ 是路径条数

邻接矩阵和邻接表最不一样的地方，是它能做代数运算。而这件事在真题里不是花絮，是一整道大题。

🔴 $A^k[i][j]$ = 从 $v_i$ 到 $v_j$、长度恰好为 $k$ 的路径条数（允许路径中重复经过顶点）。

推导（对 $k$ 归纳）。$k=1$ 时 $A^1=A$，$A[i][j]$ 就是长度为 1 的路径（也就是边）的条数，成立。设 $A^{k-1}[i][t]$ 已经是 $i\to t$ 长度 $k-1$ 的路径条数，那么按矩阵乘法：

$$A^k[i][j]=\sum _{t=0}^{n-1}{A}^{k-1}[i][t]\cdot A[t][j]$$

右边在数什么？把所有长度为 $k$ 的 $i\to j$ 路径，按倒数第二个顶点是谁分类。若倒数第二个顶点是 $t$，这一类的条数 =（$i$ 到 $t$ 长度 $k-1$ 的路径条数）×（$t$ 到 $j$ 有没有边）。对所有可能的 $t$ 求和，不重不漏——这恰好就是矩阵乘法的定义式。∎

算一个例子：四元环 $0-1,1-2,2-3,3-0$。

$$A=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right)A^2=\left(\begin{array}{cccc}2& 0& 2& 0\\ 0& 2& 0& 2\\ 2& 0& 2& 0\\ 0& 2& 0& 2\end{array}\right)A^3=\left(\begin{array}{cccc}0& 4& 0& 4\\ 4& 0& 4& 0\\ 0& 4& 0& 4\\ 4& 0& 4& 0\end{array}\right)$$

逐格核对：$A^2[0][0]=2$——从 0 走两步回到 0，走法是 $0\to 1\to 0$ 和 $0\to 3\to 0$，确实 2 条。$A^2[0][2]=2$——$0\to 1\to 2$ 与 $0\to 3\to 2$。$A^2[0][1]=0$——四元环是二部图，不存在长度为偶数的 $0\to 1$ 路径，这与图的基本概念里"二部图无奇回路"的染色论证是同一件事。

答这类题有两个措辞要拿准，真题的评分点就卡在这儿：

1. "长度恰好为 $k$"，不是"至多 $k$"。 $A^2$ 数的是两步路径，一步就能到的边不算在里面。
2. 它数的是路径条数，不是最短路。 $A^k$ 全程只做加法和乘法，没有任何取最小的动作。Floyd 的三重循环形状与矩阵乘法一模一样，但它把加法换成了 $min$、乘法换成了加法——结构同源，语义完全不同，别把两者的结论串了。

由此还能读出一条推论：$n$ 个顶点的图，若 $B^m$（$2\le m\le n$）中某个位置非零，就说明存在一条该长度的路径，也即两点可达。

存储结构与建图

#define MaxVertexNum 100
#define INFINITY 65535         // 无穷大：须大于所有可能的路径长度和

typedef struct {
    char vex[MaxVertexNum];                     // 顶点表：下标 i ↔ 顶点 i
    int  edge[MaxVertexNum][MaxVertexNum];      // 无权图存 0/1；带权图存权值
    int  vexNum, edgeNum;
} MGraph;

void addEdge(MGraph *G, int u, int v) {         // 添加无向边
    G->edge[u][v] = 1;
    G->edge[v][u] = 1;   // 🔴 必须对称赋值：漏掉这行，从 v 出发就找不到 u
    G->edgeNum++;        // 一条无向边只加一次，不是两次
}

// 🔴 带权图的初始化与无权图不同，是全篇最容易写错的一处
void initWGraph(MGraph *G, int n) {
    G->vexNum = n; G->edgeNum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            G->edge[i][j] = (i == j) ? 0 : INFINITY;
}

// 有向图一次扫描同时求出度与入度：两者下标互换，可在同一循环里取
void directedDegree(MGraph *G, int i, int *outD, int *inD) {
    *outD = *inD = 0;
    for (int j = 0; j < G->vexNum; j++) {
        if (G->edge[i][j] != 0) (*outD)++;  // 第 i 行 → 以 i 为弧尾 → 出度
        if (G->edge[j][i] != 0) (*inD)++;   // 第 i 列 → 以 i 为弧头 → 入度
    }
}

上面这个 directedDegree 值得单独说一句：求入度，邻接矩阵只要 $O(n)$（扫一列），而邻接表必须遍历整张表、要 $O(n+e)$。这是邻接矩阵相对邻接表的实质优势，也是真题在两种存储上分别问过同一个操作的原因。

如果要一次求出所有顶点的出入度，不必对每个顶点各扫一遍，一次双重循环就够——每看到一个非零的 Edge[i][j]，就同时给 $i$ 的出度加一、给 $j$ 的入度加一：

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (G.Edge[i][j] != 0) { outDeg[i]++; inDeg[j]++; }

这四行是图论代码大题的通用开头，后面接什么判断，就变成哪一道题。

邻接矩阵 vs 邻接表

对比维度	邻接矩阵	邻接表	判别依据
空间	$O(n^2)$，与 $e$ 无关	$O(n+e)$	$e$ 接近 $n^2$ 选矩阵
判两点是否相邻	$O(1)$	$O(\mathrm{deg}(v))$，最坏 $O(n)$	是否频繁随机判边
求某顶点全部邻接点	$O(n)$（必扫整行）	$O(\mathrm{deg}(v))$	度是否远小于 $n$
求有向图的入度	$O(n)$（扫一列）	$O(n+e)$（遍历全表）	这是十字链表的存在理由
增删顶点	$O(n^2)$（挪行挪列）	$O(1)$ 增	矩阵行列是固定编号
遍历全图（DFS/BFS）	$O(n^2)$	$O(n+e)$	见 DFS 与 BFS
表示是否唯一	唯一	不唯一	链上结点次序取决于建表次序

判边一个 $O(1)$、一个 $O(n)$，差别的根在于这条信息是被直接寻址还是被搜索：矩阵把 $(i,j)$ 这对下标直接映射成内存地址，是查表；邻接表把顶点 $i$ 的邻居串成一条链，要判 $j$ 在不在就得走一遍。

最后一行"表示是否唯一"看着不起眼，但影响很远：矩阵的表示唯一，所以在矩阵上跑 DFS/BFS 得到的遍历序列也唯一；邻接表的链上结点次序取决于建表次序，遍历序列就不唯一。 判"下列哪个不是该图的 DFS 序列"这类题，默认前提正是"邻接表次序未定，所以有多个合法序列"。

至于空间，$O(n^2)$ 与边数完全无关：1000 个顶点、2000 条边的图要 ${10}^6$ 个格子，其中 $99.6\mathrm{\%}$ 是 0。所以稀疏图用邻接矩阵不但不省空间，还是最费的那个——真题把"存储稀疏图，用邻接矩阵比邻接表更省空间"当作错误命题放进过三选项判断题。

两个最小示例，以及非连通图的矩阵长什么样（第一次学时展开）

无向图（四元环）：

图:  0 — 1        邻接矩阵:
     |   |          0  1  2  3
     3 — 2        0 [0, 1, 0, 1]
                  1 [1, 0, 1, 0]
                  2 [0, 1, 0, 1]
                  3 [1, 0, 1, 0]

有向图 $⟨0,1⟩,⟨0,2⟩,⟨2,1⟩$——$A[i][j]=1$ 只说明有一条 $i\to j$ 的弧，$A[j][i]$ 是不是 1 与它无关：

邻接矩阵:
     0  1  2
  0 [0, 1, 1]
  1 [0, 0, 0]
  2 [0, 1, 0]

图注：左、中、右三例分别是无向图、含双向弧的有向图、以及一个由两个互不相连的部分组成的 有向图。看右边那张矩阵——它被虚线切成了对角上的两块，块外全是 0。 一个图有几个互不相通的部分，就能把邻接矩阵重排成几块对角块，块外恒为 0。 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.5 图的邻接矩阵表示，p351

从一张矩阵把图的信息全读出来——五顶点带权有向图走查（想练手读表就展开）

	$v_0$	$v_1$	$v_2$	$v_3$	$v_4$
$v_0$	0	3	∞	7	∞
$v_1$	∞	0	2	∞	∞
$v_2$	∞	∞	0	4	1
$v_3$	∞	∞	∞	0	5
$v_4$	∞	∞	∞	∞	0

弧数：数非对角线的非 $\mathrm{\infty }$ 元素，第 0 行 2 个、第 1 行 1 个、第 2 行 2 个、第 3 行 1 个、第 4 行 0 个，共 6 条弧（有向图不除以 2）。

出度、入度：

顶点	出度（数第 $i$ 行）	入度（数第 $i$ 列）	度
$v_0$	2（到 $v_1,v_3$）	0	2
$v_1$	1（到 $v_2$）	1（来自 $v_0$）	2
$v_2$	2（到 $v_3,v_4$）	1（来自 $v_1$）	3
$v_3$	1（到 $v_4$）	2（来自 $v_0,v_2$）	3
$v_4$	0	2（来自 $v_2,v_3$）	2

自检：出度之和 $=6$、入度之和 $=6$，两者相等且等于弧数 ✓。

它是严格上三角的（所有非 $\mathrm{\infty }$ 的非对角元都在对角线右上方），所以一定是 DAG。

$v_0$ 到 $v_4$ 的全部路径：$v_0\to v_3\to v_4$ 长 $7+5=12$；$v_0\to v_1\to v_2\to v_4$ 长 $3+2+1=6$；$v_0\to v_1\to v_2\to v_3\to v_4$ 长 $3+2+4+5=14$。共 3 条，最短的是 6（一般解法见 Dijkstra）。

考点速记

三条结论，正文里都推过，忘了可以现推：

1. 有向图：行数出度、列数入度，度 = 两者之和。 自检用"出度和 = 入度和 = 弧数"。
2. 无向图矩阵必对称，可压到 ${\displaystyle \frac{n(n-1)}{2}}$；有向图不能压。
3. $A^k[i][j]$ = 长度恰好为 $k$ 的路径条数，数的是条数不是最短路。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 给矩阵问度：一张 $4\times 4$ 的 0/1 矩阵，问"各顶点的度依次是"。选项里同时摆着"只数列"和"行列相加"两种结果。
• 矩阵幂的含义（一整道大题）：写出图的邻接矩阵 $A$，求 $A^2$，问 $A^2$ 中某个位置的元素是什么含义；再推广问 $B^m$（$2\le m\le n$）中非零元素的含义。答的是"长度为 $m$ 的路径条数"，措辞里"长度恰好"和"条数"两个词都要写出来。
• 上三角压缩存储的还原（大题起手）：把严格上三角部分按行优先压成一维数组给你，要求还原邻接矩阵、画出带权有向图，再在这张图上求关键路径。存储压缩和图算法在这里被串成一道题。
• 由矩阵形状判拓扑序：主对角线以下全为零，问拓扑序列的结论——存在（无环），但可能不唯一。
• 代码大题的默认载体：图论的算法设计题给出的类型定义几乎都是 MGraph（VerticesList[] 顶点表 + Edge[][] 邻接矩阵 + numVertices/numEdges）。已考过的三道分别是：判断是否存在含全部边的 EL 路径（数各顶点的度，看奇度顶点个数）、找出所有出度大于入度的顶点（一次双重扫描同时统计出入度）、判断拓扑序列是否唯一。三道题的第一步都是"统计度"，写熟上面那四行双重循环，起手就稳了。
• 存储选型的判断：把"稀疏图用邻接矩阵更省空间"作为错误命题混在三选项判断里。

易错：有向图的"度"是入度加出度。 只数第 $i$ 行得到的是出度，只数第 $i$ 列得到的是入度。题目问"度"而你只数了一个方向，选项里一定有那个错误答案在等你。

易错：带权图无边填 $\mathrm{\infty }$、对角线填 0，不能用 0 表示无边。 无权图里 0 = 没有边，带权图里 0 = 代价为零，含义正相反。

易错：$A^k$ 数的是路径条数，不是最短路径长度。 矩阵幂全程只有加法和乘法，没有取 $min$ 的动作；Floyd 才是把加法换成 $min$ 的那个，两者三重循环形状一样但结论不能互换。

易错："矩阵是上三角"推得出无环，推不出拓扑序唯一。 唯一性只取决于"每一步入度为 0 的顶点是否只有一个"，跟矩阵形状没关系。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p153，§6.4 引言： "图没有顺序存储结构，但可以借助二维数组来表示元素之间的关系，即邻接矩阵表示法"； 同页 §6.4.1 给出邻接矩阵的定义式。
• 同书印刷 p154：网的邻接矩阵定义（有边填 $w_{i,j}$，无边填 $\mathrm{\infty }$）， 并给出 C 语言存储表示 AMGraph（vexs[] 顶点表 + arcs[][] 邻接矩阵 + vexnum, arcnum）， 其中以 Maxint 32767 表示极大值。
• 同书印刷 p158：明确"一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一"， 以及邻接表在判边、求入度上的劣势——本篇的对比表以此为准。

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.5，p351。

相关知识

邻接表（$O(n+e)$ 空间，稀疏图默认选择）｜ 十字链表与邻接多重表（补上求入度、删无向边两处短板）｜ 特殊矩阵的压缩存储（对称矩阵的下标换算）｜ Dijkstra / Prim（朴素实现以邻接矩阵为前提）｜ Floyd（在邻接矩阵上做"矩阵逐步合成"）

相关文章

• 图的基本概念
• 邻接表
• 十字链表与邻接多重表
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 最小生成树：Prim
• 最小生成树：Kruskal
• BFS 求无权图最短路径
• Dijkstra 算法
• Floyd 算法
• DAG 描述表达式
• 拓扑排序
• 关键路径

交互体验

前往完整可视化页面 →

真题练习

相关真题（6题）

2023Q4113分2021Q4115分2015Q428分2012Q62分2011Q82分2011Q418分