树与图的生成树

1、信息学院信息技术教研室 Vs Vt V2V4 V3V1 2 4 8 4 2 7 9 1 4 6 V1 V8 V9V10 V7 V4V3 V6 V5 V2 王桂平王桂平 第第3 3章章 树与图的生成树树与图的生成树 2 例1 下图所示的网络代表6个城市间的交通网，边上权是公 路的造价，现在要用公路把6个城市联系起来，这要修 筑5条公路，如何设计使得这5条公路总的造价最小。 1 5 6 2 4 3 16 19 21 23 18 14 11 6 5 6 3 1 生成树 ：连通图G的一个子图如果是一棵包含G的所 有顶点的树，则该子图称为G的。 用不同的遍历图的方法，可以得到不同的生成树；从 不同的顶点

2、出发，也可能得到不同的生成树。 生成树是连通图的。所谓是指： ； 按照生成树的定义， 个顶点的连通网络的生成树有 个顶点、 条边。 4 最小生成树(MST, Minimum Spannirng Tree) ：生成树各边的权值总和称为生成树的 权，权最小的生成树称为最小生成树。 构造最小生成树的准则： 1. 必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树； 2. 必须使用且仅使用必须使用且仅使用 n-1 条边来联结网络中的条边来联结网络中的 n 个顶个顶 点；点； 3. 不能使用产生回路的边。不能使用产生回路的边。 构造最小生成树的方法：算法 和算法。都得遵守以上

3、准则。 5 2 克鲁斯卡尔算法 先看例子。 克鲁斯卡尔算法的基本思想( )： 1. 设有一个有设有一个有 n 个顶点的连通网络个顶点的连通网络 N = V, E ，最初，最初 先构造一个只有先构造一个只有 n 个顶点，没有边的非连通图个顶点，没有边的非连通图 T = V, , 图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。 2. 当在当在 E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边的两若该边的两 个顶点落在不同的连通分量上个顶点落在不同的连通分量上，则将此边加入到，则将此边加入到 T 中；否则将此边舍去，重新选择一条权值最小的边。中；否则将此边舍去，重新

4、选择一条权值最小的边。 3. 如此重复下去，直到所有顶点在同一个连通分量上如此重复下去，直到所有顶点在同一个连通分量上 为止。为止。 6 7 0 562 34 28 1 10 25 24 22 18 12 1614 0 562 34 1 10 25 22 12 1614 0241814 02510 2425022 1822012 12016 1416028 10280 8 在在Kruskal算法里要用到算法里要用到(MinHeap)和和 (DisjointSets)。 用来存放用来存放E中所有的边。中所有的边。 用来检查依附于用来检查依附于1条边的条边的2个顶点是否在同一个个顶点是否在同一个

5、连同分量上。连同分量上。 9 为简化起见，本算法中不使用为简化起见，本算法中不使用和和，分别使用，分别使用 和和来替代并查集和最小堆，并且可以很好地来替代并查集和最小堆，并且可以很好地 体现算法的思想。体现算法的思想。 VerUnionVerNum： 1) 其中的元素值相同的话，表示在其中的元素值相同的话，表示在上，初上，初 始时，每个元素的值为其下标，即每个顶点始时，每个元素的值为其下标，即每个顶点 。 2) 在最小生成树产生过程中，如果查找到的权值最小的边在最小生成树产生过程中，如果查找到的权值最小的边 的两个顶点在同一个连通分量（元素值相同），则要的两个顶点在同一个连通分量（元素值相同）

6、，则要 ，如果不在同一个连同分量上，则要把这条边，如果不在同一个连同分量上，则要把这条边 加进来，并把加进来，并把设为相同。设为相同。 10 AdjUnionAdjNum4： 1) 二维数组中的每个元素的二维数组中的每个元素的4个分量分别为标志个分量分别为标志F、每条边、每条边 的起点的起点i、终点、终点j、权值、权值w。 2) 标志位初始值为标志位初始值为0，表示边没有加入到生成树中，初始，表示边没有加入到生成树中，初始 时边的集合为空集。时边的集合为空集。 3) 标志位的修改，当查找到权值最小的边，并且这条边的标志位的修改，当查找到权值最小的边，并且这条边的 2个顶点不在同一个连通分量上，

7、则修改对应的标志位个顶点不在同一个连通分量上，则修改对应的标志位 为为1，如果在同一个连通分量上，则这条边要舍去，对，如果在同一个连通分量上，则这条边要舍去，对 应的标志位设为应的标志位设为-1。 00128 Fijw 11 本算法思想 1.先在二维数组AdjUnion里查找到权值最小的边（标志位 为1和-1的不予考虑） 2.检查这条边的2个顶点i和j是不是在同一个连通分量上 （在一维数组VerUnion里通过判断这条边的2个顶点为下 标的元素值是否相同），如果在同一个连同分量上，则 舍去（在AdjUnion将这条边的标志置为-1），如果不在的 话，执行下列操作： 1) 输出这条边输出这条边;

