《图的连通性问题精.ppt》由会员分享，可在线阅读，更多相关《图的连通性问题精.ppt（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图的连通性问题第1页，本讲稿共16页7.4 图的连通性问题图的连通性问题7.4.1 无向图的连通分量和生成树无向图的连通分量和生成树广度优先生成树广度优先生成树：在连通图中，由广度优先搜索得到的生成树。：在连通图中，由广度优先搜索得到的生成树。（1）连通图）连通图 在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有结点。进行深度优先搜索或广度优先搜索，便可访问到图中所有结点。深度优先生成树深度优先生成树：在连通图中，由深度优先搜索得到的生成树。：在连通图中，由深度优先搜索得到的生
2、成树。（2）非连通图）非连通图 在对无向图进行遍历时，对于非连通图，需从多个顶点出发进行在对无向图进行遍历时，对于非连通图，需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。问序列恰为其各个连通分量中的顶点集。生成森林生成森林：在非连通图中，每个连通分量中的顶点集和遍历时走：在非连通图中，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。的生成森林。深度优先
3、生成森林深度优先生成森林：在非连通图中，由深度优先搜索得到的生成：在非连通图中，由深度优先搜索得到的生成森林。森林。广度优先生成森林广度优先生成森林：在非连通图中，由广度优先搜索得到的生成：在非连通图中，由广度优先搜索得到的生成森林。森林。第2页，本讲稿共16页图图7.11 生成树和生成森林生成树和生成森林A1L2F6C7M3J4B5D8E9G10K11I13H12(c)图图7.3(a)G3的深度优先生成森林的深度优先生成森林(a)无向图无向图G3 G3A BC D E F G H I K L M J 第3页，本讲稿共16页(连通网的连通网的)最小生成树最小生成树 假设要在 n 个城市之间建立
4、通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建如何在最节省经费的前提下建立立这个通讯网通讯网？问题：问题：第4页，本讲稿共16页 构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和权值之和”为最小。算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）该问题等价于：该问题等价于：算法一：（普里姆算法）算法一：（普里姆算法）第5页，本讲稿共16页 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点在添加的顶点 w 和已经在生成树上的顶点和已经在生成树上的顶点v 之间必定存在一之间必定存
5、在一条边，并且该边的权值在所有连通顶点条边，并且该边的权值在所有连通顶点 v 和和 w 之间的边中取值最小之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。普里姆算法的基本思想普里姆算法的基本思想:第6页，本讲稿共16页abcdegf195141827168213127例如例如:aedcbgf148531621所得生成树权值和=14+8+3+5+16+21=67第7页，本讲稿共16页 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U，则应在所有连通在所有连通U中顶点和中顶点和V-U中顶点的边中顶
6、点的边中选取权值最小的边中选取权值最小的边。一般情况下所添加的顶点应满足下列条件:UV-U第8页，本讲稿共16页 设置一个辅助数组，对当前设置一个辅助数组，对当前VU集中集中的每个顶点，记录和顶点集的每个顶点，记录和顶点集U中顶点相连接中顶点相连接的代价最小的边：的代价最小的边：struct VertexType adjvex;/U集中的顶点序号 VRType lowcost;/边的权值 closedgeMAX_VERTEX_NUM;第9页，本讲稿共16页abcdegf195141827168213127aedcbaaa19141814例如例如:e12ee8168d3dd7213c55 19
7、m m 14 m 1819 5 7 12 m m m 5 3 m m m m 7 3 8 21 m14 12 m 8 m 16 m m m 21 m 2718 m m m 16 27第10页，本讲稿共16页void MiniSpanTree_P(MGraph G,VertexType u)/用普里姆算法从顶点u出发构造网G的最小生成树 k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，Uu for(i=0;iG.vexnum;+i)继续向
8、生成树上添加顶点继续向生成树上添加顶点;第11页，本讲稿共16页 k=minimum(closedge);/求出加入生成树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk);/输出生成树上一条边 closedgek.lowcost=0;/第k顶点并入U集 for(j=0;jG.vexnum;+j)/修改其它顶点的最小边 if(G.arcskj.adj closedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;第12页，本讲稿共16页具体做法具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加
9、不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。考虑问题的出发点考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：第13页，本讲稿共16页abcdegf195141827168213127aedcbgf148531621例如例如:7121819第14页，本讲稿共16页算法描述算法描述:构造非连通图 ST=(V,);k=i=0;/k 计选中的边数 while(kn-1)+i;检查边集 E 中第第 i 条权值最小的边条权值最小的边(u,v);若若(u,v)加入加入ST后不使后不使ST中产生回路中产生回路，则则 输出边输出边(u,v);且且 k+;第15页，本讲稿共16页普里姆算法普里姆算法克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围比较两种算法第16页，本讲稿共16页