相邻矩阵 表示顶点间相邻关系的矩阵。 若G是一个具有n个顶点的图,则G的 相邻矩阵是如下定义的nxn矩阵: A[i=1:若(V,V)(或<V,V>) 是图G的边; =0,若(V,V)(或<V,V>) 图G的边。 相邻矩阵的空间代价为(n2) 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 21 相邻矩阵 表示顶点间相邻关系的矩阵。 若G是一个具有n个顶点的图，则G的 相邻矩阵是如下定义的n×n矩阵： A[i,j]=1，若（Vi，Vj）（或<Vi，Vj>） 是图G的边； A[i,j]=0，若（Vi，Vj）（或<Vi，Vj>） 不是图G的边。 相邻矩阵的空间代价为Θ(n2)
「01000 10001 A7=01010 10000 V3 00010(V 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 22 A7= 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦
03015 3040 A4= 15 0406 15060 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 23 A4= 3 15 3 4 4 0 0 0 0 0 0 0 0 6 15 6 ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦
632图的邻接表 ( adjacency list)表示法 VA V5 V V2 V G6 G7 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 24 6.3.2 图的邻接表 （adjacency list）表示法 G6 G7
无向图G6邻接表表示 1V1 3 4 2 V2 4 3V 2 4V4 →→2 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 25 无向图G6邻接表表示