有向图的邻接表 1 VI 2V 一→51 2|V 3 3V 3 V3 4 V2 5VE G的出边表 G的入边表 北京大学信息学院 版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 26 有向图的邻接表 G7的出边表 G7的入边表
图的邻接表空间代价 n个顶点m条边的无向图 需用(n+2m)个存储单元 n个顶点m条边的有向图 需用(n+m)个存储单元 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 27 图的邻接表空间代价 n个顶点m条边的无向图 需用(n+2m)个存储单元 n个顶点m条边的有向图 需用(n+m)个存储单元
邻接多重表( adjacency multilist) 把邻接表表示中代表同一条边的两 个表目合为一个表目 图的每条边只用一个多重表表目表 小 n包括此边的两个顶点的序号 两个指钍(一个指针指向与第一个顶 点相关联的下一条边,另一个指针指 向与第二个顶点相关联的下一条边) 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 28 邻接多重表(adjacency multilist) 把邻接表表示中代表同一条边的两 个表目合为一个表目 图的每条边只用一个多重表表目表 示 包括此边的两个顶点的序号 两个指针（一个指针指向与第一个顶 点相关联的下一条边，另一个指针指 向与第二个顶点相关联的下一条边）
无向图G6的邻接多重表 1 V 2N2N4边(V,V2) 边(V1,V3) 3V3 4 N5边(V1,V4) 4V4 3N边(,v) N524 边(V2,V4) 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 29 无向图G6的邻接多重表
有向图邻接多重表 在顶点表中设计两个指针 第一个指向以此顶点为始点的第一条边 第二个指向以此顶点为终点的第一条边 ■边表 第一个指针指向始点与本边始点相同的下一 条边 第二个指针指向终点与本边终点相同的下 条边 故仅用表中第一个链便得到有向图的出边 表,仅用第二个链便得到有向图的入边表 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 30 有向图邻接多重表 在顶点表中设计两个指针 第一个指向以此顶点为始点的第一条边 第二个指向以此顶点为终点的第一条边 边表 第一个指针指向始点与本边始点相同的下一 条边 第二个指针指向终点与本边终点相同的下一 条边 故仅用表中第一个链便得到有向图的出边 表，仅用第二个链便得到有向图的入边表