图最小生成树

1第九讲1、图的基本概念复习2、最小生成树23最小生成树1.生成树在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G′称做图G的生成树。一个图可以有多个生成树，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边也就不同，例如图7-12的(b)和(c)为图7-12(a)的两棵生成树。其中(b)是通过DFS得到的，称为深度优先生成树；(c)是通过BFS得到的，称为广度优先生成树。17823456(a)17823456(b)17823456(c)图7-12生成树4按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。而所有包含n-1条边及n个顶点的连通图都是无回路的树，所以生成树是连通图中的极小连通子图.由于使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。5假设把n个城市看作图的n个顶点，边表示两个城市之间的线路，每条边上的权值表示铺设该线路所需造价。铺设线路连接n个城市，但不形成回路，这实际上就是图的生成树，而以最少的线路铺设造价连接各个城市，即求线路铺设造价最优问题，实际上就是在图的生成树中选择权值之和最小的生成树。构造最小生成树的算法有很多，下面分别介绍克鲁斯卡尔(Kruskal)算法和普里姆(Prim)算法。克鲁斯卡尔(Kruskal)算法克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的方法。6假设G=（V，E）是一个具有n个顶点的带权无向连通图，T=(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造最小生成树的过程如下：(1)置U的初值等于V，TE的初值为空集；7(2)按权值从小到大的顺序依次选取图G中的边，若选取的边未使生成树T形成回路，则加入TE；若选取的边使生成树T形成回路，则将其舍弃。循环执行(2)，直到TE中包含(n-1)条边为止。8应用克鲁斯卡尔算法构造最小生成树的过程:910普里姆(Prim)算法普里姆算法的基本思想：普里姆算法是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最小生成树的。11从连通网络N={V,E}中的某一顶点u0出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把该边加入到生成树的边集TE中，把它的顶点加入到集合U中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合U中为止。12假设G=(V，E)是一个具有n个顶点的带权无向连通图，T(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造G的最小生成树T的步骤如下：（1）初始状态，TE为空，U={v0}，v0∈V；（2）在所有u∈U，v∈V-U的边(u，v)∈E中找一条代价最小的边(u′，v′)并入TE，同时将v′并入U；重复执行步骤（2）n-1次，直到U=V为止。13在普里姆算法中，为了便于在集合U和(V-U)之间选取权值最小的边，需要设置两个辅助数组closest和lowcost，分别用于存放顶点的序号和边的权值。对于每一个顶点v∈V-U，closest[v]为U中距离v最近的一个邻接点，即边(v，closest[v])是在所有与顶点v相邻、且其另一顶点j∈U的边中具有最小权值的边，其最小权值为lowcost[v]，即lowcost[v]=cost[v][closest[v]]，14为实现克鲁斯卡尔算法需要设置一维辅助数组E，按权值从小到大的顺序存放图的边，数组的下标取值从0到e-1（e为图G边的数目）。假设数组E存放图G中的所有边，且边已按权值从小到大的顺序排列。n为图G的顶点个数，e为图G的边数。注：克鲁斯卡尔算法的时间复杂度与边数e有关O(eloge)，该算法适合于求边数较少的带权无向连通图的最小生成树。15应用普里姆算法构造最小生成树的过程:1617采用邻接表作为存储结构：设置一个辅助数组closedge[]：lowcost域：存放在V-U中各个顶点到集合U中的当前最小权值；adjvex域：记录该边所依附的在U中的顶点注：普里姆算法的时间复杂度为O(n2),与网中的边数无关，因此适合于求边稠密的网的最小生成树。181920211.拓扑排序通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图7-21给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学则必须先并行学完高等数学、程序设计基础课程。拓扑排序22课程代号课程名称先修课程Cl高等数学无C2程序语言无C3离散数学C1C4数据结构C2，C3C5编译原理C2，C4C6操作系统C4，C7C7计算机组成原理C2图7-21课程名称及相应的课程安排次序图7-22课程安排的AOV网C1C7C2C5C4C3C6在图7-22中，我们用一种有向图来表示课程开设，在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这有向图叫做顶点表示活动的网络(ActivityOnVertices)简称为AOV网。23AOV网——ActivityOnVertexNetwork用顶点表示活动，用弧表示活动间的优先关系的有向图，称为顶点表示活动的网。AOV网中不能有回路拓扑排序：假设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列vl，v2，…，vn称做一个拓扑序列(TopologicalOrder)，当且仅当该顶点序列满足下列条件：若在有向图G中存在从顶点vi到vj的一条路径，则在顶点序列中顶点vi必须排在顶点vj之前。通常，在AOV网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排序(TopologicalSort)。24由于AOV网中有些活动之间没有次序要求，它们在拓扑序列的位置可以是任意的，因此拓扑排序的结果不唯一。C1C7C2C5C4C3C6对右图进行拓扑排序，可得一个拓扑序列：C1，C3，C2，C4，C7，C6，C5也可得到另一个拓扑序列：C2，C7，C1，C3，C4，C5，C6还可以得到其它的拓扑序列。学生按照任何一个拓扑序列都可以完成所要求的全部课程学习。在AOV网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。判定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。25进行拓扑排序的算法：(1)在AOV网络中选一个没有直接前驱的顶点,并输出之;(2)从图中删去该顶点,同时删去所有它发出的有向边;重复以上(1)、(2)步,直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。26拓扑排序的过程2728最后得到的拓扑有序序列为C4,C0,C3,C2,C1,C5。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。29在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域count，这些表头结点构成一个数组，表头结点定义如下：typedefstruct//表头结点{Vertexdata;//顶点信息intcount;//存放顶点入度ArcNode*firstarc;//指向第一条弧}Vnode;在执行拓扑排序的过程中，当某个顶点的入度为零(没有前驱顶点)时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，相当于删除所有以该顶点为尾的弧。为了避免重复检测顶点的入度是否为零，需要设立一个栈来存放入度为零的顶点。执行拓扑排序的算法如下：30StatusTopologicalSort(ALGraphG){//算法7.12//有向图G采用邻接表存储结构。//若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR。FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1]InitStack(S);for(i=0;iG.vexnum;++i)//建零入度顶点栈Sif(!indegree[i])Push(S,i);//入度为0者进栈count=0;//对输出顶点计数while(!StackEmpty(S)){Pop(S,i);printf(i,G.vertices[i].data);++count;//输出i号顶点并计数for(p=G.vertices[i].firstarc;p;p=p-nextarc){k=p-adjvex;//对i号顶点的每个邻接点的入度减1if(!(--indegree[k]))Push(S,k);//若入度减为0，则入栈}}if(countG.vexnum)returnERROR;//该有向图有回路elsereturnOK;}//TopologicalSort31【例7-3】请给出图7-24所示的有向图G的拓扑排序过程。图7-24有向图G及其邻接矩阵132405160122(b)432624顶点入度指针(a)16543232【解】依据拓扑排序算法，将图7-24中入度为0的两个顶点l和5相继入栈；顶点5出栈，输出，且以顶点5为尾的弧的另一顶点入度减一，如另一顶点2的入度值由2变为1，另一顶点6的入度值由1变为0。将入度为0的顶点6入栈；顶点6出栈，输出，且以顶点6为尾的弧的另一顶点入度减一，如另一顶点4的入度值由2变为1；依次类推得到拓扑序列：561234，拓扑排序过程栈的变化见图7-25。入度为0的顶点可以按不同顺序入栈，因此还可以得到其它拓扑序列：152364，152634，156234，512364，516234，512634。图7-25拓扑排序过程的栈top=11top=12top=13top=11top=216top=14top=0top=21533关键路径如果在有向无环的带权有向图中用有向边表示一个工程中的各项活动(Activity)用边上的权值表示活动的持续时间(Duration)用顶点表示事件(Event)则这样的有向图叫做用边表示活动的网络，简称AOE(ActivityOnEdges)网络。AOE网是一个带权的有向无环图。AOE网络在某些工程估算方面非常有用。例如，可以使人们了解：(1)完成整个工程至少需要多少时间(假设网络中没有环)?(2)为缩短完成工程所需的时间,应当加快哪些活动?34在AOE网络中,有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(CriticalPath)。35图7-26就是一个AOE网，该网中有11个活动和9个事件。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如事件v5表示a4和a5活动已经完成，a7和a8活动可以开始。每个弧上的权值表示完成相应活动所需要的时间，如完成活动a1需要6天