6.2.2 邻接表法
原书定位
印刷页P207起,对应PDF第219页。下文为目视整理的知识提要;完整内容见原书对照。
顶点表按顺序存储,每个顶点连接一条邻接点链表。有向图通常保存出边;逆邻接表保存入边。无向图每条边记录两次,有向图每条弧一次,空间均为 。
枚举出邻边的时间与出度成正比;查询指定边需在对应链表搜索。有向图计算全部入度可遍历所有边,。链表内部次序可不同,同一图的邻接表及遍历序列不一定唯一。

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

无向图和有向图的邻接表,原书P208。
对应练习
关联知识
原书对照
展开原书对照截图


