71图的定义和术语 对于有向图G=<V,E>,若G中任意两个顶点v 和v(内v),都有一条从v到v;的有向路径,同时 还有一条从v到v的有向路径,则称有向图G是强 连通图。有向图强连通的极大子图称为该有向图 的强连通分支或者强连通分量。 图76有向图G2的两个强连通分量 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 对于有向图G = <V，E>，若G中任意两个顶点vi 和vj (vi≠vj )，都有一条从vi到vj的有向路径，同时 还有一条从vj到vi的有向路径，则称有向图G是强 连通图。有向图强连通的极大子图称为该有向图 的强连通分支或者强连通分量。 图7.6 有向图G2的两个强连通分量 v0 v2 v3 v1
71图的定义和术语 个连通图的生成树是含有该连通图全部顶点的一个极小连 通子图。 若连通图G的顶点个数为n,则G的生成树的边数为n-1但是 有n-1条边的图不一定是生成树。如果无向图G的一个生成树 G'上添加一条边,则G中一定有环,因为依附于这条边的两 个顶点有另一条路径。相反,如果G的边数小于n-1,则G一 定不连通。 (a)无向图G1 (b)有向图G2(a)无向图G1的生成树(b)有向图G2的生成树 图7.2图的示例图7.7图7.2中无向图和有向图的生成树示例 “十一五”国家级规划教材。张铭,王腾蛟,赵海,《数据结构与算法》,高教社,2008.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.1 图的定义和术语 ◼ 一个连通图的生成树是含有该连通图全部顶点的一个极小连 通子图。 ◼ 若连通图G的顶点个数为n，则G的生成树的边数为n-1。但是 有n-1条边的图不一定是生成树。如果无向图G的一个生成树 G′上添加一条边，则G′中一定有环，因为依附于这条边的两 个顶点有另一条路径。相反，如果G′的边数小于n-1，则G′一 定不连通。 图7.7 图7.2中无向图和有向图的生成树示例 v0 v2 v3 v1 v4 v0 v2 v1 v3 (a) 无向图G1的生成树 (b) 有向图G2的生成树 图7.2 图的示例 v0 v2 v3 v1 v4 v0 v2 v1 v3 (a) 无向图G1 (b) 有向图G2
7,2图的抽象数据类型 自由树( free tree)是不带简单回路的无向图,它是连通的,并且具有 n-1条边。冈络( network)是带权的连通图,图78中的G4是一个网 络 如果一个有向图只有一个顶点的入度为0,其余顶点的入度均为1, 则称为有向树。一个有向图的生成森林由若干棵有向树组成,这些 树的并集包含了原图所有顶点,各有向树的弧不相交。图79就是有 向图生成森林的示例。 15 (a)有向图 (b)有向图的生成森林 图78网络实例G4 图79有向图及其生成森林 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.2 图的抽象数据类型 ◼ 自由树(free tree)是不带简单回路的无向图，它是连通的，并且具有 n - 1条边。网络(network)是带权的连通图，图7.8中的G4是一个网 络。 ◼ 如果一个有向图只有一个顶点的入度为0，其余顶点的入度均为1， 则称为有向树。一个有向图的生成森林由若干棵有向树组成，这些 树的并集包含了原图所有顶点，各有向树的弧不相交。图7.9就是有 向图生成森林的示例。 v0 v1 v2 v3 3 4 15 6 9 v0 v2 v3 v1 v4 v5 v0 v3 v1 v4 v2 v5 （a）有向图 （b）有向图的生成森林 图7.8 网络实例G4 图7.9 有向图及其生成森林
72图的抽象数据类型 代码71】图的抽象数据类型 class graphi 图的ADT public int VerticesNumO;∥返回图的顶点个数 int edgesnumo;∥返回图的边数 返回与顶点 one Vertex相关联的第一条边 Edge firstEdge(int one vertex); 返回与边 Preedge有相同关联顶点oneⅤ ertex的 下一条边 Edge nextedge (Edge preedge) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.2 图的抽象数据类型 【代码7.1】图的抽象数据类型 class Graph{ //图的ADT public: int VerticesNum(); //返回图的顶点个数 int EdgesNum(); //返回图的边数 //返回与顶点oneVertex相关联的第一条边 Edge FirstEdge(int oneVertex); //返回与边PreEdge有相同关联顶点oneVertex的 //下一条边 Edge NextEdge(Edge preEdge);
7,2图的抽象数据类型 添加一条边 bool setedge(int fromVertex, int to Vertex, int weight) ∥删一条边 bool deleage(int fromVertex, int to Vertex) ∥如果 oneeye是边则返回TRUE,否则返回 FALSE bool is edge(edge oneedge); “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.2 图的抽象数据类型 //添加一条边 bool setEdge(int fromVertex,int toVertex,int weight); //删一条边 bool delEdge(int fromVertex,int toVertex); //如果oneEdge是边则返回TRUE，否则返回FALSE bool IsEdge(Edge oneEdge);