【数据结构】邻接矩阵完全指南：原理、实现与稠密图优化技巧​

导读

大家好，很高兴又和大家见面啦！！！

在上一篇中，我们探讨了图的基本概念与术语，如顶点、边、有向图与无向图的区别等。今天，我们将迈入实战阶段，深入解析图的存储结构——这一复杂关系的「翻译器」。

如何将顶点与边的抽象关系转化为代码可操作的数据？面对稀疏图与稠密图，存储结构的选择如何影响算法效率？本文将以邻接矩阵法为起点，系统拆解图的存储逻辑：

• 从基础定义到代码实现，手把手构建邻接矩阵模型
• 通过矩阵幂运算揭示「路径数量」的隐藏规律（如$A^2$的奇妙意义）
• 无向图对称性、顶点度计算等特性的一一验证

无论你是希望夯实基础，还是渴望用数学工具优化算法，本文的图文解析与场景化案例都将为你提供清晰的技术地图。

一、图的存储结构

图是由顶点集与边集组成，因此我们想要完整的存储图的信息，那就需要完整的将图中的顶点信息以及边的信息给存储下来。

根据不同图的结构和算法，采用不同的存储方式将对程序的效率产生相当大的影响，因此所选的存储结构应适合于待求解的问题。

1.1 分类

在图中我们将会介绍4种存储结构：

• 邻接矩阵法——通过一维数组与二维数组实现
• 邻接表法——通过一维数组与链表实现
• 十字链表法——通过一维数组与链表实现
• 邻接多重表——通过一维数组与链表实现

从实现方式的原理上来看，不管是哪种存储结构，都是需要用到两种存储方式，这刚好对应了图中的两种元素——顶点集与边集。

无需多言，相信大家应该已经猜到了，图中对于顶点集的存储，采用的就是一维数组，而对于边集的存储，则会有所区别。

接下来我们就来看一下图的第一种存储结构——邻接矩阵法，它的实现原理究竟是怎么样的。

二、邻接矩阵法

邻接矩阵法就是指用一维数组存储图中的顶点信息，用二维数组存储图中边的信息（各顶点之间的邻接关系）。

存储顶点之间邻接关系的二维数组称为邻接矩阵。

对于一个顶点数量为 $n$ 的图 $G=(V,E)$ ，其邻接矩阵 $A$ 是一个n阶方阵，即 $n\times n$ 的矩阵。

2.1 邻接矩阵

在邻接矩阵中，我们可以用0和1来表示顶点之间的邻接关系：

在邻接矩阵中，行坐标和列坐标所代表的结点与一维数组中结点对应的下标一致，矩阵的值就是依附于该顶点的边。

比如上图中的边 $(A,B)$ 对应到矩阵 $A$ 中，那就是点$a_{01}$ 与点 $a_{10}$ 这两个点的值均为1；

如果上图为无向图，且我们要表示弧 $<A,B>$ ，那么对应的点就是点 $a_{01}=1$ 与点 $a_{10}=0$ ；

可以看到，邻接矩阵既可以完整的存储无向图中边的信息，也可以完整的存储有向图中弧的信息；

2.2 邻接矩阵存储网

当我们给图的每条边（弧）加上权值时，该图就变成了一张网，那此时我们又应该如何通过邻接矩阵存储边的信息呢？

对于网的存储也不复杂，我们可以预设一个值如 $\infty$ 表示两个顶点之间不存在边。

比如当网中各条边的权值都大于等于 $0$ 时，我们就可以预设 $-1$ 表示两个顶点之间不存在边；

在这个网中，存储顶点信息的一维数组为：

0	1	2	3
a	b	c	d

当我们用邻接矩阵来存储边的信息时，那对应的邻接矩阵为：

	0	1	2	3
0	-1	1	3	4
1	1	-1	2	-1
2	3	2	-1	-1
3	4	-1	-1	-1

三、邻接矩阵的存储结构

邻接矩阵的存储结构的C语言表示为：

typedef char VertexType;
typedef int EdgeType;
#define MAXSIZE 5	// 一维数组最大长度
//邻接矩阵法
typedef struct Adjacency_Matrix {VertexType Vertex[MAXSIZE];			// 一维数组存储顶点信息EdgeType Edge[MAXSIZE][MAXSIZE];	// 二维数组存储边信息int len_ver;						// 当前顶点数量int len_edge;						// 当前边数量
}AMGraph;								// 邻接矩阵图

经过前面的介绍，相信大家都应该是能够理解这个存储结构的，这里我就不再赘述；

四、算法评价

4.1 时间复杂度

