1、 连通网络的连通网络的最小代价最小代价问题问题第第6 6章章 图图(3)(3)设设G=(VG=(V，E)E)是一个连通是一个连通网络，网络，U U是顶点集是顶点集V V的一个非空子集。若的一个非空子集。若(u(u，v)v)是一条具有最小权值是一条具有最小权值(代价代价)的边的边，其中，其中uUuU，vV-UvV-U，则必存在一棵包，则必存在一棵包含边含边(u(u，v)v)的最小生成树。的最小生成树。(证明略证明略)图的应用图的应用 通信网问题。图的顶点之间的边上的权值表示相应的代价，对通信网问题。图的顶点之间的边上的权值表示相应的代价，对于于n n个顶点的连通图可以建立许多不同的个顶点的连通图
2、可以建立许多不同的生成树生成树。一棵生成树的代价就是树上各边的一棵生成树的代价就是树上各边的代价之和代价之和。各边各边代价之和代价之和最小的那棵生成树称为该连通网的最小的那棵生成树称为该连通网的最小代价生成最小代价生成树树，简称为，简称为最小生成树最小生成树。2 2、求解最小生成树的基础、求解最小生成树的基础 MST MST性质：性质：uvUVUTKSTKS4 47:42 普里姆普里姆(Prim)(Prim)算法和算法和克鲁斯卡尔克鲁斯卡尔(Kruskal(Kruskal)算法是两个利用算法是两个利用MST MST 性质构造最小生成树的算法。性质构造最小生成树的算法。3 3、普里姆算法、普里姆
3、算法(1)(1)算法思想算法思想 从连通网络从连通网络 N N=V V,E E 中的某中的某一顶点一顶点V(T)=V(T)=u u0 0 出发，选择与它关出发，选择与它关联的具有最小权值的边联的具有最小权值的边(u u0 0,v v)，将其，将其 以后每一步从一个顶点在以后每一步从一个顶点在V(T)V(T)中，而另一个顶点不在中，而另一个顶点不在V(T)V(T)中的中的各条边中选择权值最小的边各条边中选择权值最小的边(u u，v v),),把它的顶点把它的顶点v v加入到集合加入到集合V(T)V(T)中中，将其边，将其边(u u,v v)加入到生成树的边集合加入到生成树的边集合E(T)E(T)
4、中。中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合合V(T)V(T)中为止中为止(直到直到V(T)V(T)满满n n个顶点为止个顶点为止)。顶点顶点v v加入到生成树的顶点集合加入到生成树的顶点集合V(T)V(T)中，中，V(T)V(T)TKSTKS5 57:42(2)(2)算法步骤算法步骤(构造过程构造过程)假设假设N=(VN=(V，E)E)是连通网，是连通网，TETE是是N N上最小生成树中边的集合。上最小生成树中边的集合。U=u0(u0V)U=u0(u0V)，TE=TE=。在所有在所有uUuU，vVvV-U-U的边的边(
5、u(u，v)Ev)E中找一条权值最小的边中找一条权值最小的边(u0(u0，v0)v0)并入集合并入集合TETE，同时，同时v0v0并入并入U U。重复重复，直至，直至U=VU=V为止。为止。此时此时TETE中必有中必有n-ln-l条边，则条边，则T=(VT=(V，TE)TE)为为N N的最小生成树。的最小生成树。示例示例1 1：v v1 1v v2 2v v3 3v v4 4v v5 5v v6 63 35 55 52 24 46 61 15 56 66 6 v v5 5 v v1 1 v v2 2 v v3 3 v v4 4 v v6 6 v v1 1v v2 2v v3 3v v4 4v
6、v5 5v v6 610105 56 66 66 610107 7121210101515 v v5 5 v v1 1 v v2 2 v v3 3 v v4 4 v v6 6 示例示例2 2：TKSTKS6 67:42(3)(3)普里姆算法的实现普里姆算法的实现 邻接矩阵结构邻接矩阵结构 typedef structtypedef struct char vexsmvnum char vexsmvnum;int arcsmvnummvnum int arcsmvnummvnum;int vexnum,arcnum int vexnum,arcnum;amgraph amgraph;记录前驱顶点
7、和记录前驱顶点和V(T)V(T)中到中到V-V-V(T)V(T)权值最小的边的存储空间权值最小的边的存储空间structstruct int adjvex int adjvex；int lowcostint lowcost；closedgenvnum closedgenvnum；算法实现算法实现 初始化：初始化：首先将初始顶点甜加入首先将初始顶点甜加入U U中，对其余的每一个顶点中，对其余的每一个顶点v vi i，将将closedgeiclosedgei 均初始化为到均初始化为到u u的边信息。的边信息。循环循环n-ln-l次，做加下处理：次，做加下处理：a a、从各组最小边从各组最小边clo
8、sedgevclosedgev 中选出最小的最小边中选出最小的最小边closedgekclosedgek，输出此边输出此边(v(v，k kV V-U)-U)；b b、将将k k加入加入U U中；中；c c、更新剩余的每组最小边信息更新剩余的每组最小边信息closedgevclosedgev，(v(vV V-U)-U)。TKSTKS7 77:42 v v1 1v v2 2v v3 3v v4 4v v5 5v v6 610105 56 66 66 610107 7121210101515lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex
9、 lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex lowcostlowcost adjvexadjvex k k V-T(V)V-T(V)T(V)T(V)V V6 6V V5 5V V4 4V V3 3V V2 2 V V closedgeclosedge v v5 5 v v1 1 1 1 V V2 2V V3 3V V4 4V V5 5V V6 6 VV1 1 121215151010V V1 1V V1 1V V1 1 2 2 V V3 3V V4 4V V5 5V V
10、6 6 VV1 1V V2 2 V V2 2V V1 1V V2 2V V2 2 v v2 2 7 715156 65 50 03 3 v v3 3 V V4 4V V5 5V V6 6 VV1 1V V2 2V V3 3 7 715156 60 00 0V V2 2V V1 1V V2 24 4 v v4 4 V V5 5V V6 6 VV1 1V V2 2V V3 3V V4 4 6 610100 00 00 0V V4 4V V4 46 6 v v6 6 V V5 5 VV1 1V V2 2V V3 3V V4 4V V6 6 0 010100 00 00 0V V4 45 5 VV1
11、1V V2 2V V3 3V V4 4V V6 6V V5 5 0 00 00 00 00 0 示例示例v v1 1v v2 2v v3 3v v4 4v v5 5v v6 610105 56 66 66 610107 7121210101515 生成树可生成树可能不唯一能不唯一TKSTKS8 87:42 算法描述算法描述void minispantree_prim(amgraph g,charvoid minispantree_prim(amgraph g,char u)u)/普里姆算法普里姆算法 struct struct int adjvex int adjvex;int lowcost
12、 int lowcost;closedgemvnum closedgemvnum;int i,j,k,min int i,j,k,min;k=locatevex(g,u,g.vexnum k=locatevex(g,u,g.vexnum););/初始化初始化 for(j=0;jg.vexnum;jfor(j=0;jg.vexnum;j+)+)if(j if(j!=k)!=k)closedgej.adjvex closedgej.adjvex=k;=k;closedgej.lowcost=g.arcskj closedgej.lowcost=g.arcskj;closedgek.lowcost
13、closedgek.lowcost=0;=0;TKSTKS9 97:42 for(i=1;ig.vexnum;i for(i=1;ig.vexnum;i+)+)/重复重复n-1n-1次做次做 min=maxint min=maxint;for(j=0;jg.vexnum;j for(j=0;j0&closedgej.lowcost0&closedgej.lowcost%c ,g.vexsclosedgek.adjvex printf(%c-%2d-%c ,g.vexsclosedgek.adjvex,closedgek.lowcost,g.vexsk closedgek.lowcost,g.v
14、exsk););/输出输出 closedgek.lowcostclosedgek.lowcost=0;=0;/把顶点把顶点vexskvexsk 加入到加入到T T for(j=0;jg.vexnum;j for(j=0;jg.vexnum;j+)+)/调整调整if(g.arcskjclosedgej.lowcostif(g.arcskjclosedgej.lowcost)closedgej.adjvex closedgej.adjvex=k;=k;closedgej.lowcost=g.arcskj closedgej.lowcost=g.arcskj;getchgetch();();TKST
15、KS 10107:42 算法分析算法分析 时间复杂度：时间复杂度：4 4、克鲁斯卡尔算法克鲁斯卡尔算法(1)(1)克鲁斯卡尔算法的构造过程克鲁斯卡尔算法的构造过程 10101110)1()1()1(njnjninjOOO)()1()1)(12()1(2)1(21011nOOnnOnOnjniTKSTKS 11117:42 即即(算法步骤算法步骤)(2)(2)示例示例v v1 1v v2 2v v3 3v v4 4v v5 5v v6 610105 56 66 66 610107 7121210101515v v1 1v v2 2v v3 3v v4 4v v5 5v v6 610105 56
16、66 66 610107 71212101015155 56 66 610101010 生成树可能生成树可能不唯一不唯一TKSTKS 12127:42(3)(3)克鲁斯卡尔算法的实现克鲁斯卡尔算法的实现 辅助数据结构辅助数据结构 存储边信息的结构体存储边信息的结构体(数组数组 edge)edge)struct edgenode struct edgenode int int head;/head;/边的始点边的始点 intint tail;/tail;/边的终点边的终点 int lowcostint lowcost;/;/边上的权值边上的权值 ;标识各顶点连通分量数组标识各顶点连通分量数组 v
17、exsetarcnumvexsetarcnum 对每个顶点对每个顶点viVviV，对应元素，对应元素vexsetivexseti 表示该顶点所在的连通表示该顶点所在的连通分量。初始时：分量。初始时：vexsetivexseti=i=i，表示各顶点自成一个连通分量。表示各顶点自成一个连通分量。TKSTKS 13137:42 算法思想算法思想 将边信息数组将边信息数组edgeedge中的元素按权值从小到大排序。中的元素按权值从小到大排序。依次从排好序的数组依次从排好序的数组edgeedge中选出一条边中选出一条边(v(vl l，v v2 2)，在，在vexsetvexset中中分别查找分别查找v
18、vl l和和v v2 2所在的连通分量所在的连通分量VSVS1 1和和VSVS2 2。若若VSVS1 1和和VSVS2 2不等，表明所选的两个顶点分属不同的连通分量，不等，表明所选的两个顶点分属不同的连通分量，输出此边，并合并输出此边，并合并VSVS1 1和和VSVS2 2两个连通分量；两个连通分量；若若VSVS1 1和和VSVS2 2 相等，表明所选的两个顶点属于同一个连通分量，相等，表明所选的两个顶点属于同一个连通分量，舍去此边而选择下一条权值最小的边。舍去此边而选择下一条权值最小的边。重复重复(n-1(n-1次次)，直至，直至edgeedge中所有的边都扫描判断完，并且所中所有的边都扫描
19、判断完，并且所有顶点都在同一连通分量上。有顶点都在同一连通分量上。算法描述算法描述void minispantree_kruskal(amgraphvoid minispantree_kruskal(amgraph g)g)int i,j,v1,v2,vs1,vs2,int i,j,v1,v2,vs1,vs2,*vexsetvexset;vexset=new intg.vexnum vexset=new intg.vexnum;TKSTKS 14147:42 sort(g sort(g););for(i=0;ig.vexnum;i+)vexseti for(i=0;ig.vexnum;i+)v
20、exseti=i;=i;for(i=0;ig.arcnum;i for(i=0;i%c ,g.vexsv1,printf(%c-%2d-%c ,g.vexsv1,g.edgei.lowcost,g.vexsv2);g.edgei.lowcost,g.vexsv2);for(j=0;jg.vexnum;jfor(j=0;jg.vexnum;j+)+)if(vexsetj=vs2)vexsetj if(vexsetj=vs2)vexsetj=vs1;=vs1;TKSTKS 15157:42 算法分析算法分析 时间复杂度：时间复杂度：(n(ne)e)(e(elogeloge)(4)(4)比较两种算法比较比较两种算法比较 算法名算法名 普里姆算法普里姆算法 克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度 (n(n2 2)(n(ne)e)适应范围适应范围 稠密图稠密图 稀疏图稀疏图？1 1、书面作业：、书面作业：P161P161：2 2中中(1)(1)、(2)(2)、(3)(3)2 2、实践：、实践：实验二、栈序列匹配实验二、栈序列匹配TKSTKS 16167:42
