图的基本概念图的存储结构图的遍历最小生成树最短路径课件_第1页
图的基本概念图的存储结构图的遍历最小生成树最短路径课件_第2页
图的基本概念图的存储结构图的遍历最小生成树最短路径课件_第3页
图的基本概念图的存储结构图的遍历最小生成树最短路径课件_第4页
图的基本概念图的存储结构图的遍历最小生成树最短路径课件_第5页
已阅读5页,还剩51页未读, 继续免费阅读

下载本文档

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

文档简介

第八章图

图的基本概念图的存储结构图的遍历最小生成树最短路径拓扑排序关键路径第八章图图的基本概念1最短路径(ShortestPath)最短路径问题:如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径,使得沿此路径各边上的权值总和达到最小。问题解法单源最短路径—

Dijkstra算法任意顶点对之间的最短路径—Floyd算法最短路径(ShortestPath)最短路径问题:如果从2单源最短路径问题问题的提出:给定一个带权有向图G与源点v,求从v到G中其它顶点的最短路径。限定各边上的权值大于或等于0。为求得这些最短路径,Dijkstra提出按路径长度的递增次序,逐步产生最短路径的算法。首先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从顶点v到其它各顶点的最短路径全部求出为止。举例说明单源最短路径问题问题的提出:给定一个带权有向图G与源点v,3Dijkstra逐步求解的过程Dijkstra逐步求解的过程4算法的基本思想设置并逐步扩充一个集合S,存放已求出的最短路径的顶点,则尚未确定最短路径的顶点集合是V-S,为了直观起见,我们设想S中顶点均被涂成红色,V-S中的顶点均被涂成蓝色。算法初始化时,红点集中仅有一个源点,以后每一步都是按最短路径长度递增的顺序,逐个地把蓝点集中的顶点涂成红色后,加入到红点集中。算法的基本思想5算法粗框:while(S中的红点数<n)在当前蓝点集中选择一个最短路径长度最短的蓝点扩充到蓝点集中;

那么,如何在蓝点集中选择一个最短路径长度最短的蓝点呢?注意:这种蓝点所对应的最短路径上,除终点外,其余顶点都是红点。为此,对于图中每一个顶点i,都必须记住从v到i、且中间只经过红点的最短路径的长度,并将此长度记作i的距离值。算法粗框:那么,如何在蓝点集中选择一个最短路径长度最短的6

开始时,红点集只有一个源点v,初始蓝点集中的蓝点j的距离值D[j]均为有向边<v,j>上的权值。用数组D(n)来存放n个顶点的距离值。若当前蓝点集中具有最小距离值的蓝点是k,则其距离值D(k)是k的最短路径长度,并且k是蓝点集中最短路径长度最短的顶点。开始时,红点集只有一个源点v,初始蓝点集中的蓝点j的距离7证明1:(距离值D(k)是k的最短路径长度)若D(k)不是k的最短路径长度,则必存在另外一条从源点v到k的路径P,其长度小于D(k)。由距离值的定义可知,路径P上必然包含一个或多个蓝点作为中间点。假设从源点沿P向前第一次碰到的蓝点是x,则P上从源点v到x的这一段路径的长度,显然不小于x的距离值D(x)。而P上从x到终点k所经过的边上,其权值均为非负实数,所以D(x)<=P的长度。又因为P的长度<D(k)(这是假设前提),于是有下述不等式:D(x)<=P的长度<D(k)由此可知:D(x)<D(k),这与k是蓝点集中距离值最小的蓝点产生矛盾。所以D(k)是k的最短路径长度。证明1:(距离值D(k)是k的最短路径长度)8蓝点k蓝点x红点集S源点v蓝点k蓝点x红点集S源点v9证明2:(k是蓝点集中最短路径长度最短的顶点)设i是蓝点集中任何一个异于k的顶点,若i的最短路径只经过红点,则该最短路径长度是i的距离值D(i),因为D(k)是当前蓝点集距离值最小的顶点,所以D(i)>=D(k)。若i的最短路径P包含其它蓝点作为中间点,设P上第一个蓝点是j,则P上从v到j的路径长度就是j的距离值D(j)。显然,D(j)>=D(k),而P的长度=D(j)+j到i的长度,因为j到i的长度为非负实数,所以P的长度>=D(k)。由此可知蓝点集中任意顶点i的最短路径长度都不会小于k的最短路径长度D(k)。证明2:(k是蓝点集中最短路径长度最短的顶点)10扩充红点集的方法:每一步只要在当前蓝点集中选择一个具有最小的距离值的蓝点k扩充到红点集合中,k被涂成红色之后,剩余的蓝点的距离值可能由于增加了新红点k而发生变化(即减少)。因此必须调整当前蓝点集中各蓝点的距离值。算法框架:S={v};置初始蓝点集中各蓝点的距离值;while(S中红点数<n){在当前蓝点集中选择距离值最小的顶点k;S=S+{k};/*将k涂成红色加入红点集*/调整剩余蓝点的距离值;}扩充红点集的方法:每一步只要在当前蓝点集中选择一个具11如何调整剩余蓝点的距离值呢?