在邻接矩阵中，时间复杂度我们需要从顶点和边两个方面分别来评价：

• 当我们遍历顶点时，就是在遍历一个一维数组，那么遍历顶点的时间复杂度为：$O(N)$
• 当我们遍历边时，就是在遍历一个二维数组，那么遍历边的时间复杂度为：$O(N^2)$

因此我们遍历整个图的时间复杂度就应该为：$$T(n)=O(N)+O(N^2)=O(N^2)$$

4.2 空间复杂度

在邻接矩阵法中，当我们为顶点数为 $n$ 的图申请空间时，我们总共需要分别为顶点和边申请空间：

• 顶点：需要申请 $n$ 个空间
• 边：需要申请 $n^2$ 个空间

记录顶点数和边数的变量空间为一个常数空间，因此整个图所对应的空间复杂度应该为：
$$T(n)=O(N)+O(N^2)+O(1)=O(N^2)$$

五、邻接矩阵的特点

图的邻接矩阵表示法具有以下特点：

1. 无向图的邻接矩阵一定是一个对称矩阵（并且唯一）。
2. 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非预设值元素如 $\infty$）的个数正好是顶点 $i$ 的度 $TD(v_i)$ 。
3. 对于有向图，邻接矩阵的第 $i$ 行非零元素（或非 $\infty$元素）的个数正好是顶点 $i$ 的出度 $OD(v_i)$ ；第 $i$ 列非零元素（或非 $\infty$ 元素）的个数正好是顶点 $i$ 的入度 $ID(v_i)$ 。
4. 用邻接矩阵存图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
5. 稠密图（边数较多的图）适合采用邻接矩阵的存储表示。
6. 设图 $G$ 的邻接矩阵为 $A$ ，$A^n$ 的元素 $A_{[i][j]}^n$ 等于由顶点i到顶点j的长度为n的路径的数目。

接下来我们来对这些特点逐个解析；

5.1 特点1解析

在邻接矩阵中，我们采用的是n阶方阵存储的图中边的信息。

在无向图中，当两个顶点之间存在将其连通的边时，从有向图的角度来看，这条边是一条双向边：

因此，在邻接矩阵中的反映就一定是一个对称矩阵。

在第三章——特殊矩阵的压缩存储中我们有详细介绍过如何对像对称矩阵这种特殊矩阵进行压缩存储，有需要的朋友可以点击链接详细阅读。

5.2 特点2解析

在无向图中，一个顶点的度就是依附于该顶点的边的数量。

在邻接矩阵中，每一行或者每一列都表示的是依附于该顶点的边。

因此在第 $i$ 行或者第 $i$ 列中所有不为0，或者存储网时，不为预设值（如 $\infty 、-1\dots \dots$）的点 $a_{ij}$ 或者 $a_{ji}$ 的数量之和就是该顶点 $i$ 的度 $TD(v_i)$ 。

这里需要注意，当我们计算了第 $i$ 行就不需要再计算第 $i$ 列，即行和列只需要取其一即可；

5.3 特点3解析

在有向图中，邻接矩阵中点 $a_{ij}$ 的行坐标 $i$ 表示的是弧尾，列坐标 $j$ 表示的是弧头。这里我们用实例来说明：

在这个有向图中，我们在存储顶点 $a,b$ 时分别将顶点 $a$ 存储在下标0，顶点 $b$ 存储在下标1处，此时弧 $<a,b>$ 在邻接矩阵中存储时，代表该弧的点为 $a_{01}$ ，可以看到该点的横坐标就是弧尾，纵坐标就是弧头；

同理，弧 $<b,a>$ 所对应的邻接矩阵中的点为 $a_{10}$，同样的，横坐标代表的是弧尾，纵坐标代表的是弧头。

因此我们说在有向图中，邻接矩阵的第 $i$ 行非零元素的个数正好是顶点 $i$ 的出度 $OD(v_i)$;
第 $i$ 列非零元素的个数正好是顶点 $i$ 的入度 $ID(v_i)$

5.4 特点4解析

在邻接矩阵中，我们要求边的个数，实际上就是遍历整个二维数组，而二维数组遍历的时间复杂度为：$O(N^2)$ ，因此所耗费的时间代价是巨大的。

5.5 特点5解析

在邻接矩阵中，我们在存储边的信息时，不管两个之间是否存在边，我们都为其申请了空间。

试想一下，如果在一个稀疏图中，边的数量为 $|E|<|V|lo{g}_2|V|$ ，也就是说，如果该图中有4个顶点时，边的数量不足8个，但是我们通过邻接矩阵存储时，申请了 $4^2=16$ 个空间。

