树与图的生成树

1、信息学院信息技术教研室VsVtV2V4V3V12484279146V1V8V9V10V7V4V3V6V5V2王桂平王桂平第第3 3章章 树与图的生成树树与图的生成树2例1下图所示的网络代表6个城市间的交通网，边上权是公路的造价，现在要用公路把6个城市联系起来，这要修筑5条公路，如何设计使得这5条公路总的造价最小。1562431619212318141165631 生成树：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的。用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。生成树是连通图的。所谓是指：；按照生成树的定义， 个顶点的连通网络的生成

2、树有 个顶点、 条边。4最小生成树(MST, Minimum Spannirng Tree)：生成树各边的权值总和称为生成树的权，权最小的生成树称为最小生成树。 构造最小生成树的准则：1. 必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；2. 必须使用且仅使用必须使用且仅使用 n-1 条边来联结网络中的条边来联结网络中的 n 个顶个顶点；点；3. 不能使用产生回路的边。不能使用产生回路的边。 构造最小生成树的方法：算法和算法。都得遵守以上准则。52 克鲁斯卡尔算法 先看例子。 克鲁斯卡尔算法的基本思想()：1. 设有一个有设有一个有 n 个顶点的连通网络个顶点的

3、连通网络 N = V, E ，最初，最初先构造一个只有先构造一个只有 n 个顶点，没有边的非连通图个顶点，没有边的非连通图 T = V, , 图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。2. 当在当在 E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边的两若该边的两个顶点落在不同的连通分量上个顶点落在不同的连通分量上，则将此边加入到，则将此边加入到 T 中；否则将此边舍去，重新选择一条权值最小的边。中；否则将此边舍去，重新选择一条权值最小的边。3. 如此重复下去，直到所有顶点在同一个连通分量上如此重复下去，直到所有顶点在同一个连通分量上为止。为止。670562

4、342811025242218121614056234110252212161402418140251024250221822012120161416028102808在在Kruskal算法里要用到算法里要用到(MinHeap)和和(DisjointSets)。用来存放用来存放E中所有的边。中所有的边。用来检查依附于用来检查依附于1条边的条边的2个顶点是否在同一个个顶点是否在同一个连同分量上。连同分量上。9为简化起见，本算法中不使用为简化起见，本算法中不使用和和，分别使用，分别使用和和来替代并查集和最小堆，并且可以很好地来替代并查集和最小堆，并且可以很好地体现算法的思想。体现算法的思想。Ver

5、UnionVerNum：1) 其中的元素值相同的话，表示在其中的元素值相同的话，表示在上，初上，初始时，每个元素的值为其下标，即每个顶点始时，每个元素的值为其下标，即每个顶点。2) 在最小生成树产生过程中，如果查找到的权值最小的边在最小生成树产生过程中，如果查找到的权值最小的边的两个顶点在同一个连通分量（元素值相同），则要的两个顶点在同一个连通分量（元素值相同），则要，如果不在同一个连同分量上，则要把这条边，如果不在同一个连同分量上，则要把这条边加进来，并把加进来，并把设为相同。设为相同。10AdjUnionAdjNum4：1) 二维数组中的每个元素的二维数组中的每个元素的4个分量分别为标志个

6、分量分别为标志F、每条边、每条边的起点的起点i、终点、终点j、权值、权值w。2) 标志位初始值为标志位初始值为0，表示边没有加入到生成树中，初始，表示边没有加入到生成树中，初始时边的集合为空集。时边的集合为空集。3) 标志位的修改，当查找到权值最小的边，并且这条边的标志位的修改，当查找到权值最小的边，并且这条边的2个顶点不在同一个连通分量上，则修改对应的标志位个顶点不在同一个连通分量上，则修改对应的标志位为为1，如果在同一个连通分量上，则这条边要舍去，对，如果在同一个连通分量上，则这条边要舍去，对应的标志位设为应的标志位设为-1。00128Fijw11本算法思想1.先在二维数组AdjUnion

7、里查找到权值最小的边（标志位为1和-1的不予考虑）2.检查这条边的2个顶点i和j是不是在同一个连通分量上（在一维数组VerUnion里通过判断这条边的2个顶点为下标的元素值是否相同），如果在同一个连同分量上，则舍去（在AdjUnion将这条边的标志置为-1），如果不在的话，执行下列操作：1) 输出这条边输出这条边;2) 将标志位置为将标志位置为1;3) 在在VerUnion数组中将以数组中将以顶点顶点j所在的连通分量的每所在的连通分量的每个顶点个顶点为下标的元素值设为为下标的元素值设为VerUnioni;3.重复执行1、2步，直至最小生成树中的边数为VerNum-112001280051001

8、21601614023120342203618045250462401234560123456Fijw001281051001216016140231203422036180452504624012340601224060122401011140101111010000000.0562341102522121614AdjUnionVerUnion#define MAX_VER_NUM 10/顶点个数最大值顶点个数最大值#define MAX 10000int VerNum;/顶点个数顶点个数int AdjNum;/边的个数边的个数int Edge MAX_VER_NUM MAX_VER_NUM

