631图的相邻矩阵( adjacency matrix)表示法 ■相邻矩阵 表示顶点间相邻关系的矩阵。 若G是一个具有n个顶点的图,则G的 相邻矩阵是如下定义的n×n矩阵: A[ij=1,若(V,v)(或<V,V>) G的边; [j]=0,若(V,V)(或<V,V>) 是图G的边。 相邻矩阵的空间代价为o(n2) 北京大学信息学院 版权所有,转载或翻印必究 Page 16
北京大学信息学院 ©版权所有，转载或翻印必究 Page 16 6.3.1 图的相邻矩阵（adjacency matrix）表示法 ◼ 相邻矩阵 ◼ 表示顶点间相邻关系的矩阵。 ◼ 若G是一个具有n个顶点的图，则G的 相邻矩阵是如下定义的nn矩阵： A[i,j]=1，若（Vi，Vj）（或<Vi，Vj >） 是图G的边； A[i,j]=0，若（Vi，Vj）（或<Vi，Vj>） 不是图G的边。 ◼ 相邻矩阵的空间代价为O(n2)
631图的相邻矩阵( adjacency matrix)表示法(续) 01000 1000 A7=01010 10000 00010 北京大学信息学院 版权所有,转载或翻印必究 Page 17
北京大学信息学院 ©版权所有，转载或翻印必究 Page 17 6.3.1 图的相邻矩阵（adjacency matrix）表示法（续） A7= 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0
631图的相邻矩阵( adjacency matri)表示法(续) 03015 3040 A4= 15 0406 4 15060 北京大学信息学院 版权所有,转载或翻印必究 Page 18
北京大学信息学院 ©版权所有，转载或翻印必究 Page 18 6.3.1 图的相邻矩阵（adjacency matrix）表示法（续） A4= 0 3 0 15 3 0 4 0 0 4 0 6 15 0 6 0
632图的邻接表 ( adjacency list)表示法 V3 6 G7 北京大学信息学院 版权所有,转载或翻印必究 Page 19
北京大学信息学院 ©版权所有，转载或翻印必究 Page 19 6.3.2 图的邻接表 （adjacency list）表示法
632图的邻接表( adjacency ist)表示法(续) G6邻接表表示 北京大学信息学院 版权所有,转载或翻印必究 Page 20
北京大学信息学院 ©版权所有，转载或翻印必究 Page 20 6.3.2 图的邻接表（adjacency list）表示法（续） G6邻接表表示