此时我们对空间的实际利用率 $<50$ ，换句话说就是我们浪费的空间 $>50$ 。

这么一看，当我们用邻接矩阵法存储这种边数量很少的图时，会造成大量的空间浪费。

因此，邻接矩阵法不适合存储稀疏图这种边数量很少的图，更加适合存储稠密图这种边数量很多的图。

5.6 特点6解析

要理解特点6，首先我们要清楚矩阵相乘的规则：

• 当且仅当一个矩阵的行数与另一个矩阵的列数相等时两个矩阵才能相乘；
• 当矩阵 $A$ 为 $m\times n$ 的矩阵与矩阵 $B$ 为 $n\times m$ 的矩阵相乘时， 得到的矩阵 $C$ 中的元素 $c_{ij}$ 为：
  $$c_{ij}=\sum _{k=1}^n{a}_{ik}\cdot b_{kj}$$

这里我们以有向图 $G$ 为例进行说明：

在该有向图中，顶点a对应的下标为0，顶点b对应的下标为1，其邻接矩阵 $A$ 如下所示：

	0	1
0	0	1
1	0	0

对应的 $A^2$ 中的个元素为：
$$\begin{gathered} a_{00}^{\prime }=a_{00}\times a_{00}+a_{01}\times a_{10}=0+0=0 \\ {a}_{01}^{\prime }=a_{00}\times a_{01}+a_{01}\times a_{11}=0+0=0 \\ {a}_{10}^{\prime }=a_{10}\times a_{00}+a_{11}\times a_{10}=0+0=0 \\ {a}_{11}^{\prime }=a_{10}\times a_{01}+a_{11}\times a_{11}=0+0=0 \end{gathered}$$

以 $a_{00}^{\prime }$ 为例，该点表示的是顶点 $a^{\prime }$ 到顶点 $a^{\prime }$ 的长度为2的路径的数目。

$$a_{00}^{\prime }=a_{00}\times a_{00}+a_{01}\times a_{10}=0+0=0$$

该公式中各项的含义为：

• $a_{00}$：顶点a到顶点a的弧
• $a_{01}$：顶点a到顶点b的弧
• $a_{10}$：顶点b到顶点a的弧

我们要想得到 $A^2$ 中 顶点 $a^{\prime }$ 到顶点 $a^{\prime }$ 的长度为2的路径，那我们就有两种方式从顶点 $a^{\prime }$ 到达顶点 $a^{\prime }$：

• 从顶点 $a^{\prime }$ 到达顶点 $a^{\prime }$，再从顶点 $a^{\prime }$ 到达顶点 $a^{\prime }$，此时路径长度为2；
• 从从顶点 $a^{\prime }$ 到达顶点 $b^{\prime }$，再从顶点 $b^{\prime }$ 到达顶点 $a^{\prime }$，此时的路径长度为2；

因此要得到长度为2的路径，就必须存在弧 $<b,a>$ ，但是图中不存在弧 $<b,a>$ 因此就不存在长度为2的路径，此时长度为2的路径的数量为0；

同理，我们也能够验证矩阵 $A^2$ 中的其它三个元素。

这个特点比较绕，如果实在不理解也没关系，我们只做了解即可。

结语

邻接矩阵法以矩阵的简洁性，将图的顶点与边关系凝练为二维数组的0/1或权值，成为稠密图存储的经典选择。通过本文的解析，我们可总结其核心价值：

1. 直观性：矩阵行列直接对应顶点，快速判断任意两顶点是否邻接（O(1)时间复杂度）；
2. 数学优势：矩阵运算（如幂运算）可高效推导路径数与连通性；
3. 场景适配：尤其适合边数接近顶点数平方的稠密图，避免空间浪费。

然而，邻接矩阵的O(n²)空间复杂度也提醒我们：面对稀疏图（如社交网络），邻接表等结构可能更具优势。技术的选择永远服务于具体问题，理解不同存储结构的特性，方能灵活应对千变万化的算法需求。

拓展思考：若图的顶点动态增减，邻接矩阵如何优化？权值无穷大（∞）在代码中应如何合理表示？欢迎在评论区探讨你的见解，或继续阅读本系列的下一篇——《邻接表：稀疏图的存储利器》。

---

🌟 如果本文对你有所帮助，欢迎：
• 关注[👉] 获取更多算法与数据结构深度解析
• 点赞[👍] 支持原创内容
• 收藏[📁] 备查或分享给需要的伙伴
• 转发[🔄] 让知识传播更远

你的每一次互动，都是我们持续创作的动力！