9、 ;/图的邻接矩阵图的邻接矩阵void Kruskal( ) /假设图的邻接矩阵、顶点个数、边的个数这些信息已经读进来了假设图的邻接矩阵、顶点个数、边的个数这些信息已经读进来了int* VerUnion = new 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;

10、 j+)if(G.AdjMatrixijMAX)/0:边还未检测过边还未检测过,1:边已经加进来了边已经加进来了-1:检测过但因为在同一个连通分量上，被舍去了检测过但因为在同一个连通分量上，被舍去了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 & AdjUnionk3min) m

11、in=AdjUnionk3; j=k;/判断判断AdjUnionj这条边的这条边的2个顶点是不是在同一个连通分量上个顶点是不是在同一个连通分量上if(VerUnion AdjUnionj1 !=VerUnion AdjUnionj2 )/如果不是如果不是,输出来输出来,设置标志位设置标志位/重新设置在同一个连通分量上的顶点的标记值重新设置在同一个连通分量上的顶点的标记值cout AdjUnionj1 AdjUnionj2 AdjUnionj3 endl;AdjUnionj0=1;int tmp=VerUnion AdjUnionj2 ;for(k=0; kVerNum; k+)if(VerUn

12、ionk=tmp)VerUnionk=VerUnion AdjUnionj1 ;count+;else AdjUnionj0=-1; /如果是，舍去，重来如果是，舍去，重来(1)(2)15整个算法的时间复杂性是整个算法的时间复杂性是O(n2)163 普里姆算法 先看例子。 普里姆算法的() ：1. 从连通网络从连通网络 N = V, E 中的某一顶点中的某一顶点 u0出发，选择出发，选择与它关联的具有最小权值的边与它关联的具有最小权值的边(u0, v)，将其顶点加入，将其顶点加入到生成树的顶点集合到生成树的顶点集合U中。中。2. 以后每一步从一个顶点在以后每一步从一个顶点在U中，而另一个顶点不

13、在中，而另一个顶点不在U中的各条边中选择权值最小的边中的各条边中选择权值最小的边(u, v),把它的顶点加把它的顶点加入到集合入到集合U中。如此继续下去，直到网络中的所有顶中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合点都加入到生成树顶点集合U中为止。中为止。1705623428110252422181216140510425322212116614在Prim算法运算过程当中，需要知道哪些信息？1.V集合内各顶点距离U内权值最小的边的权值；2. V集合内各顶点距离U内哪个顶点最近(权值最小)。U：当前生成树顶点集合，V：不属于当前生成树的顶点集合。18 采用采用来存储图。为了实现

14、上述思想，必须定义来存储图。为了实现上述思想，必须定义2个个辅助数组：辅助数组： 存放顶点集合存放顶点集合 ()内的各顶点到顶点集合内的各顶点到顶点集合U(生成树顶点集合生成树顶点集合)内的权值最小的边的权值。内的权值最小的边的权值。 记录顶点集合记录顶点集合 ()内的各顶点距离顶点集合内的各顶点距离顶点集合()内内哪个顶点哪个顶点最近（权值最小）。最近（权值最小）。 从顶点从顶点0出发，出发，2个辅助数组的初始状态为：个辅助数组的初始状态为：0 28 10 lowcost0123456-1 000000nearvex0123456V=5选边选边(0,5) 因为在生成树顶点集合内最初只有一个顶

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

16、算法里要重复做以下工作()：。则选中的权值最小的边为。则选中的权值最小的边为(nearvexv,v)，相应的权值为，相应的权值为lowcostv。如第一次选中的。如第一次选中的v=5，则边，则边(0,5)是选中的权值最小的是选中的权值最小的边，相应的权值为边，相应的权值为lowcost5=10。，将，将边边(nearvexv, v, lowcostv)输出来。输出来。：注意，原来顶点注意，原来顶点v不属于生成树顶点集合，现在不属于生成树顶点集合，现在v加入进来了，则加入进来了，则顶点集合顶点集合V(生成树外生成树外)内的各顶点到顶点集合内的各顶点到顶点集合U(生成树顶点集合生成树顶点集合)内的

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

18、改nearvexi：nearvexi=v；表示生成树外顶点；表示生成树外顶点i到生成树内顶点到生成树内顶点v当前距离最当前距离最近。近。21024181402510242502218220121201614160281028005623428110252422181216140 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=

19、2, 选边选边(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 -1nearvex0 28 10 lowcost0123456-1 000000nearvex0123456V=5, 选边选边(0,5)深色背景：深色背景：U内的顶点内的顶点粗体粗体被修改的值被修改的值056234281

20、10252422181216140510425322212116614白色背景：白色背景：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+)int min=MAX;int v=0;24for(int j=0