6.2.2 邻接表法

教材导航 · 第6章

原书定位

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

顶点表按顺序存储,每个顶点连接一条邻接点链表。有向图通常保存出边;逆邻接表保存入边。无向图每条边记录两次,有向图每条弧一次,空间均为 O(n+m)O(n+m)。

枚举出邻边的时间与出度成正比;查询指定边需在对应链表搜索。有向图计算全部入度可遍历所有边,O(n+m)O(n+m)。链表内部次序可不同,同一图的邻接表及遍历序列不一定唯一。

邻接表的顶点结点与边结点

邻接表的顶点结点与边结点,原书P207。

无向图和有向图的邻接表

无向图和有向图的邻接表,原书P208。

对应练习

6.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

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

原书对照,原书P208,PDF第220页

原书对照,原书P209,PDF第221页