8、 2) 将标志位置为将标志位置为1; 3) 在在VerUnion数组中将以数组中将以顶点顶点j所在的连通分量的每所在的连通分量的每 个顶点个顶点为下标的元素值设为为下标的元素值设为VerUnioni; 3.重复执行1、2步，直至最小生成树中的边数为VerNum-1 12 00128 00510 01216 01614 02312 03422 03618 04525 04624 0123456 0123456Fijw 00128 10510 01216 01614 02312 03422 03618 04525 04624 0123406 0122406 0122401 0111401 0111

9、101 0000000 . . . 0 562 34 1 10 25 22 12 1614 AdjUnionVerUnion #define MAX_VER_NUM 10/顶点个数最大值顶点个数最大值 #define MAX 10000 int VerNum;/顶点个数顶点个数 int AdjNum;/边的个数边的个数 int Edge MAX_VER_NUM MAX_VER_NUM ;/图的邻接矩阵图的邻接矩阵 void Kruskal( ) /假设图的邻接矩阵、顶点个数、边的个数这些信息已经读进来了假设图的邻接矩阵、顶点个数、边的个数这些信息已经读进来了 int* VerUnion = n

10、ew intVerNum; int (*AdjUnion)4 = new intAdjNum4; for(int i=0; iVerNum; i+) VerUnioni=i;/构造顶点数组构造顶点数组,值相同表示在同一个连通分量上值相同表示在同一个连通分量上 int j=0, k=0; for(i=0; iVerNum-1; i+) /构造边的数组构造边的数组 for(j=i+1; jVerNum; j+) if(G.AdjMatrixijMAX) /0:边还未检测过边还未检测过,1:边已经加进来了边已经加进来了-1:检测过但因为在同一个连通分量上，被舍去了检测过但因为在同一个连通分量上，被舍

