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 有向图及其生成森林