第7章-图2数据结构_第1页
第7章-图2数据结构_第2页
第7章-图2数据结构_第3页
第7章-图2数据结构_第4页
第7章-图2数据结构_第5页
已阅读5页,还剩24页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第七章图(2)本讲主要内容:图的连通性;连通分量和最小生成树;拓扑排序;关键路径;求最短路径问题复习上讲内容图的存储结构:数组表示法(邻接矩阵);邻接表;十字链表;邻接多重表图的遍历:深度优先搜索;广度优先搜索V1V2V3V47.4图的连通性问题7.4.1无向图的连通分量和生成树由图的遍历得出:对于连通图,从图中任一顶点出发,可以访问到图中的所有顶点;对于非连通图,需要从多个顶点出发,搜索到树的各个连通分量中的顶点集。ABLMCDEFGHHIJK再考虑一个问题:假设E(G)是连通图G中的所有边的集合,则从图中任一顶点出发遍历图,是不是所有的边都会经历?v1V2v6v4v5v8v3v7v1V2v6v4v5v8v3v7如果将E(G)分成2个集合T(G)和B(G),其中:T(G):遍历图的过程中经历的边集合B(G):遍历过程中未经历的边集合则:T(G)就是图G的极小连通子图中的边;

T(G)+图G的所有顶点=图G的极小连通子图(生成树)对于非连通图每个连通分量的生成树构成非连通图的生成森林ABLMCDEFGHHIJKHABLMCDEFGHIJKDEABLMCFJGHIK7.4.3最小生成树构造连通网的最小代价生成树。MST性质:假设N=(V,{E})是一个连通网,U是顶点集V上的一个非空子集。若(u,v)是一条具有最小权值的边,其中u∈U,v∈V-U,则必存在一棵包含边(u,v)的最小生成树。(证明过程略)构造最小生成树的算法:Prim算法和Kruskal算法。V1V2V3V4V5V66512556643V1V2V3V4V5V6V={v1,v2,v3,v4,v5,v6}U={v1,v3,v6}V-U={v2,v4,v5}(v4,v6)是从U到V-U中的最小权值的边,该边必然是最小生成树上的边。Prim算法构造最小生成树的过程:V1V2V3V4V5V6V1V2V3V4V5V66512556643V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6Prim算法:从U={u0},TE={}开始重复操作:在所有uU,vV-U的边(u,v)E中找一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=VPrim算法实现附设一个辅助数组closedge:记录从U到V-U具有最小代价的边iClosedge12345UV-UKadjvexlowcostV16V11V15{V1}{V2,V3,V4,V5,V6}2adjvexlowcostV350V15V36V34{V1,V3}{V2,V4,V5,V6}5adjvexlowcostV350V26V360{V1,V3,V6}{V2,V4,V5}3adjvexlowcostV3500V360{V1,V3,V6,V4}{V2,V5}1adjvexlowcost000V230{V1,V3,V6,V4,V2}{V5}4adjvexlowcost00000{V1,V3,V6,V4,V2,V5}{}Prim算法

voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){// struct{//记录由顶点集U到V-U的代价最小的边的辅助数组定义//VertexType

adjvex;//VRType

lowcost;//}closedge[MAX_VERTEX_NUM]; k=locateVex(G,u); for(j=0;j<G.vexnum;++j) if(j!=k)closedge[j]={u,G.arcs[k][j].adj};

closedge[k].lowcost=0; for(i=1;i<G.vexnum;++i){ k=mininum(closedge);

printf(closedge[k].adjvex,G.vexs[k]);

closedge[k].lowcost=0;

for(j=0;j<G.vexnum;++j) if(G.arcs[k][j].adj<closedge[j].lowcost)

closedge[j]={G.vexs[k],G.arcs[k][j].adj}; }}*****Kruskal算法构造最小生成树的过程V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V66512556643两种算法的区别:普鲁姆算法:基于连通地选择,避免回路克鲁斯卡儿算法:离散地选择,避免回路7.5有向无环图及其应用有向无环图(DAG图):无环的有向图有向树有环的有向图DAG图(无环)有向无环图是描述含有公共子式的表达式的有效工具例((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)+****+ab+bcd+cde+cde***+ab**+cde+7.5.1拓扑排序拓扑排序:由某个集合上的一个偏序得到该集合上的一个全序,就是拓扑排序。偏序:集合中仅有部分成员之间可以比较;全序:集合中全体成员之间均可比较。AOV网:顶点表示活动,弧表示活动之间的优先关系的有向图称为顶点表示活动的网。在AOV网中不应该存在环。v1v2v3v4v1v2v3v4偏序全序进行拓扑排序的方法:在有向图中选一个没有前驱的顶点且输出;从图中删除该结点和所有以该结点为尾的弧。重复上述操作。若可以输出全部顶点,则该图中不存在环,否则存在环。例如:算法实现:以邻接表的方法存储有向图;头结点增加信息:顶点入度;增加一个栈:存放入度为0的顶点。v1v2v3v4输出有向图的拓扑序列的算法StatusTopologicalSort(ALGraphG){

FindInDegree(G,indegree);

InitStack(S);for(i=0;i<G.vexnum;++i)if(!indegree[i])Push(S,i);count=0;while(!StackEmpty(S)){ Pop(S,i);printf(i,G.vertices[i].data);++count; for(p=G.vertices[i].firstarc;p;p=p->nextarc){ k=p->adjvex; if(!(--indegree[k]))push(S,k); }

}if(count<G.vexnum)returnERROR;elsereturnOK;}*****7.5.2关键路径AOE网:边表示活动的网;带权的有向无环网;估算工程的完成时间。AOE网有待研究的问题:完成整个工程至少需要多少时间?哪些活动是影响工程进度的关键?关键路径:路径长度最长的路径;分析关键路径的目的:找出关键活动。e(i):活动ai的最早开始时间;l(i):活动ai的最迟开始时间;l(i)-e(i):活动ai的时间余量;l(i)=e(i):关键活动;关键路径上的活动都是关键活动v1v2v3v5v7v8v9v4v6a10=2a1=6a7=9a4=1a2=4a8=7a3=5a6=2a5=1a11=4a9=4图中的关键路径是(v1,v2,v5,v8,v9

)例如:a6的最早开始时间是5,最晚开始时间是8。StatusCriticalPath(ALGraphG){if(!TopologicalOrder(G,T))returnERROR;

vl[0..G.vexnum-1]=ve[0..G.vexnum-1];while(!StackEmpty(T)) for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){ k=p-<adjvex;dut=*(p->info);

if(vl[k]-ve[k])vl[j]=ve[k]-dut; }for(j=0;j<G.vexnum;++j) for(p=G.vertices[j].firstarc;p;p=p->nextarc){ k=p->adjvex;dut=*(p->info);

ee=ve[j];el=vl[k]-dut; tag=(ee==el)?’*’:”;

printf(j,k,dut,ee,el,tag); }}*****7.6最短路径7.6.1从某个源点到其余各顶点的最短路径Dijkstra算法:按路径长度递增的次序产生最短路径D[i]表示当前所找到的从点v到每个终点vi的最短路径的长度。

D[i]初值:v到vi的弧的权值;则: 初值最小的路径就是从v出发的最短的一条路径下面按照长度递增多次序产生各个终点的最短路径v1v2v3v4v0v51005060201030105始点终点最短路径路径长度v0v1

v2

(v0,v2) 10

v3

(v0,v4,v3) 50

v4

(v0,v4) 30

v5

(v0,v4,v3,v5)60 带权有向图G6带权有向图G6中从v0到其余各点的最短路径Dijkstra算法举例终点从v0到各终点的D值和最短路径的求解过程i=1i=2i=3i=4i=5v1∞∞∞∞无v210(v0,v2)v3∞60(v0,v2,v3)50(v0,v4,v3)v430(v0,v4)30(v0,v4)v5100(v0,v5)100(v0,v5)90(v0,v4,v5)60(v0,v4,v3,v5)vjv2v4v3S{v0,v2}v1v2v3v4v0v51005060201030105迪杰斯特拉算法voidshotestPath_DIJ(MGaphG,intv0,PathMatrix&P,ShortPathTable&D){for(v=0;v<G.vexnum;++v){ final[v]=FALSE;D[v]=G.arcs[v0][v]; for(w=0;w<G.vexnum;++w)p[v][w]=FALSE; if(D[v]<INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;}}//forD[v0]=0;final[v0]=TRUE;for(i=1;i<G.vexnum;++i){ min=INFINITY; for(w=0;w<G.vexnum;++w) if(!final[w]) if(D[w]<min){v=w;min=D[w];} final[v]=TRUE; for(w=0;w<G.vexnum;++w) if(!fianl[w]&&(min+G.arcs[v][w]<D[w])){ D[w]=min+G.arcs[v][w]; P[w]=P[v];P[w][w]=TRUE;//P[w]=P[v]+[w] }//if}//for}*****7.6.2每一对顶点之间的最短路径Floyd算法:举例说明求从顶点vi到vj的最短路径v0v1v262437小结:图的连通性问题:连通分量、强连通分量、生成树最小生成树(普鲁姆算法,克鲁斯卡儿算法) 普鲁姆算法:基于连通地选择,避免回路 克鲁斯卡儿算法:离散地选择,避免回路拓扑排序:无入度点优先,动态生成无入度点关键路径:最早、最晚时间一致最短路径:(迪杰斯特拉)按路径长度递增次序产生最短路径。课堂练习:7.1,7.3,7.4,7.5,7.77.9试列出下图中全部可能的拓扑有序序列,并指出应用7.5.1节中算法求得的是哪一个序列。1235467.11试利用Dijkstra算法求下图中从顶点

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论