第五章 图(二)

《第五章 图(二)》由会员分享，可在线阅读，更多相关《第五章 图(二)（13页珍藏版）》请在文档大全上搜索。

1、6.3 图的存储结构6.3.1 邻接矩阵（1）图的邻接矩阵表示用数组记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。（2）邻接矩阵设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 ，定义：中的边不是或若中的边是或若)(,),()(,),(01GEvvvvGEvvvvajijijijiij邻接矩阵举例，如图7.10、7.110101101001011010ija1203012000101010aij7.10 无向图及其邻接矩阵无向图及其邻接矩阵 7.11 有向图及其邻接矩阵有向图及其邻接矩阵注：无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对

2、称。在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度；在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 行 1 的个数可得顶点 j 的入度。网络的邻接矩阵jiji,ji,jiji,ji,jiji若若或或且且若若或或且且若若,)(,)(),(0EEEEWjia068053290410aij230186312954邻接矩阵GNNN个顶点从0到N-1编号Gij =10若是是G中的边中的边否则v0 v1 v2 v3v4v5v6v7v8v9v00101000000301524v1v2v3v41010011010011000010011010010001000000

3、0017689v5v6v7v80000100010000110100001011011010011001001v90000110010邻接矩阵问题：对于无向图的存储，怎样可以省一半空间？v0v1v2v3v4v5v6v7v8v9用一个长度为N(N+1)/2的1维数组A存储v0v1v2v30101101101001100001001100001000100000000则Gij在A中对应的下标是：v4v5v6v7v8v9000000010000110000001100010001101011010110001000011001110010( i(i+1)/2 + j )对于网络，只要把Gij的值定义

4、为边的权重即可。问题：vi和vj之间若没有边该怎么表示？邻接矩阵 有什么好处？ 直观、简单、好理解 方便检查任意一对顶点间是否存在边 方便找任一顶点的所有“邻接点”（有边直接相连的顶点） 方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”） 无向图：对应行（或列）非0元素的个数 有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”邻接矩阵 有什么不好？ 浪费空间 存稀疏图（点很多而边很少）有大量无效元素 对稠密图（特别是完全图）还是很合算的 浪费时间 统计稀疏图中一共有多少条边6.3.2 邻接表（1）无向图的邻接表同一个顶点发出的边链接在同一个边链

5、表中，每一个链结点代表一条边(边结点), 结点中有另一顶点的下标 dest 和指针next。BCADdata adjABCD0123dest nextdest next 130210（2）有向图的邻接表和逆邻接表ABCdata adjABC012dest nextdest next 102 data adjABC012dest next 011（3）网络 (带权图) 的邻接表data adjABCD0123dest cost next 1 53 62 83 21 99528BACD6邻接表：GN为指针数组，对应矩阵每行一个链表，只存非0元素 对于网络，结构中要增加权重的域。G0130124G1G2G35173510402635G4G52251946896G65873789G7G8G969435568一定要够稀疏才合算啊邻接表 方便找任一顶点的所有“邻接点” 节约稀疏图的空间 需要N个头指针 + 2E个结点（每个结点至少2个域） 方便计算任一顶点的“度”？ 对无向图：是的 对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度” 方便检查任意一对顶点间是否存在边？