6.2.1 邻接矩阵法

教材导航 · 第6章

原书定位

印刷页P206起,对应PDF第218页。下文为目视整理的知识提要;完整内容见原书对照。

用 n×nn\times n 矩阵表示边。无权图可用 0、1;带权图应约定无边标志,若允许零权边就不能以 0 统一代表无边,常用 ∞\infty。

空间 O(n2)O(n^2),查询指定两点是否相邻为 O(1)O(1),枚举一个顶点的邻边为 O(n)O(n)。无向图矩阵对称;有向图行统计出度、列统计入度。带权图应统计存在的边,而非把权值直接相加当度数。

对 0、1 邻接矩阵作普通矩阵乘法,(Ak)ij(A^k)_{ij} 表示从 ii 到 jj 长度为 kk 的游走数,允许重复顶点,不能直接解释为简单路径数。

有向图、无向图及带权图的邻接矩阵

有向图、无向图及带权图的邻接矩阵,原书P206。

对应练习

6.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P206,PDF第218页

原书对照,原书P207,PDF第219页