11、去了 AdjUnionk0=0; AdjUnionk1=i; AdjUnionk2=j; AdjUnionk3=G.AdjMatrixij; k+; j=0; int count=0; while(countVerNum-1) int min=MAX; for(k=0;kAdjNum;k+) /找到权值最小的边找到权值最小的边AdjUnionj; if(AdjUnionk0=0 j=k; /判断判断AdjUnionj这条边的这条边的2个顶点是不是在同一个连通分量上个顶点是不是在同一个连通分量上 if(VerUnion AdjUnionj1 !=VerUnion AdjUnionj2 ) /如果

12、不是如果不是,输出来输出来,设置标志位设置标志位 /重新设置在同一个连通分量上的顶点的标记值重新设置在同一个连通分量上的顶点的标记值 cout AdjUnionj1 AdjUnionj2 AdjUnionj3 endl; AdjUnionj0=1; int tmp=VerUnion AdjUnionj2 ; for(k=0; kVerNum; k+) if(VerUnionk=tmp) VerUnionk=VerUnion AdjUnionj1 ; count+; else AdjUnionj0=-1; /如果是，舍去，重来如果是，舍去，重来 (1) (2) 15 整个算法的时间复杂性是整个算

13、法的时间复杂性是O(n2) 16 3 普里姆算法 先看例子。 普里姆算法的( ) ： 1. 从连通网络从连通网络 N = V, E 中的某一顶点中的某一顶点 u0出发，选择出发，选择 与它关联的具有最小权值的边与它关联的具有最小权值的边(u0, v)，将其顶点加入，将其顶点加入 到生成树的顶点集合到生成树的顶点集合U中。中。 2. 以后每一步从一个顶点在以后每一步从一个顶点在U中，而另一个顶点不在中，而另一个顶点不在U 中的各条边中选择权值最小的边中的各条边中选择权值最小的边(u, v),把它的顶点加把它的顶点加 入到集合入到集合U中。如此继续下去，直到网络中的所有顶中。如此继续下去，直到网络

14、中的所有顶 点都加入到生成树顶点集合点都加入到生成树顶点集合U中为止。中为止。 17 0 562 34 28 1 10 25 24 22 18 12 1614 0 5 10 4 25 3 22 2 12 1 16 6 14 在Prim算法运算过程当中，需要知道哪些 信息？1.V集合内各顶点距离U内权值最小 的边的权值；2. V集合内各顶点距离U内 哪个顶点最近(权值最小)。 U：当前生成树顶点集合， V：不属于当前生成树的顶点集合。 18 采用采用来存储图。为了实现上述思想，必须定义来存储图。为了实现上述思想，必须定义2个个 辅助数组：辅助数组： 存放顶点集合存放顶点集合 ()内的各顶点到顶点

15、集合内的各顶点到顶点集合 U(生成树顶点集合生成树顶点集合)内的权值最小的边的权值。内的权值最小的边的权值。 记录顶点集合记录顶点集合 ()内的各顶点距离顶点集合内的各顶点距离顶点集合 ()内内哪个顶点哪个顶点最近（权值最小）。最近（权值最小）。 从顶点从顶点0出发，出发，2个辅助数组的初始状态为：个辅助数组的初始状态为： 0 28 10 lowcost 0123456 -1 000000nearvex 0123456 V=5 选边选边(0,5) 因为在生成树顶点集合内最初只有一个顶点因为在生成树顶点集合内最初只有一个顶点0，因此在，因此在nearvex 数组中，只有表示顶点数组中，只有表示顶

16、点0的数组元素的数组元素nearvex0=-1，其他都是，其他都是0，表，表 示集合外各顶点距离集合内最近的顶点是示集合外各顶点距离集合内最近的顶点是0。 数组数组lowcost表示生成树顶点集合（目前只有顶点表示生成树顶点集合（目前只有顶点0）顶点到生）顶点到生 成树外各顶点的边的最小权值。初始值为邻接矩阵中顶点成树外各顶点的边的最小权值。初始值为邻接矩阵中顶点0所在的行。所在的行。 19 在在prim算法里要重复做以下工作算法里要重复做以下工作()： 。 。 。 。 20 在在prim算法里要重复做以下工作算法里要重复做以下工作()： 。则选中的权值最小的边为。则选中的权值最小的边为(ne

17、arvexv,v)，相应的权值为，相应的权值为 lowcostv。如第一次选中的。如第一次选中的v=5，则边，则边(0,5)是选中的权值最小的是选中的权值最小的 边，相应的权值为边，相应的权值为lowcost5=10。 ，将，将 边边(nearvexv, v, lowcostv)输出来。输出来。 ：注意，原来顶点注意，原来顶点v不属于生成树顶点集合，现在不属于生成树顶点集合，现在 v加入进来了，则加入进来了，则顶点集合顶点集合V(生成树外生成树外)内的各顶点到顶点集合内的各顶点到顶点集合 U(生成树顶点集合生成树顶点集合)内的权值最小的边的权值内的权值最小的边的权值 lowcosti=minl

18、owcosti, Edgevi，即用，即用V集合内各顶点集合内各顶点i到到 加入集合加入集合U的新顶点的新顶点v的距离的距离(Edgevi)与原来它们到集合与原来它们到集合U中顶中顶 点的最短距离点的最短距离(lowcosti)做比较，取距离近的，作为这些集合外做比较，取距离近的，作为这些集合外 顶点到生成树顶点集合内顶点的最短距离。顶点到生成树顶点集合内顶点的最短距离。 ：如果顶点集合：如果顶点集合V内顶点内顶点i到顶点到顶点v的距离比原来它的距离比原来它 到顶点集合到顶点集合U中顶点的最短距离还要近，则修改中顶点的最短距离还要近，则修改nearvexi： nearvexi=v；表示生成树外

19、顶点；表示生成树外顶点i到生成树内顶点到生成树内顶点v当前距离最当前距离最 近。近。 21 0241814 02510 2425022 1822012 12016 1416028 10280 0 562 34 28 1 10 25 24 22 18 12 1614 0 28 25 10 lowcost-1 0005 -1 0nearvexV=4, 选边选边(5,4) 0 28 22 25 10 24 lowcost-1 004 -1 -1 4nearvexV=3, 选边选边(4,3) 0 28 12 22 25 10 18 lowcost-1 03 -1 -1 -1 3nearvexV=2,

20、选边选边(3,2) 0 16 12 22 25 10 18 lowcost-1 2 -1 -1 -1 -1 3nearvexV=1, 选边选边(2,1) 0 16 12 22 25 10 14 lowcost-1 -1 -1 -1 -1 -1 1nearvexV=6, 选边选边(1,6) 0 16 12 22 25 10 14 lowcost-1 -1 -1 -1 -1 -1 -1nearvex 0 28 10 lowcost 0123456 -1 000000nearvex 0123456 V=5, 选边选边(0,5) 深色背景：深色背景：U内的顶点内的顶点 粗体粗体被修改的值被修改的值 0

21、 562 34 28 1 10 25 24 22 18 12 1614 0 5 10 4 25 3 22 2 12 1 16 6 14 白色背景：白色背景：V中的顶点中的顶点 浅色背景：浅色背景：V中将被选择的顶点中将被选择的顶点 23 #define MAX 100000 #define MAX_VER_NUM 10/顶点个数最大值顶点个数最大值 int Edge MAX_VER_NUM MAX_VER_NUM ; /邻接矩阵邻接矩阵 int vernum;/顶点个数顶点个数 /假设邻接矩阵和顶点个数已经读进来了假设邻接矩阵和顶点个数已经读进来了 void Prim( ) int* lowcost = new intvernum; int* nearvex = new intvernum; for(int i=0; iverNum; i+) lowcosti = Edge0i; nearvexi=0; nearvex0 = -1; for(i=1; iverNum; i+)