考研数据结构图的必背算法及知识点.docx
- 文档编号:17719186
- 上传时间:2023-08-03
- 格式:DOCX
- 页数:14
- 大小:71.18KB
考研数据结构图的必背算法及知识点.docx
《考研数据结构图的必背算法及知识点.docx》由会员分享,可在线阅读,更多相关《考研数据结构图的必背算法及知识点.docx(14页珍藏版)》请在冰点文库上搜索。
考研数据结构图的必背算法及知识点
Preparedon22November2020
考研数据结构图的必背算法及知识点
1.最小生成树:
无向连通图的所有生成树中有一棵边的权值总和最小的生成树
问题背景:
假设要在n个城市之间建立通信联络网,则连通n个城市只需要n—1条线路。
这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路,相应地都要付出一定的经济代价。
n个城市之间,最多可能设置n(n-1)/2条线路,那么,如何在这些可能的线路中选择n-1条,以使总的耗费最少呢
分析问题(建立模型):
可以用连通网来表示n个城市以及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的权值表示相应的代价。
对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。
即无向连通图的生成树不是唯一的。
连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树,对连通图的不同遍历,就可能得到不同的生成树。
图G5无向连通图的生成树为(a)、(b)和(c)图所示:
G5
G5的三棵生成树:
可以证明,对于有n个顶点的无向连通图,无论其生成树的形态如何,所有生成树中都有且仅有n-1条边。
最小生成树的定义:
如果无向连通图是一个网,那么,它的所有生成树中必有一棵边的权值总和最小的生成树,我们称这棵生成树为最小生成树,简称为最小生成树。
最小生成树的性质:
假设N=(V,{E})是个连通网,U是顶点集合V的一个非空子集,若(u,v)是个一条具有最小权值(代价)的边,其中,
则必存在一棵包含边(u,v)的最小生成树。
解决方案:
两种常用的构造最小生成树的算法:
普里姆(Prim)和克鲁斯卡尔(Kruskal)。
他们都利用了最小生成树的性质
1.普里姆(Prim)算法:
有线到点,适合边稠密。
时间复杂度O(N^2)
假设G=(V,E)为连通图,其中V为网图中所有顶点的集合,E为网图中所有带权边的集合。
设置两个新的集合U和T,其中
集合U(顶点集)用于存放G的最小生成树中的顶点,
集合T(边集合)存放G的最小生成树中的边。
T,U的初始状态:
令集合U的初值为U={u1}(假设构造最小生成树时,从顶点u1出发),集合T的初值为T={}。
Prim算法的思想是:
从所有u∈U,v∈V-U的边中,选取具有最小权值的边(u,v)∈E,将顶点v加入集合U中,将边(u,v)加入集合T中,如此不断重复,直到U=V时,最小生成树构造完毕,这时集合T中包含了最小生成树的所有边。
Prim算法可用下述过程描述,其中用wuv表示顶点u与顶点v边上的权值。
(1)U={u1},T={};
(2)while(U≠V)do
(u,v)=min{wuv;u∈U,v∈V-U}
T=T+{(u,v)}
U=U+{v}
(3)结束。
按照Prim方法,从顶点1出发,该网的最小生成树的产生过程如图:
为实现Prim算法,需设置两个辅助closedge,用来保存U到集合V-U的各个顶点中具有最小权值的边的权值。
对每个Vi∈(V-U)在辅助数组中存在一个相应的分量closedge[i-1],它包括两个域:
typedefstructArcNode
{
intadjvex;
owcost=0;owcost,故需修改closedge[1]为边(v2,v3)及其权值,同理修改closedge[4],closedge[5].
closedge[1].adjvex=3.
closedge[1].lowcost=5.
closedge[4].adjvex=1.
closedge[4].lowcost=5.
closedge[5].adjvex=3.
closedge[5].lowcost=6.
以此类推,直至U=V;
下图给出了在用上述算法构造网图的最小生成树的过程中:
Prim算法实现:
按照算法框架:
(1)U={u1},T={};
(2)while(U≠V)do
(u,v)=min{wuv;u∈U,v∈V-U}
T=T+{(u,v)}
U=U+{v}
(3)结束。
当无向网采用二维数组存储的邻接矩阵存储时,Prim算法的C语言实现为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dj};owcost=0;djvex,[k]);owcost=0;
for(j=0;j<;++j)
if[k][j].adj } owcost中求最小值,其频度为n-1;其二是重新选择具有最小代价的边,其频度为n。 由此,普里姆算法的时间复杂度为O(n2),与网中的边数无关,因此适用于求边稠密的网的最小生成树。 2.克鲁斯卡尔(Kruskal): 由点到线,适合边稀疏的网。 时间复杂度: O(e*loge) Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。 基本思想是: 1)设无向连通网为G=(V,E),令G的最小生成树为T,其初态为T=(V,{}),即开始时,最小生成树T由图G中的n个顶点构成,顶点之间没有一条边,这样T中各顶点各自构成一个连通分量。 2)在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量,则将此边加入到T中,否则舍弃此边而选择下一条边(若该边依附的两个顶点属于同一个连通分量,则舍去此边,以免造成回路)。 依此类推,当T中的连通分量个数为1时,此连通分量便为G的一棵最小生成树。 按照Kruskal方法构造最小生成树的过程如图所示: 在构造过程中,按照网中边的权值由小到大的顺序,不断选取当前未被选取的边集中权值最小的边。 依据生成树的概念,n个结点的生成树,有n-1条边,故反复上述过程,直到选取了n-1条边为止,就构成了一棵最小生成树。 Kruskal算法的实现: 算法的框架: 构造非连通图T=(V,{}) k=i=0; 1); vf2=Find(father,edges[i].v2); if(vf1! =vf2) {father[vf2]=vf1; j++; printf(“%3d%3d\n”,edges[i].v1,edges[i].v2); } i++; } } vernum-1] InitStack(S); for(i=0;i<;++i) if(! indegree[i])Push(S,i)ata);++count;irstarc;p;p=p—>nextarc){ k=p—>adivex; 键路径(AOE网): 在AOE-网中有些活动可以并行地进行,所以完成工程的最短时间是从开始点到完成点的最长路径的长度,路径长度最长的路径叫做关键路径(CriticalPath)。 网: (Activityonedgenetwork) AOE网示意图若在带权的有向图中,以顶点表示事件,以有向边表示活动,边上的权值表示活动的开销(如该活动持续的时间),则此带权的有向图称为AOE网。 实际问题: 如果用AOE网来表示一项工程,那么,仅仅考虑各个子工程之间的优先关系还不够,更多的是关心整个工程完成的最短时间是多少;哪些活动的延期将会影响整个工程的进度,而加速这些活动是否会提高整个工程的效率。 因此,通常在AOE网中列出完成预定工程计划所需要进行的活动,每个活动计划完成的时间,要发生哪些事件以及这些事件与活动之间的关系,从而可以确定该项工程是否可行,估算工程完成的时间以及确定哪些活动是影响工程进度的关键。 如图是一个假想的有11项活动的AOE-网: 其中有9个事件v1,v2,v3,…,v9,每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。 如v1表示整个工程开始,v9表示整个工程结束,v5表示a4和a5已经完成,a7和a8可以开始。 与每个活动相联系的数是执行该活动所需的时间。 比如,活动a1需要6天,a2需要4天等。 和AOV-网不同,对AOE-网有待研究的问题是: (1)完成整项工程至少需要多少时间 (2)哪些活动是影响工程进度的关键 关键路径 由于在AOE-网中有些活动可以并行地进行,所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和,不是路径上弧的数目)。 路径长度最长的路径叫做关键路径(CriticalPath)。 AOE网有关的概念: 1)路径长度: 路径上各个活动的持续时间之和 2)完成工程的最短时间: 由于AOE网中有活动是并行进行的,所以完成工程的最短时间就是从开始点到完成点的最长路劲长度。 3)活动最早开始时间(earlisttime)(e(i)): 从开始点到顶点vi的最长路径称为事件vi的最早发生时间。 这个时间决定了以vi为尾的弧表示的活动的最早开始时间. 4)活动最晚开始时间(latesttime)(l(i)): 在不推迟整个工程完成的前提下,活动最迟开始的时间 5)完成活动的时间余量: 该活动的最迟开始时间减去最早开始时间 6)关键路径(criticalpath): 路径长度最长的路径称为关键路径 7)关键活动(criticalactivity): 关键路径上的活动称为关键活动,关键活动的特点是: e(i)=l(i)分析关键路径的目的就是辨别在整个工程中哪些是关键活动,以便争取提高关键活动的工作效率,缩短整个工程的工期。 解决方案: 由上分析可知,辨别关键活动就是要找e(i)=l(i)的活动。 为了求得AOE-网中活动的e(i)和l(i),首先求事件的最早发生时间ve(j)和最迟发生时间vl(j)。 如果活动ai由弧 e(i)=ve(j) l(i)=vl(k)-dut( 求ve(j)和vl(j)需分两步进行: (1)从ve(0)开始向前递推 其中,T是所有以第j个顶点为头的弧的结合。 (2)从vl(n-1)=ve(n-1)起向后递推 其中,S是所有以第i个顶点为尾的弧的集合。 这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提下进行。 也就是说ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定,而vl(j-1)则必须在vj的所有后继的最迟发生时间求得之后才能确定。 因此,可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。 关键路径的算法: (1)输入e条弧 (2)从源点v0出发,令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i](1≤i≤n-1)。 如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止;否则执行步骤(3)。 (3)从汇点vn出发,令vl[n-1]=ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i](n-2≥i≥0); (4)根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。 若某条弧满足条件e(s)=l(s),则为关键活动。 先将拓扑排序算法: TopologicalOrder() CriticalPath便为求关键路径的算法: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 StatusTopologicalOrder(ALGraphG,Stack&T){ vernum-1] for(i=0;i<;++i) if(! indegree[i])Push(S,i)]=0;irstarc;p;p=p->nextarc){ k=p—>adjvex;]=ve[0..];irstarc;p;p=p->nextarc){ k=p->adjvex;dut=*(p—>info); 短路径: 最短路径问题是图研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 最短路径问题是图的又一个比较典型的应用问题。 例如,某一地区的一个公路网,给定了该网内的n个城市以及这些城市之间的相通公路的距离,能否找到城市A到城市B之间一条举例最近的通路呢 如果将城市用点表示,城市间的公路用边表示,公路的长度作为边的权值,那么,这个问题就可归结为在网图中,求点A到点B的所有路径中,边的权值之和最短的那一条路径。 这条路径就是两点之间的最短路径,并称路径上的第一个顶点为源点(Sourse),最后一个顶点为终点(Destination)。 单源点的最短路径问题: 给定带权有向图G=(V,E)和源点v∈V,求从v到G中其余各顶点的最短路径。 在下面的讨论中假设源点为v0。 解决问题的迪杰斯特拉算法: 即由迪杰斯特拉(Dijkstra)提出的一个按路径长度递增的次序产生最短路径的算法。 首先求出长度最短的一条最短路径,然后参照它求出长度次短的一条最短路径,依次类推,直到从顶点v到其它各顶点的最短路径全部求出为止。 算法的基本思想是: 设置两个顶点的集合S和T=V-S,集合S中存放已找到最短路径的顶点,集合T存放当前还未找到最短路径的顶点。 初始状态时,集合S中只包含源点v0,然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中,集合S每加入一个新的顶点u,都要修改顶点v0到集合T中剩余顶点的最短路径长度值,集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。 此过程不断重复,直到集合T的顶点全部加入到S中为止。 Dijkstra算法的实现: 首先,引进一个辅助向量D,它的每个分量D[i]表示当前所找到的从始点v到每个终点vi的最短路径的长度。 它的初态为: 若从v到vi有弧,则D[i]为弧上的权值;否则置D[i]为∞。 显然,长度为: D[j]=Min{D[i]|vi∈V} 的路径就是从v出发的长度最短的一条最短路径。 此路径为(v,vj)。 那么,下一条长度次短的最短是哪一条呢假设该次短路径的终点是vk,则可想而知,这条路径或者是(v,vk),或者是(v,vj,vk)。 它的长度或者是从v到vk的弧上的权值,或者是D[j]和从vj到vk的弧上的权值之和。 依据前面介绍的算法思想,在一般情况下,下一条长度次短的最短路径的长度必是: D[j]=Min{D[i]|vi∈V-S} 其中,D[i]或者弧(v,vi)上的权值,或者是D[k](vk∈S和弧(vk,vi)上的权值之和。 根据以上分析,可以得到如下描述的算法: (1)假设用带权的邻接矩阵edges来表示带权有向图,edges[i][j]表示弧〈vi,vj〉上的权值。 若〈vi,vj〉不存在,则置edges[i][j]为∞(在计算机上可用允许的最大值代替)。 S为已找到从v出发的最短路径的终点的集合,它的初始状态为空集。 那么,从v出发到图上其余各顶点(终点)vi可能达到最短路径长度的初值为: D[i]=edges[LocateVex(G,v)][i]vi∈V (2)选择vj,使得 D[j]=Min{D[i]|vi∈V-S} vj就是当前求得的一条从v出发的最短路径的终点。 令 S=S∪{j} (3)修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。 如果 D[j]+edges[j][k] 则修改D[k]为 D[k]=D[j]+edges[j][k] 重复操作 (2)、(3)共n-1次。 由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。 如图所示一个有向网图G8的带权邻接矩阵为: 有向网图G8的带权邻接矩阵 用C语言描述的Dijkstra算法: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortPathTable&D){ //用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权长度D[v]。 //若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。 //final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。 for(v=0;v<;++v){ final[v]=FALSE;D[v]=[v0][v]; for(w=0;w<;++w)P[v][w]=FALSE;//设空路径 if(D[v] }//for D[v0]=0;final[v0]=TRUE;//初始化,v0顶点属于S集 //开始主循环,每次求得v0到某个v顶点的最短路径,并加v到s集。 for(i=1;i<;++i){//其余个顶点 min=INFINITY;//当前所知离v0顶点的最近距离 for(w=0;w<;++w) if(! final[w])//w顶点在V-S中 if(D[w] final[v]=TRUE;//离v0顶点最近的v加入S集 for(w=0;w<;++w)//更新当前最短路径及距离 if(! final[w]&&(min+[v][w] D[w]=min+[v][w];P[w]=P[v];P[w][w]=TRUE;//P[w]=P[v]+[w] }//if }//for }//ShortestPath_DIJ 以上就是图的应用全部详细介绍,希望对大家的学习有所帮助。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 考研 数据 结构图 算法 知识点