6.2.1 邻接矩阵法
原书定位
印刷页P206起,对应PDF第218页。下文为目视整理的知识提要;完整内容见原书对照。
用 矩阵表示边。无权图可用 0、1;带权图应约定无边标志,若允许零权边就不能以 0 统一代表无边,常用 。
空间 ,查询指定两点是否相邻为 ,枚举一个顶点的邻边为 。无向图矩阵对称;有向图行统计出度、列统计入度。带权图应统计存在的边,而非把权值直接相加当度数。
对 0、1 邻接矩阵作普通矩阵乘法, 表示从 到 长度为 的游走数,允许重复顶点,不能直接解释为简单路径数。

有向图、无向图及带权图的邻接矩阵,原书P206。
对应练习
关联知识
原书对照
展开原书对照截图

