无向图G6邻接表表示 有向图的邻接表 →4 →6 回|G的出边表 G的入边表 邻接多重表( adjacency 图的邻接表空间代价 multilist) n个顶点m条边的无向图 把鉍替表素示中尖春同一条边的两 需用(n+2m)个存储单元 ■图的每条边只用一个多重表表目表 n个顶点m条边的有向图 需用(n+m)个存储单元 包括此边的两个顶点的序号 与器 项点希笑联下个禁 无向图G6的邻接多重表 有向图邻接多重表 在顶点表中设计两个指针 2NN边(v2) 个指向以此顶点为始点的第一条边 指向以此项点为终点的第一条边 边表 3w个为[4N边,v 个指针指向始点与本边始点相同的 第二个指针指向终点与本边终点相同的下 23N边(2.V N24边(:,v 穀仅很聋棗墨个韃得猾碧商閣装 55 北京大学信息学院 ©版权所有，转载或翻印必究 Page 25 无向图G6邻接表表示 北京大学信息学院 ©版权所有，转载或翻印必究 Page 26 有向图的邻接表 G7的出边表 G7的入边表 北京大学信息学院 ©版权所有，转载或翻印必究 Page 27 图的邻接表空间代价 „ n个顶点m条边的无向图 „ 需用(n+2m)个存储单元 „ n个顶点m条边的有向图 „ 需用(n+m)个存储单元 北京大学信息学院 ©版权所有，转载或翻印必究 Page 28 邻接多重表(adjacency multilist) „ 把邻接表表示中代表同一条边的两 个表目合为一个表目 „ 图的每条边只用一个多重表表目表 示 „ 包括此边的两个顶点的序号 „ 两个指针（一个指针指向与第一个顶 点相关联的下一条边，另一个指针指 向与第二个顶点相关联的下一条边） 北京大学信息学院 ©版权所有，转载或翻印必究 Page 29 无向图G6的邻接多重表 北京大学信息学院 ©版权所有，转载或翻印必究 Page 30 有向图邻接多重表 „ 在顶点表中设计两个指针 „ 第一个指向以此顶点为始点的第一条边 „ 第二个指向以此顶点为终点的第一条边 „ 边表 „ 第一个指针指向始点与本边始点相同的下一 条边 „ 第二个指针指向终点与本边终点相同的下一 条边 „ 故仅用表中第一个链便得到有向图的出边 表，仅用第二个链便得到有向图的入边表