北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第六章 图

自由树( free tree) 不带有简单回路的无向图,它是 连通的,并且具有|V|-1条边 北京大学信息学院 @版权所有,转载或翻印必究 Page 16

北京大学信息学院 ©版权所有，转载或翻印必究 Page 16 自由树（free tree） „ 不带有简单回路的无向图，它是 连通的，并且具有|V|-1条边

62图的抽象数据类型 结点、边怎么表示? 结点:增?、删、査?、改 ■边:增、删、查?、改 V 北京大学信息学院 @版权所有,转载或翻印必究

北京大学信息学院 ©版权所有，转载或翻印必究 Page 17 6.2 图的抽象数据类型 „ 结点、边怎么表示？ „ 结点：增？、删、查?、改 „ 边：增、删、查?、改

class Grapht /图的ADT public: int verticesnum//返回图的顶点个数 int EdgesNum(P∥/返回图的边数 /返回与顶点 onevertex相关联的第一条边 Edge FirstEdge(int one); 返回与边 PreEdge有相同关联顶点 onevertex的 /下一条边 Edge Nextedge( Edge preEdge; 北京大学信息学院 @版权所有,转载或翻印必究 Page 18

北京大学信息学院 ©版权所有，转载或翻印必究 Page 18 class Graph{ //图的ADT public: int VerticesNum(); //返回图的顶点个数 int EdgesNum(); //返回图的边数 //返回与顶点oneVertex相关联的第一条边 Edge FirstEdge(int oneVertex); //返回与边PreEdge有相同关联顶点oneVertex的 //下一条边 Edge NextEdge(Edge preEdge);

//添加一条边 bool setEdge( int fromVertex, int toVertex, int weight); 删一条边 bool deleage(int fromVertex, int tovertex; //如果 one Edge是边则返回TRUE,否则返回 FALSE bool SeDge(edge one Edge; /返回边 oneEdge的始点 int FromVertex(Edge oneEdge)i //返回边 one Edge的终点 int ToVertex(Edge one Edge)i /返回边 one Edge的权 int Weight(Edge one; Si 北京大学信息学院 @版权所有,转载或翻印必究

北京大学信息学院 ©版权所有，转载或翻印必究 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); };

63图的存储结构 631图的相邻矩阵 ( adjacency matrix)表示法 632图的邻接表( adjacency list)表示法 邻接多重表( adjacency multilist 表示法 北京大学信息学院 @版权所有,转载或翻印必究

北京大学信息学院 ©版权所有，转载或翻印必究 Page 20 6.3 图的存储结构 „ 6.3.1 图的相邻矩阵 （adjacency matrix）表示法 „ 6.3.2 图的邻接表（adjacency list）表示法 „ 邻接多重表(adjacency multilist) 表示法