若新红点k加入红点集S后,使得某个蓝点j的距离值D(j)减少,则必定是由于存在一条从源点v途径新红点k最终到达蓝点j且中间只经过红点的、新的最短路径Pvkj,它的长度小于从源点v到达j且中间只经过老红点(即步包含k)的原最短路径Pvj的长度D(j)。由于Pvkj是一条中间只经过红点的最短路径,所以,它的前一段从v到k的路径必定是k的最短路径,其长度为D(k);它的后一段从k到j的路径Pkj只可能有两种情形:其一是由k经过边<k,j>直达蓝点j;其二是从k出发再经过S中若干老红点后到达j。如何调整剩余蓝点的距离值呢?12用反正法证明后一种情形是不可能的。假设从源点v出发,经过红点k、老红点x,最后到达蓝点j的新最短路径Pvkxj的长度小于原D(j)。因为x比k先加入红点集S,故D(x)<=D(k),又因为权值非负,所以从v到x的路径Pvx的长度不大于从v经k到x的路径Pvkx的长度,即length(Pvk)=D(x)<=D(k)+length(Pkx)=length(Pvkx)因此从v经x到j的路径长度:length(Pvxj)=length(Pvk)+length(Pxj)不大于从v经k、x到j的新路径长度length(Pvkxj)=length(Pvkx)+length(Pxj)又因为Pvxj中间只经过老红点,所以Pvxj的长度不大于D(j)的值,由此可得:D(j)<=length(Pvxj)<=length(Pvkxj)用反正法证明后一种情形是不可能的。13这与新路径Pvkxj的长度小于原D(j)值的假设相矛盾!因此,使得D(j)值减小的新路径比必是先经过老红点到达k,然后经过边<k,j>直达蓝点j的,它得长度是D(k)+边<k,j>上的权。由此得到调整距离值的方法:当顶点k从蓝点集转移到红点集时,对蓝点集扫描检查,若某蓝点j的原距离值D(j)大于新路径的长度D(k)+边<k,j>上的权,则将D(j)修改成此长度值。为了同时得到路径,设置一个路径向量P[n],其中P[i]表示从源点到达i点的最短路径上该点的前驱顶点。这与新路径Pvkxj的长度小于原D(j)值的假设相矛盾!因此14蓝点j蓝点k红点集S源点vx蓝点j蓝点k红点集S源点vx15循环红点集k+1D[0]…D[4]P[]…P[4]初始化1234{4}{4,3}{4,3,5}{4,3,5,1}{4,3,5,1,2}-3512maxmax20060maxmax20030maxmax20030maxmax20030maxmax20030004040040300403004030040312534501030102060100max1max2203<-404305<-3<-4循环红点集k+1D[0]…D[4]P[]…P[4]初始化{4161253410301020125341030102017floatD[n];intP[n],S[n];DIJKSTRA(floatC[][n],intv){inti,j,k,v1,pre;intmin,max=60,inf=80;v1=v-1;for(i=0;i<n;i++){D[i]=C[v1][i];if(D[i]!=max)P[i]=v;elseP[i]=0;}for(i=0;i<n;i++)S[i]=0;S[v1]=1;D[v1]=0;for(i=0;i<n-1;i++){min=inf;for(j=0;j<n;j++)if((!S[j])&&(D[j]<min)){min=D[j];k=j;}S[k]=1;for(j=0;j<n;j+=)if((!S[j])&&(D[j]>D[k]+C[k][j])){D[j]=D[k]+C[k][j];P[j]=k+1;}}for(i=0;i<n;i++){printf(“%f\n%d”,D[i],i+1);pre=p[i];while(pre!=0){printf(“<--%d”,pre);pre=P[pre-1];}}}floatD[n];S[k]=1;18算法说明对于顶点i和j:1、首先,考虑从i到j是否有以顶点1为中间点的路径,:i,1,j,即考虑图中是否有边<i,1>和<1,j>,若有,则新路径i,1,j的长度是C[i][1]+C[1][j],比较路径i,j和i,1,j,的长度,并以较短者为当前所求得的最短路径,。该路径是中间点序号不大于1的最短路径。所有顶点对之间的最短路径算法说明所有顶点对之间的最短路径192、其次,考虑从i到j是否包含顶点2为中间点的路径:i,...,2,...,j,若没有,则从i到j的最短路径仍然是第一步中求出的,即从i到j的中间点序号不大于1的最短路径;若有,则i,...,2,...,j可分解成两条路径i,...,2和2,...,j,而这两条路径是前一次找到的中间点序号不大于1的最短路径,将这两条路径相加就得到路径i,...,2,...,j的长度,将该长度与前一次求出的从i到j的中间点序号不大于1的最短路径长度比较,取其较短者作为当前求得的从i到j的中间点序号不大于2的最短路径。2、其次,考虑从i到j是否包含顶点2为中间点的路径:i,..203、然后,再选择顶点3加入当前求得的从i到j中间点序号不大于2的最短路径中,按上述步骤进行比较,从未加入顶点3作中间点的最短路径和加入顶点3作中间点的新路径中选取较小者,作为当前求得的从i到j的中间点序号不大于3的最短路径。依次类推,直到考虑了顶点n加入当前从i到j的最短路径后,选出从i到j的中间点序号不大于n的最短路径为止。由于图中顶点序号不大于n,所以从i到j的中间点序号不大于n的最短路径,已考虑了所有顶点作为中间点的可能性。因而它必是从i到j的最短路径。3、然后,再选择顶点3加入当前求得的从i到j中间点序号不大于21算法的基本思想就是:从初始的邻接矩阵A0开始,递推地生成矩阵序列A1,A2,...,An显然,A中记录了所有顶点对之间的最短路径长度。若要求得到最短路径本身,还必须设置一个路径矩阵P[n][n],在第k次迭代中求得的path[i][j],是从i到j的中间点序号不大于k的最短路径上顶点i的后继顶点。算法结束时,由path[i][j]的值就可以得到从i到j的最短路径上的各个顶点。算法的基本思想就是:显然,A中记录了所有顶点对之间的最短路径22Floyd算法intpath[n][n];FLOYD(floatA[][n],floatC[][n]){inti,j,k,next;intmax=160;for(i=0,i<n,i++)for(j=0;j<n;j++){if(C[i][j]!=max)path[i][j]=j;elsepath[i][j]=0;A[i][j]=C[i][j];}for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(a[i][j]>(A[i][k]+A[k][j])){A[i][j]=A[i][k]+A[k][j];path[i][j]=path[i][k];}for(i=0;i<n;i++)for(j=0;j<n;j++){printf(“%f”,A[i][j]);next=path[i][j];if(next==0)printf(“%dto%dnopath.\n”,i+1;j+1);else{printf(“%d”,i+1);while(next!=j){printf(“-->%d”,next+1);next=path[next][j];}printf(“-->%d”,j+1);}}}Floyd算法for(i=0;i<n;i++)23125345010301020601001253450103010206010024图的基本概念图的存储结构图的遍历最小生成树最短路径ppt课件25拓扑排序计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外,一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动,这个工程就可以完成了。例如,计算机专业学生的学习就是一个工程,每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程,有些则不要求。这样在有的课程之间有先后关系,有的课程可以并行地学习。拓扑排序计划、施工过程、生产流程、程序流程等都是“工程”。除26C1高等数学C2程序设计基础C3离散数学C1,C2

C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1C9计算机原理C8

课程代号课程名称先修课程C1高27学生课程学习工程图学生课程学习工程图28

可以用有向图表示一个工程。在这种有向图中,用顶点表示活动,用有向边<Vi,Vj>表示活动的前后次序。Vi必须先于活动Vj

进行。这种有向图叫做顶点表示活动的AOV网络(ActivityOnVertices)。在AOV网络中,如果活动Vi必须在活动Vj

之前进行,则存在有向边<Vi,Vj>,AOV网络中不能出现有向回路,即有向环。在AOV网络中如果出现了有向环,则意味着某项活动应以自己作为先决条件。因此,对给定的AOV网络,必须先判断它是否存在有向环。可以用有向图表示一个工程。在这种有向29检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列,使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中,则该AOV网络中必定不会出现有向环;相反,如果得不到满足要求的拓扑有序序列,则说明AOV网络中存在有向环,此AOV网络所代表的工程是不可行的。检测有向环的一种方法是对AOV网络构造它的拓30例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为31进行拓扑排序的方法

输入AOV网络。令n为顶点个数。1、在AOV网络中选一个没有直接前驱的顶点(即此顶点入度为0),并输出之;2、从图中删去该顶点,同时删去所有它发出的有向边;重复以上两步,直到全部顶点均已输出,拓扑有序序列形成,拓扑排序完成;或图中还有未输出的顶点,但已跳出处理循环。这说明图中还剩下一些顶点,它们都有直接前驱,再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。进行拓扑排序的方法 输入AOV网络。令n为顶点个数。32abcdefabcdef33

为了便于考察每个顶点的入度,在顶点表中增加一个入度域,同时设置一个栈来存储所有入度为0的顶点。在进行拓扑排序之前,只要对顶点表扫描一遍,将所有入度为0的顶点都推入栈中,一旦排序过程中出现新的入度为0的顶点,也同样将其推入栈中。v10v22nullv31v42v53nullv60。。。

。。。

。。。

。。。

123456出边表为了便于考察每个顶点的入度,在顶点表中增加一个入度域341、扫描顶点表,将入度为0的顶点入栈;2、while(栈非空){将栈顶顶点v弹出并输出之;检查v的出边,将每条出边<v,u>终点u的入度减1,若u的入度变为0,则把u推入栈;}3、若输出的顶点数小于n,则输出“有回路”;否则拓扑排序正常结束。拓扑排序算法框架1、扫描顶点表,将入度为0的顶点入栈;拓扑排序算法框架35在算法具体实现时,上述链栈无须占有额外的空间,而是利用顶点表中值为0的入度域来存放链栈的指针(用下标值模拟)。因为顶点域中已经存入有相应的顶点,故入栈时只需修改相应的指针。在算法具体实现时,上述链栈无须占有额外的空间,而是利36021230021231021121014021toptoptoptop=0123456021230021231021121014021toptop37044011044011044001044001toptoptop123456044011044011044001044001toptop38拓扑排序算法typedefintdatatype;typedefintvextype;typedefstructnode/*边表结点定义*/{intadjvex;structnode*next;}edgenode;

typedefstruct/*顶点表结点定义*/{vextypevertexintid;edgenode*link}vexnode;vexnodedig[n];拓扑排序算法39TOPOSORT(vexnodedig[]){inti,j,k,m=0,top=-1;edgenode*p;for(i=0;i<n;i++)if(dig[i].id==0){dig[i].id=top;top=i;}while(top!=-1){j=top;top=dog[top].id;printf(“%d\t”,dig[j].vertex+1);m++;p=dig[j].link;while(p){k=p->adjvex;dig[k].id--;if(dig[k].id==0){dig[k].id=top;top=k;}p=p->next;}}if(m<n)printf(“\nThenetworkhasacycle\n”);}

TOPOSORT(vexnodedig[])w40算法分析设AOV网有n个顶点,e条边。初始建立入度为0的顶点栈,要检查所有顶点一次,执行时间为O(n);排序中,若AOV网无回路,则每个顶点入、出栈各一次,每个边表结点被检查一次,执行时间为O(n+e),所以总的时间复杂度为O(n+e)。算法分析41关键路径如果在无有向环的带权有向图中用有向边表示一个工程中的各项活动(Activity)用边上的权值表示活动的持续时间(Duration)用顶点表示事件(Event)AOE网络在某些工程估算方面非常有用。例如,可以使人们了解:(1)完成整个工程至少需要多少时间(假设网络中没有环).(2)为缩短完成工程所需的时间,应当加快哪些活动. 则这样的有向图叫做用边表示活动的网络,简称AOE(ActivityOnEdges)网络。关键路径如果在无有向环的带权有向图中AOE网络在某些工程估算42在AOE网络中,有些活动顺序进行,有些活动并行进行。从源点到各个顶点,以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了,整个工程才算完成。因此,完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(CriticalPath)。在AOE网络中,有些活动顺序进行,有些活动并43定义几个与计算关键活动有关的量:事件Vi的最早可能开始时间Ve(i)是从源点V0

到顶点Vi的最长路径长度。事件Vi的最迟允许开始时间Vl[i]是在保证汇点Vn-1

在Ve[n-1]时刻完成的前提下,事件Vi的允许的最迟开始时间。活动ak的最早可能开始时间e[k]设活动ak在边<Vi,Vj>上,则e[k]是从源点

V0到顶点Vi的最长路径长度。因此,e[k]=Ve[i]。活动ak的最迟允许开始时间l[k]l[k]是在不会引起时间延误的前提下,该活动允许的最迟开始时间。定义几个与计算关键活动有关的量:事件Vi的最早可能开始时44l[k]=Vl[j]-dur(<i,j>)。其中,dur(<i,j>)是完成ak所需的时间。 时间余量l[k]-e[k]表示活动ak的最早可能开始时间和最迟允许开始时间的时间余量。l[k]==e[k]表示活动ak是没有时间余量的关键活动。显然,关键路径上的所有活动都是关键活动。为找出关键活动,需要求各个活动的e[k]与l[k],以判别是否l[k]==e[k].为求得e[k]与l[k],需要先求得从源点V0到各个顶点Vi的Ve[i]和Vl[i]。求Ve[i]的递推公式l[k]=Vl[j]-dur(<45从Ve[0]=0开始,向前递推

<Vi,Vj>

S2,i=1,2,,n-1

其中,S2是所有从Vi指向顶点Vj的有向边<Vi

,Vj>的集合。 从Vl[n-1]=Ve[n-1]开始,反向递推

<Vi,Vj>

S1,i=n-2,n-3,,0其中,S1是所有从顶点Vi发出的有向边<Vi

,Vj

>的集合。 从Ve[0]=0开始,向前递推46这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。设活动ak(k=1,2,…,e)在带权有向边<Vi

,Vj

>上,它的持续时间用dur(<Vi

,Vj

>)表示,则有e[k]=Ve[i];l[k]=Vl[j]-

dur(<Vi

,Vj

>);k=1,2,…,e。

这样就得到计算关键路径的算法。计算关键路径时,可以一边进行拓扑排序一边计算各顶点的Ve[i],并按拓扑有序的顺序对各顶点重新进行了编号。算法在求Ve[i],i=0,1,…,n-1时按拓扑有序的顺序计算,在求Vl[i],i=n-1,n-2,…,0时按逆拓扑有序的顺序计算。这两个递推公式的计算必须分别在拓扑有序及逆拓扑有47v5v1v2v3v4v6v7v8v9465112974426405771614181814108661670v5v1v2v3v4v6v7v8v946511297442648v5v1v2v3v4v6v7v8v9465112974426405771614181814108661670活动1-21-31-42-53-54-65-75-86-87-98-9e0006457771614l02366877101614e-l02302300300v5v1v2v3v4v6v7v8v946511297442649v5v1v2v7v8v9619742607161418181461670v5v1v2v7v8v961974260716141818150求关键路径的算法typedefstructnode1/*边表结点定义*/{intadjvex;/*邻接点域*/intdut;/*权值*/structnode1*next;/*链域*/}edgenode1;

typedefstructnode2/*顶点表结点定义*/{vextypevertex;/*顶点信息*/intid;/*入度*/edgenode1*link;/*边表头指针*/}vexnode1;

vexnode1dig[n];

/*邻接表*/求关键路径的算法51CRITICALPATH(vexnode1dig[]){inti,j,k,m;intfront=-1;rear=-1;/*顺序队列首位指针置初值*/inttpord[n],vl[n],ve[n];intl[maxsize],e[maxsize];edgenode1*p;for(i=0;i<n;i++)ve[i]=0;/*各事件最早发生时间置为0*/for(i=0;i<n;i++)/*将入度为0的顶点入队*/if(dig[i].id==0)tpord[++rear]=i;CRITICALPATH(vexnode1dig[])52m=0;/*计数器初始化*/while(front!=rear)/*队非空*/{front++;j=tpord[front];/*出队*/m++;/*对出队的顶点个数计数*/p=dig[j].link;/*指向出边表中顶点的下标*/whi

温馨提示

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

评论

0/150

提交评论