最小生成树生成树和生成森林最小生成树小结和作业生成树一、定义一、定义图图G的生成树是的生成树是G的极小连通子图，即包含的极小连通子图，即包含G中的所有顶点（中的所有顶点（n）和）和n-1条边的连通子图条边的连通子图生成树V1V2V3V4V5V8V6V7V1V2V4V8V5V3V6V7V1V2V3V4V5V8V6V7深度优先：深度优先：广度优先：广度优先：生成树二、算法二、算法图的遍历算法访问了图中的每个顶点一次图的遍历算法访问了图中的每个顶点一次且仅一次。且仅一次。访问某个顶点的邻接点时，要经过与这两访问某个顶点的邻接点时，要经过与这两个顶点相关联的边。个顶点相关联的边。因此，图的遍历算法可以产生一颗生成树：因此，图的遍历算法可以产生一颗生成树：所有的顶点和经过的边。所有的顶点和经过的边。生成树算法void DFSTree(Graph G,int v,CSNode T) =true; first=true; for(w=FirstAdjVex(G,v);w=0; w=NextAdjVex(G,v,w) )p= new CSNode(v);if(first) =p;first=false; else =p;q=p;); SG1SG2SG3Vw1w3w2算法算法以孩子以孩子兄弟链表作兄弟链表作为生成森林为生成森林的存储结构的存储结构生成森林一、定义一、定义 非连通图非连通图G的每个连通分量的生成树，的每个连通分量的生成树，构成了图构成了图G的生成森林的生成森林生成森林abchdekfg812345670812345670abchdekfg非连通图非连通图G：G的深度优先搜索生的深度优先搜索生成森林：成森林：achdfekbg生成森林算法算法算法以孩子以孩子兄弟链表作兄弟链表作为生成森林为生成森林的存储结构的存储结构void DFSForest(Graph G, CSNode T)T=null;for(v=0;v=G.vexnum;+v)=false;for(v=0;v=G.vexnum;+v)p=new CSNode(v)if(!T) T=p;else =p;q=p;DFSTree(G,v,p);最小生成树 假设要在假设要在 n n 个城市之间建立通讯联络个城市之间建立通讯联络网，则连通网，则连通 n n 个城市只需要修建个城市只需要修建 n-1n-1条线条线路，路，如何在最节省如何在最节省经费经费的前提下建立这个通的前提下建立这个通讯网讯网？问题：问题：最小生成树连通网：连通网：n个城市和城市间个城市和城市间可能的通信线路可能的通信线路网的顶点：网的顶点：表示城市表示城市网的边：网的边：表示两个城市之间表示两个城市之间的线路的线路网的边上的权值：网的边上的权值：通信代价通信代价2452710614v4v5v1v3v2v6v7138最小生成树22614v4v5v1v3v2v6v712452710614v4v5v1v3v2v6v7138最小生成树 构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和权值之和”为最小。该问题等价于：特点：1.最小生成树中边的条数为|V|-1。2.最小生成树无圈。3.最小生成树是包含所有顶点的的最小的树。最小生成树算法三：克鲁斯卡尔算法算法三：克鲁斯卡尔算法KruskalKruskal算法二：普里姆算法算法二：普里姆算法PrimPrim算法一：破圈法算法一：破圈法破圈法一、一、基本思想基本思想1、将所有的边按权重从大到小排列。2、对每条边e尝试下面的操作，直到G中的边数=n-1: 如果删除e, 图G仍然是连通图，则从G中删除e 否则，保留e。破圈法v4v5v1v325v2v6v711064724138破圈法abcdegf195141827168213127课堂练习：Prim算法算法思想：使最小生成树连续的一步步成长。在每一步，都要把一个节点当作根并往上加边，这样相关联的顶点就加到增长中的树上。Prim算法 在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。UV-UPrim算法v4v5v1v325v2v6v711064724138v4v5v1v3v2v6v7122416Prim算法v4v5v1v325v2v6v711064724138v4v5v1v3v2v6v7122416vknowndvpvv1v2v3v4v5v6v7FFFFFFF00000000Tv1241Tv4v1v1v12v47v48v44v4Tv2Tv3Tv76v7Tv6Tv55v31v7算法的核心：选择向集合U中加入顶点时，要选择到U具有最短边的顶点。1、对任何一个顶点v，如果它有多个邻接U的边，则需要找出最短的边作为邻接到U的边2、从所有的V U顶点中，找出具有最短边的顶点，将它加入UPrim算法abcdegf195141827168213127abegf14d8c351621Prim算法Kruskal算法具体做法: 先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。abcdegf3abcegfd 21581416Kruskal算法Kruskal算法v4v5v1v325v2v6v711064724138v4v5v1v3v2v6v7112246算法描述算法描述: :构造非连通图构造非连通图 ST=(V, );ST=(V, ); k=i=0; / k k=i=0; / k 选中的边数选中的边数 while (kn-1) while (kn-1) +i; +i; 检查边集检查边集E E中第中第i i条权值最小的边条权值最小的边(u,v);(u,v); if if 若若(u,v)(u,v)加入加入STST后不使后不使STST中产生回路中产生回路， 则输出边则输出边(u,v);(u,v); 且且k+;k+; Kruskal算法两种算法的比较普里姆算法普里姆算法克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名称算法名称适应范围适应范围课堂练习求出图中最小生成树abed8c9244756小结和作业1.普里姆算法普里姆算法2.克鲁斯卡尔算法克鲁斯卡尔算法 3. 两种算法的比较两种算法的比较 2. 最小生成树算法最小生成树算法1.图的生成树和生成森林图的生成树和生成森林作业：作业：P275,9.15,