邻接矩阵 核心思想 邻接矩阵的核心特点：
二维数组直接映射：用 A[i][j] 表示顶点 i 与顶点 j 之间的关系无权图：A[i][j] = 1 表示存在边，A[i][j] = 0 表示不存在边带权图：A[i][j] = w 表示边的权值，A[i][j] = ∞ 表示不存在边无向图的对称性：无向图的邻接矩阵是对称矩阵，即 A[i][j] = A[j][i]无向图示例（4 个顶点）：
图: 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）：
邻接矩阵:
0 1 2
0 [0, 1, 1]
1 [0, 0, 0]
2 [0, 1, 0]注意：有向图的邻接矩阵不一定对称。
交互可视化 通过下方的交互动画，你可以逐步观察邻接矩阵的执行过程：
加载可视化中...抽屉全屏操作详解 存储结构 邻接矩阵的 C 语言定义：
c#define MaxVertexNum 100 // 最大顶点数
#define INFINITY 65535 // 表示无穷大（用于带权图）
// 无权图
typedef struct {
char vex[MaxVertexNum]; // 顶点表
int edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵（0/1）
int vexNum, edgeNum; // 顶点数、边数
} MGraph;
// 带权图
typedef struct {
char vex[MaxVertexNum];
int edge[MaxVertexNum][MaxVertexNum]; // 权值，无边时为 INFINITY
int vexNum, edgeNum;
} WGraph;初始化与建图：
c// 初始化无向无权图
void initGraph(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] = 0;
}
// 添加无向边
void addEdge(MGraph *G, int u, int v) {
G->edge[u][v] = 1;
G->edge[v][u] = 1; // 无向图需对称赋值
G->edgeNum++;
}带权图的邻接矩阵初始化时，将所有元素设为 INFINITY，对角线设为 0。
度的计算 无向图：顶点 i 的度 = 第 i 行（或第 i 列）中非零元素的个数。
c// 无向图求顶点 i 的度
int degree(MGraph *G, int i) {
int d = 0;
for (int j = 0; j < G->vexNum; j++)
if (G->edge[i][j] != 0)
d++;
return d;
}有向图：
类型计算方法出度 OD(i)第 i 行非零元素个数入度 ID(i)第 i 列非零元素个数度 TD(i)OD(i) + ID(i)c// 有向图求顶点 i 的出度和入度
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 行 → 出度
if (G->edge[j][i] != 0) (*inD)++; // 第 i 列 → 入度
}
}优缺点分析 优点缺点判断两顶点是否相邻：O(1)，直接访问 A[i][j]空间复杂度 O(V²)，稀疏图浪费严重实现简单，适合稠密图统计边数需遍历整个矩阵，O(V²)方便计算矩阵运算（如求路径数）增删顶点不灵活，需调整矩阵大小无向图可压缩存储（对称矩阵只存上/下三角）找某顶点所有邻接点需扫描一整行，O(V)适用场景：顶点数不多、边数较多的稠密图。当边数远小于 V² 时（稀疏图），应优先考虑邻接表。
复杂度分析 操作时间复杂度说明判断边是否存在O(1)直接访问 A[i][j]求某顶点的度O(V)遍历一行（或一列）求所有边数O(V²)遍历整个矩阵插入/删除一条边O(1)修改矩阵元素插入/删除一个顶点O(V²)需调整矩阵结构空间复杂度：O(V²)，无论图是稠密还是稀疏都需要 V×V 的存储空间。
本文对应考点 无向图邻接矩阵的对称性（选择题/判断题高频）从邻接矩阵求顶点的度/出度/入度（填空题高频考查）邻接矩阵 vs 邻接表的优缺点对比（简答题高频）邻接矩阵的空间复杂度 O(V²) 及适用场景（概念题）带权图邻接矩阵中 ∞ 和 0 的含义区分（易错点）邻接矩阵 A 的幂次 Aⁿ[i][j] 表示顶点 i 到 j 长度为 n 的路径条数（偶尔考）易错：无向图的邻接矩阵是对称矩阵，只需存上三角或下三角即可节省一半空间。但有向图的邻接矩阵不一定对称。408 选择题常问"无向图邻接矩阵的性质"。
易错：邻接矩阵中，第 i 行非零/非无穷元素的个数 = 顶点 i 的出度（有向图）或度（无向图）。第 i 列非零元素的个数 = 顶点 i 的入度（有向图）。
相关知识 邻接表：稀疏图更适合邻接表，空间 O(V+E)Dijkstra 算法：Dijkstra 朴素实现基于邻接矩阵Floyd 算法：Floyd 直接操作邻接矩阵做全源最短路径相关文章图的基本概念邻接表十字链表与邻接多重表广度优先搜索（BFS）深度优先搜索（DFS）最小生成树：Prim最小生成树：KruskalBFS 求无权图最短路径Dijkstra 算法Floyd 算法DAG 描述表达式拓扑排序关键路径交互体验 前往完整可视化页面 → 真题练习 相关真题（6题）2023Q41综合题10分去刷题邻接矩阵图基本概念2021Q41综合题5分去刷题邻接矩阵图基本概念2015Q42综合题10分去刷题邻接矩阵图基本概念2012Q6选择题2分去刷题邻接矩阵拓扑排序2011Q8选择题2分去刷题邻接矩阵邻接表拓扑排序2011Q41综合题12分去刷题关键路径邻接矩阵