/添加一条边 bool setEdge(int from Vertex, int toVertex, int 63图的存储结构 bool delEdge(int fromVertex, int toVertex); 返回TRUE,否则返回 FALSE 令631图的相邻矩阵 bool IsEdge(Edge oneEdge); //返回边 one Edgel的始点 ( adjacency matrix)表示法 /返回边 one Edge的终点 令632图的邻接表( adjacency vErtex(Edge oneEdge); //返回边 oneEdge的权 list)表示法 int Weight(Edge oneEdge); 邻接多重表( adjacency multilist) 相邻矩阵 01000 表示顶点间相邻关系的矩阵。 若G是一个具有n个顶点的图,则G的 10001 相邻矩阵是如下定义的nxn矩阵 A7=01010 A[ij=1,若(V,V)(或<V,v>) 是图G的边 10000 ^ 00010 图G的边 相邻矩阵的空间代价为e(n2) 亡 宜大息单 权新有,轴彩光 632图的邻接表 ( adjacency list)表示法 3040 15 = 0406 15060 值惠单4 北京大学信息学院 ©版权所有，转载或翻印必究 Page 19 //添加一条边 bool setEdge(int fromVertex,int toVertex,int weight); //删一条边 bool delEdge(int fromVertex,int toVertex); //如果oneEdge是边则返回TRUE，否则返回FALSE bool IsEdge(Edge oneEdge); //返回边oneEdge的始点 int FromVertex(Edge oneEdge); //返回边oneEdge的终点 int ToVertex(Edge oneEdge); //返回边oneEdge的权 int Weight(Edge oneEdge); }; 北京大学信息学院 ©版权所有，转载或翻印必究 Page 20 6.3 图的存储结构 „ 6.3.1 图的相邻矩阵 （adjacency matrix）表示法 „ 6.3.2 图的邻接表（adjacency list）表示法 „ 邻接多重表(adjacency multilist) 表示法 北京大学信息学院 ©版权所有，转载或翻印必究 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) 北京大学信息学院 ©版权所有，转载或翻印必究 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 ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ 北京大学信息学院 ©版权所有，转载或翻印必究 Page 23 A4= 3 15 3 4 4 0 0 0 0 0 0 0 0 6 15 6 ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ 北京大学信息学院 ©版权所有，转载或翻印必究 Page 24 6.3.2 图的邻接表 （adjacency list）表示法 G6 G7