（b1）邻接矩阵

官官方信息技术老师·12 页·深入（追求细节与边界）·0 次浏览·3 天前

✦ （b1）邻接矩阵信息技术（b1）邻接矩阵接口

邻接矩阵矩阵幂路径计数稀疏图

（b1）邻接矩阵

看清一张图如何装进矩阵：构造细节、矩阵幂与路径计数、选型边界

按空格/→ 演示下一步

1 / 12 页

全部页面点击任意一页，跳回舞台从这页播放

邻接矩阵矩阵幂路径计数稀疏图

（b1）邻接矩阵

看清一张图如何装进矩阵：构造细节、矩阵幂与路径计数、选型边界

1第 1 页 · （b1）邻接矩阵

接口

邻接矩阵那张表你看到了——n×n 的格子，0 和 1 填在里面。但程序里你不会直接戳那些格子，你会调方法：addVertex、addEdge、adj……这些方法的「签名清单」，就是邻接矩阵的接口。

接口是约定

只声明能调哪些操作、各自的输入输出，不暴露内部数据

邻接矩阵的典型接口

V()、E()、addEdge()、adj()、hasEdge() 这类方法集

实现可替换

同一接口可由矩阵、表、链表等不同数据结构实现

接口 ≠ 实现

接口稳定，实现可重构；这是软件工程的基石之一

电器插座标准对应 →软件接口

插座规定电压、孔型（接口约定），里面是铜片还是合金（实现细节）你不管；电器按标准造，换品牌也能插

2第 2 页 · 接口

邻接矩阵+关联矩阵

上一页我们认识了邻接矩阵,它用n×n方阵记录「顶点之间是否相邻」。但图论里还有一类问题:「这条边连了哪两个端点」——邻接矩阵回答起来很别扭,需要请出关联矩阵。

邻接矩阵形式

n×n方阵,A[i][j]表示顶点i与j是否直接相连,1为有边、0为无边

无向图对称性

无向图中A[i][j]=A[j][i],矩阵沿对角线对称;对角线为0(默认无自环)

关联矩阵形式

n×m矩阵,n为顶点数、m为边数,B[i][j]记录顶点i与边j的关联情况

取值含义

无向图B[i][j]∈{0,1,2};有向图B[i][j]∈{-1,0,1},+1为尾-1为头

使用场景对比

邻接矩阵适合查两顶点关系;关联矩阵适合分析边的局部性质或求解割集

通讯录 vs 活动签到表对应 →邻接矩阵 vs 关联矩阵

通讯录按人查「认识谁」(顶点→顶点);签到表按活动查「谁来参加」(顶点→边)

A_{ij}=\begin{cases}1,&(v_i,v_j)\in E\\0,&\text{otherwise}\end{cases}

3第 3 页 · 邻接矩阵+关联矩阵

实例

前几页讲了邻接矩阵的接口——行是起点、列是终点、里面写 0 或 1。但抽象的表格看着不过瘾。这一页用 4 个顶点的小图把它算出来，看看到底怎么写、有什么规律、什么时候用最划算。

示例图

4 个顶点 A~D，边 AB、BC、CD、DA 围成一个环

构造规则

顶点 i 与 j 有连边 → A[i][j]=1；否则 =0

关键观察

无向图关于主对角线对称；对角线全 0（无自环）

适用场景

稠密图（边数 ~n²）空间 O(n²) 划算；O(1) 判两顶点是否相邻

微信好友通讯录对应 →邻接矩阵

通讯录第 i 行第 j 列打 √ ↔ 矩阵 A[i][j]=1

A_{ij}=\begin{cases}1,&(v_i,v_j)\in E\\0,&(v_i,v_j)\notin E\end{cases}

4第 4 页 · 实例

顶点和边

邻接矩阵每个格子编码两个顶点之间的边关系。要真正用好矩阵，先回到最底层——顶点和边本身是什么。

顶点（Vertex）

图中独立的基本单元，代表一个实体或状态

边（Edge）

顶点间的连接关系，可有方向或权重

图的形式化

G=(V,E)，V 是顶点集合，E 是边集合

与邻接矩阵的关系

矩阵行列数等于 |V|，元素编码边的信息

边界情况

自环、重边会破坏简单图假设，需特别处理

城市和公路网对应 →顶点和边

城市=顶点，公路=边；研究路网本质就是研究图

n = |V| \Rightarrow A \in \mathbb{R}^{n \times n}

5第 5 页 · 顶点和边

邻接矩阵

图的骨架是顶点和边。但图一大（百万级顶点），计算机靠肉眼数不过来——它需要一张结构化的「表」来回答「两点能否直达」「走 k 步有几条路」这类问题：邻接矩阵。

形式定义

