考研数据结构图的必背算法及知识点

考研数据结构图的必背算法及知识点Prepared on 22 November 20201.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。

这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。

在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。

n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。

对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。

即无向连通图的生成树不是唯一的。

连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。

图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有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语言实现为：owcost中求最小值，其频度为n-1；其二是重新选择具有最小代价的边，其频度为n。

由此，普里姆算法的时间复杂度为O(n2)，与网中的边数无关，因此适用于求边稠密的网的最小生成树。

2.克鲁斯卡尔（Kruskal）:由点到线，适合边稀疏的网。

时间复杂度：O(e*lo ge)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)；键路径(AOE网)：在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度，路径长度最长的路径叫做关键路径(CriticalPath)。

网：（Activityonedgenetwork）AOE网示意图若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续的时间），则此带权的有向图称为AO E网。

实际问题：如果用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由弧<j,k>表示，其持续时间记为dut(<j,k>),则有如下关系：e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)求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条弧<j，k>，建立AOE-网的存储结构；(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便为求关键路径的算法：短路径：最短路径问题是图研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

最短路径问题是图的又一个比较典型的应用问题。

例如，某一地区的一个公路网，给定了该网内的n个城市以及这些城市之间的相通公路的距离，能否找到城市A到城市B之间一条举例最近的通路呢如果将城市用点表示，城市间的公路用边表示，公路的长度作为边的权值，那么，这个问题就可归结为在网图中，求点A到点B的所有路径中，边的权值之和最短的那一条路径。