图的连通性(最小生成树的算法思想).ppt

资源ID：6257771 资源大小：715.50KB 全文页数：35页
资源格式： PPT 下载积分：15金币

快捷下载

会员登录下载

三方登录下载：

下载资源需要15金币

邮箱/手机：
温馨提示：	用户名和密码都是您填写的邮箱或者手机号，方便查询和重复下载（系统自动生成）
支付方式：
验证码：	换一换

加入VIP免费专享

账号：
密码：
验证码：	换一换
当日自动登录忘记密码？

友情提示

1、下载资料失败解决办法

2、PDF文件下载后，可能会被浏览器默认打开，此种情况可以点击浏览器菜单，保存网页到桌面，就可以正常下载了。

3、本站不支持迅雷下载，请使用电脑自带的IE浏览器，或者360浏览器、谷歌浏览器下载即可。

4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩，下载后原文更清晰。

5、试题试卷类文档，如果标题没有明确说明有答案则都视为没有答案，请知晓。

网站客服

侵权投诉

图的连通性(最小生成树的算法思想).ppt

图的连通性,1.算法思想,假设N=(V,E)是连通网,TE是N上最小生成树中边的集合,算法从U=vk,TE=开始(即从vk出发求最小生成树,vkV)。重复执行下述操作：在所有的边(vi,vj)E(viU,vjV-U)中寻找一条权值最小的边(vi,vj)将其添加到TE中(或打印之),同时把vj添加到集合U 中。反复执行上述操作n-1次（或所有顶点全部加入U时为止）。,一、最小生成树,2.实例：V=v1,v2,v3,v4,v5,v6,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,任取uk=v1,则：U=v1,V-U=v2,v3,v4,v5,v6,2.实例：V=v1,v2,v3,v4,v5,v6,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,任取uk=v1,则：U=v1,V-U=v2,v3,v4,v5,v6,取边(v1,v3),则：U=v1,v3,V-U=v2,v4,v5,v6,2.实例：V=v1,v2,v3,v4,v5,v6,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,任取uk=v1,则：U=v1,V-U=v2,v3,v4,v5,v6,取边(v1,v3),则：U=v1,v3,V-U=v2,v4,v5,v6,取边(v3,v6),则：U=v1,v3,v6,V-U=v2,v4,v5,2.实例：V=v1,v2,v3,v4,v5,v6,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,任取uk=v1,则：U=v1,V-U=v2,v3,v4,v5,v6,取边(v1,v3),则：U=v1,v3,V-U=v2,v4,v5,v6,取边(v3,v6),则：U=v1,v3,v6,V-U=v2,v4,v5,取边(v6,v4),则：U=v1,v3,v6,v4,V-U=v2,v5,2.实例：V=v1,v2,v3,v4,v5,v6,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,任取uk=v1,则：U=v1,V-U=v2,v3,v4,v5,v6,取边(v1,v3),则：U=v1,v3,V-U=v2,v4,v5,v6,取边(v3,v6),则：U=v1,v3,v6,V-U=v2,v4,v5,取边(v6,v4),则：U=v1,v3,v6,v4,V-U=v2,v5,取边(v3,v2),则：U=v1,v3,v6,v4,v2,V-U=v5,2.实例：V=v1,v2,v3,v4,v5,v6,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,任取uk=v1,则：U=v1,V-U=v2,v3,v4,v5,v6,取边(v1,v3),则：U=v1,v3,V-U=v2,v4,v5,v6,取边(v3,v6),则：U=v1,v3,v6,V-U=v2,v4,v5,取边(v6,v4),则：U=v1,v3,v6,v4,V-U=v2,v5,取边(v3,v2),则：U=v1,v3,v6,v4,v2,V-U=v5,取边(v2,v5),则：U=v1,v3,v6,v4,v2,v5,V-U=,2.实例：V=v1,v2,v3,v4,v5,v6,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,任取uk=v1,则：U=v1,V-U=v2,v3,v4,v5,v6,取边(v1,v3),则：U=v1,v3,V-U=v2,v4,v5,v6,取边(v3,v6),则：U=v1,v3,v6,V-U=v2,v4,v5,取边(v6,v4),则：U=v1,v3,v6,v4,V-U=v2,v5,取边(v3,v2),则：U=v1,v3,v6,v4,v2,V-U=v5,取边(v2,v5),则：U=v1,v3,v6,v4,v2,v5,V-U=,3.算法的实现：,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,用一个辅助的一维数组closedge0.n-1存储n个顶点到U的距离：,即对于每一个viV-U,1in,1)用closedgei-1.lowcost存储vi到U的最短距离(若vi已属于U中的元素,则vi到U的距离为0)；2)用closedgei-1.adjvex存储vi到U的最短距离所邻接的那个顶点的值。,用顺序存储结构(Mgraph G)存储图，即利用一个二维数组(G.arcs)存储图的邻接矩阵，用一个一维数组(G.vexs)存储各顶点的值。,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,打印(v1,v3),也即打印：(closedgek.adjvex，G.vexsk),一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,用二维数组的第K行与这里的lowcost行中的元素依次比较，若发现距离变小了，则用小值替代大值，且用G.vexsK 的值(即v3)取代相应的adjvex的值。,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,打印(v3,v6),也即打印：(closedge5.adjvex，G.vexs5),一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,用二维数组的第K行与这里的lowcost行中的元素依次比较，若发现距离变小了，则用小值替代大值，且用G.vexsK 的值(即v6)取代相应的adjvex的值。,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,打印(v6,v4),也即打印：(closedge3.adjvex，G.vexs3),一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,用二维数组的第K行与这里的lowcost行中的元素依次比较，若发现距离变小了，则用小值替代大值，且用G.vexsK 的值(即v4)取代相应的adjvex的值。,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,打印(v3,v2),也即打印：(closedge1.adjvex，G.vexs1),一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,用二维数组的第K行与这里的lowcost行中的元素依次比较，若发现距离变小了，则用小值替代大值，且用G.vexsK 的值(即v2)取代相应的adjvex的值。,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,打印(v2,v5),也即打印：(closedge4.adjvex，G.vexs4),一、最小生成树,v1,v2,v3,v4,v5,v6,6,5,5,1,2,5,6,4,6,3,数据结构的动态分析,6 1 5 6 5 3 1 5 5 6 4 5 6 5 2 3 6 6 4 2 6,G.arcs如下：,012345,0 1 2 3 4 5,算法执行期间一维数组closedge的动态变化过程：,3.算法的实现：,0,1,2,3,4,5,0,1,G.vexs:,0 1 2 3 4 5,一、最小生成树,3.算法的实现：,算法程序,算法程序,1.复习图的数组表示法(MGgraph)的定义,#define INFINITY 10000/INFINITY用以表示#define MAX_VERTEX_NUM 20/最大顶点数enum GraphKind DG,DN,UDG,UDN;/枚举：有向图,有向网,无向图,无向网typedef struct ArcCell VRType adj;/VRType的类型视具体情况而定。对于带权图，adj用以存/放边或弧上的权值;对于无权图，adj用以存放0或1(int类型)/InfoType*info;/一般情况下可以不使用该项 ArcCell,AdjMatrix MAX_VERTEX_NUM,MAX_VERTEX_NUM;/AdiMatrix是一个类型为ArcCell的二维数组,用以存放弧或边的邻接关系或权值typedef struct VertexType vexs MAX_VERTEX_NUM;/VertexType是顶点值的类型/一维数组vexs用以存放各顶点的值 AdjMatrix arcs;/二维数组arcs存放边或弧上的信息（如权值）int vexnum,arcnum;/这两项分别存放图的顶点数目和弧的条数 GraphKind kind;/kind用以存放图的种类标志 MGraph,算法程序,typedef struct Adjvexlowcost VertexType adjvex;int lowcost;Adjvexlowcost,ALListMAX_VERTEX_NUM;ALList closedge;/定义一个一维数组，其每个数组下标变量/closedgei均有两个分量：adjvex 和lowcost/closedgei.lowcost记录了vi到U的最短距离/closedgei.adjvex记录了vi到U的这个最短距依赖U中哪个顶点,2.求图的最小生成树的辅助一维数组 closedge的定义,算法程序,void MiniSpanTree_PRIM(MGraph G,VertexType u)k=locateVex(G,u);/在G.vexs0.G.vexnum-1中查找u,将u的序号作为返回值 closedgek.adjvex=u;closedgek.lowcost=0;/将u并入到U中 for(j=0;jG.vexnum;+j)/将邻接矩阵的第k行(如选u=v1,则k=0)作为数组/closedge的初值 if(!j=k)closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;for(i=1;iG.vexnum;+i)/在无向网中找出n-1条边构成最小生成树 k=minimum(closedge);/在数组closedge中查找一个k使得/closedgek.lowcost是最小的且不等于0 printf(closedgek.adjvex,G.vexk);/输出找到的一条最小代价边 closedgek.lowcost=0;/将vk+1添加到U中 for(j=0;jG.vexnum;+j)/用邻接矩阵的第k行及vk+1修改closedge if(G.arcskj.adj)closedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;,void MiniSpanTree_PRIM(MGraph G,VertexType u)k=locateVex(G,u);/在G.vexs0.G.vexnum-1中查找u,将u的序号作为返回值 closedgek.adjvex=u;closedgek.lowcost=0;/将u并入到U中 for(j=0;jG.vexnum;+j)/将邻接矩阵的第k行(如选u=v1,则k=0)作为数组/closedge的初值 if(!j=k)closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;for(i=1;iG.vexnum;+i)/在无向网中找出n-1条边构成最小生成树 k=minimum(closedge);/在数组closedge中查找一个k使得/closedgek.lowcost是最小的且不等于0 printf(closedgek.Adjvex,G.vexk);/输出找到的一条最小代价边 closedgek.lowcost=0;/将vk+1添加到U中 for(j=0;jG.vexnum;+j)/用邻接矩阵的第k行及vk+1修改closedge if(G.arcskj.adj)closedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;/MiniSpanTree_PRIM,void MiniSpanTree_PRIM(MGraph G,VertexType u)k=locateVex(G,u);/在G.vexs0.G.vexnum-1中查找u,将u的序号作为返回值 closedgek.adjvex=u;closedgek.lowcost=0;/将u并入到U中 for(j=0;jG.vexnum;+j)/将邻接矩阵的第k行(如选u=v1,则k=0)作为数组/closedge的初值 if(!j=k)closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;for(i=1;iG.vexnum;+i)/在无向网中找出n-1条边构成最小生成树 k=minimum(closedge);/在数组closedge中查找一个k使得/closedgek.lowcost是最小的且不等于0 printf(closedgek.Adjvex,G.vexk);/输出找到的一条最小代价边 closedgek.lowcost=0;/将vk+1添加到U中 for(j=0;jG.vexnum;+j)/用邻接矩阵的第k行及vk+1修改closedge if(G.arcskj.adj)closedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj;/MiniSpanTree_PRIM,int minimum(ALList closedge)int k=-1;mini=1000;for(j=0;jG.vexnum;+j)if(closedgej.lowcost!=0/minimum,End,返回,

注意事项

本文（图的连通性(最小生成树的算法思想).ppt）为本站会员（牧羊曲112）主动上传，三一办公仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若此文所含内容侵犯了您的版权或隐私，请立即通知三一办公（点击联系客服），我们立即给予删除！

温馨提示：如果因为网速或其他原因下载失败请重新下载，重复下载不扣分。