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