61图的基本概念(续) ■连通分支或者连通分量( connected component) 无向图的最大连通子图 ■强连通分支(强连通分量) 网络 带权的连通图。 m自由树( free tree 不带有简单回路的无向图,它是连通的, 并且真有v|-1条边。 北京大学信息学院 版权所有,转载或翻印必究 Page 11
北京大学信息学院 ©版权所有，转载或翻印必究 Page 11 6.1 图的基本概念（续） ◼ 连通分支或者连通分量（connected component） ◼ 无向图的最大连通子图。 ◼ 强连通分支（强连通分量）。 ◼ 网络 ◼ 带权的连通图。 ◼ 自由树（free tree） ◼ 不带有简单回路的无向图，它是连通的， 并且具有|V|-1条边
62图的抽象数据类型 class Grapht //图的ADT public: int VerticesNum(;//返回图的顶点个数 int EdgesNum(∥/返回图的边数 /返回与顶点 onevertex相关联的第一条边 Edge FirstEdge(int oneVertex); //返回与边 PreEdge有相同关联顶点 onevertex的 /下一条边 Edge Nextedge( edge preedge); 北京大学信息学院 版权所有,转载或翻印必究 Page 12
北京大学信息学院 ©版权所有，转载或翻印必究 Page 12 6.2 图的抽象数据类型 class Graph{ //图的ADT public: int VerticesNum(); //返回图的顶点个数 int EdgesNum(); //返回图的边数 //返回与顶点oneVertex相关联的第一条边 Edge FirstEdge(int oneVertex); //返回与边PreEdge有相同关联顶点oneVertex的 //下一条边 Edge NextEdge(Edge preEdge);
62图的抽象数据类型(续) //添加一条边 bool setEdge(int fromvertex int tovertexint weight)i //删一条边 bool deleage(int fromVertex, int toVertex); //如果 one Edge是边则返回TRUE,否则返回 FALSE bool IsEdge(Edge oneEdge)i 北京大学信息学院 版权所有,转载或翻印必究 Page 13
北京大学信息学院 ©版权所有，转载或翻印必究 Page 13 6.2 图的抽象数据类型（续） //添加一条边 bool setEdge(int fromVertex,int toVertex,int weight); //删一条边 bool delEdge(int fromVertex,int toVertex); //如果oneEdge是边则返回TRUE，否则返回 FALSE bool IsEdge(Edge oneEdge);
62图的抽象数据类型(续) /返回边 oneedge的始点 int FromVertex (Edge one edge) //返回边 one Edge的终点 int ToVertex(Edge oneEdge)i //返回边 oneEdge的权 int Weight(Edge oneEdge); 北京大学信息学院 版权所有,转载或翻印必究 Page 14
北京大学信息学院 ©版权所有，转载或翻印必究 Page 14 6.2 图的抽象数据类型（续） //返回边oneEdge的始点 int FromVertex(Edge oneEdge); //返回边oneEdge的终点 int ToVertex(Edge oneEdge); //返回边oneEdge的权 int Weight(Edge oneEdge); };
63图的存储结构 631图的相邻矩阵 ( adjacency matrix)表示法 632图的邻接表( adjacency ist)表示法 邻接多重表( adjacency multilist 表示法 北京大学信息学院 版权所有,转载或翻印必究 Page 15
北京大学信息学院 ©版权所有，转载或翻印必究 Page 15 6.3 图的存储结构 ◼ 6.3.1 图的相邻矩阵 （adjacency matrix）表示法 ◼ 6.3.2 图的邻接表（adjacency list）表示法 ◼ 邻接多重表(adjacency multilist) 表示法