n×n 方阵，A[i][j] 为 i→j 的边数（无权取 0/1，加权取权重）

对称与自环

无向图 A=Aᵀ；有向图不一定；A[i][i] 记录自环数

幂即走法

Aᵏ[i][j] = 从 i 到 j 长度恰 k 的走法数（含重复顶点）

度与谱

行和为顶点度；最大特征值≤最大度，k-正则图时取等

何时用矩阵

稠密图、需 O(1) 边查询、谱方法时优势大；稀疏图常改邻接表

城市直飞航班表对应 →邻接矩阵

行=出发城市，列=到达城市；格子=直飞数；A²则是经一次中转的路径数

A^k_{ij} = \text{从 } i \text{ 到 } j \text{ 长度恰 } k \text{ 的走法数}

6第 6 页 · 邻接矩阵

顶点静态操作

邻接矩阵让我们 O(1) 判断两顶点是否相连，但「连了谁、怎么加、怎么删」这些针对顶点本身的操作，才是构建和修改图的基础。这页把它们摊开，看清每一步的真实代价。

插入顶点

矩阵扩一行一列至 (n+1)×(n+1)，新顶点与旧顶点边权置零或∞，时间 O(n)

删除顶点

删除对应行和列，后续顶点编号前移以保持矩阵紧凑，时间 O(n)

修改顶点信息

顶点表内直接覆盖，不动邻接矩阵，时间 O(1)

查找顶点

按编号 O(1)，按其他字段需顺序扫描 O(V)

电影院座位表对应 →顶点表+邻接矩阵

加座位=矩阵加行加列；拆座位=撕行撕列再前移；按票号查=直查，按姓名查=逐行扫

7第 7 页 · 顶点静态操作

边操作

上一页我们搭好了矩阵的骨架，现在问题来了：边怎么操作？在邻接矩阵里，每条边都对应矩阵中的一个格子——这让边操作异常直接。

查边

判断 u→v 是否有边：直接看 M[u][v] 是否为 0，时间 O(1)

增/删边

写入或清零 M[u][v]，无向图需同步改对称位置，时间 O(1)

找邻居

遍历第 u 行所有列，找 M[u][v]≠0 的 v，时间 O(V)

枚举所有边

扫描整个矩阵（或仅上三角）统计非零元素，时间 O(V²)

Excel 表格的单元格对应 →邻接矩阵的边操作

每个 (u,v) 是一个单元格；查、增、删都是直接定位到那个格子读写

8第 8 页 · 边操作

顶点动态操作

静态操作只看，动态操作要改。当图的结构在变化——加一个点、减一个点——邻接矩阵会怎么响应？这页我们把增删顶点的代价算清楚。

添加顶点

矩阵末尾追加一行一列，新行新列其他位置默认 0

删除顶点

移除对应行和列，必要时整体前移压缩

时间代价

增删顶点都是 O(V)，瓶颈在矩阵调整而非逻辑

班级花名册加新同学对应 →邻接矩阵加一个顶点

新同学要占一行一列，老师要重新填一遍和所有人的关系

9第 9 页 · 顶点动态操作

综合评价

前面我们一层层剥开邻接矩阵：从定义、接口，到增删操作。现在把所有线索收拢，回答最关键的问题：它强在哪、短在哪、最该用在哪。

空间换时间

O(V²) 空间换 O(1) 的边存在性查询

稠密图首选

边数接近 V² 时，空间利用率与查询效率同时拉满

顶点静态时最强

顶点编号固定后，矩阵结构最稳定，无需重建

顶点动态代价高

增删顶点需整体迁移或重映射，不适合频繁变动

典型应用

完全图判定、传递闭包、图同构、子图匹配

全员通讯录互查表对应 →邻接矩阵

n 人占 n×n 格，标1代表两人认识；查任意两人是否相连只看一眼，但人数一变整张表都要重排

A^{k}[i][j] = \text{顶点 } i \text{ 到 } j \text{ 长度恰为 } k \text{ 的路径数}

10第 10 页 · 综合评价

本节要点

✓查边 O(1)、边操作 O(1)：但空间固定为 V²
✓顶点增删最坏 O(V²)：图结构变化时需谨慎
✓适合稠密图：边数接近 V² 时空间利用率最高
✓用一维数组可省一半空间：因无向图矩阵对称且对角无用
✓顶点频繁变化时改用邻接表：邻接矩阵会反复拷贝

延伸主题：邻接表：稀疏图的主选方案邻接矩阵的矩阵运算：路径与连通性稀疏矩阵压缩存储：CSR/CSC

11第 11 页 · 本节要点

课后思考

三个开放性问题检验理解程度

课后思考

三个开放性问题检验理解程度

12第 12 页 · 课后思考