高级数据结构2

1、JYP，1，双连接组件(6.4.2)，双连接组件对连接性的要求比一般的连接组件更高，生成双连接组件的操作更复杂。假设无向图G是连通的，双连通分量的形式定义如下。定义：G的顶点V是一个连接点。当且仅当从G中删除V及其相关边时，剩余图至少有两个连通分量。例如，JYP，2，在下面的连通图G6中，顶点1、4和7是连接点。定义：双连通图是没有连接点的连通图。例如，图G5是双连接的：JYP，4，但是图G6不是双连接的。在通信网络图中，边代表通信链路，顶点代表通信站，关节明显是弱链路。定义：连通图G的双连通分量是图G的最大双连通子图，JYP，5，图G6包含四个双连通分量，如下所示：JYP，6，不难发现同一图

2、的两个双连通分量最多有一个公共顶点。可以推断，一条边不能出现在两个或更多的双连通分量中。因此，图G的二部分被分成E(G)。图G的双连通分量可以通过图G的任何深度最优教师树形成来获得，JYP，7，以及图G6，其根是顶点0，如下所示：JYP，8，其中非树边缘由虚线表示。顶点旁边的数字称为顶点的深度优先数，简称为dfn。顶点的dfn表示在深度优先搜索中访问顶点的顺序。例如，在前一个G6生成树中，dfn(0)=1，dfn(1)=2，dfn(7)=5。请注意，在深层最佳教师树中，如果顶点u是v的祖先，则dfn(u) dfn(v)。JYP，9，与生成树t相比，当且仅当u是v的祖先或v是u的祖先时，非树边(

3、u，v)是后边。例如，(4，1)和(6，7)是后边缘。不是后边缘的非树边缘称为水平边缘。根据深度优先搜索定律，与任何图形的任何深度相比，图形不可能有水平边。因此，10岁的JYP，如果至少有两个孩子，那么作为一名优秀教师的根就有必要也有足够的理由成为一个连接点。任何其他顶点u成为连接点的充要条件是u至少有一个子w，这使得通过仅由w、w的后代和返回边组成的路径到达u的祖先是不可能的，因为删除顶点u及其相关的边将使w及其后代与u的祖先断开连接。JYP，11，假设顶点w的祖先包括w本身。为了表示一个顶点可以通过它的后代和一个后边缘到达的最高祖先，对于图G的每个顶点W，low(w)被定义为可以通过它的后

4、代和一个后边缘从W到达的最高祖先的dfn。很明显，low(w)是从w通过其子代和后沿可以到达的dfn中最低的，并且可以通过以下公式计算：low(w)=min dfn(w)，min low(x)| x是w的子代，min dfn(x)| (w，x)是后沿，JYP，12以下是在G6的以顶点0为根的深度最优树中每个顶点的dfn和低值：JYP，13。通过修改DFS，可以获得用于计算连通图的每个顶点的dfn和低值的函数dfnlow:虚图：3360 dfnlow(常数int x)/DFS num=1在顶点x的开始处；/num是类型为int的图形的数据成员dfn=新int n；低=新国际号码；/dfn和low

5、都是Graph的数据成员，其/类型为int * for(int I=0；I n；I)dfni=lowi=0；DfnLow (x，-1)；/x是根，其父是伪顶点-1删除dfn删除low，jyp，14，void graph :dfnlow (int u，int v)/搜索深度首先从u和/计算dfn和low。v是u dfnu=lowu=num的父级；对于(与u相邻的每个顶点w)/如果(dfnw=0) /w是未访问的顶点DfnLow (w，u)，则特定代码与图的表示有关；lowu=min2 (lowu，loww)；/min2(x，y)返回x和y/else if (w！=v) lowu=min2 (lo

6、wu，dfnw)；/回到边缘。注/这意味着(v，u)不是后沿，JYP，15岁。请注意，如果v是u的父代，则(u，v)不能是后沿。函数DfnLow(u，v)的参数v旨在区分这种情况。深度优先搜索的第一个顶点x没有父顶点，因此它的调用形式是DfnLow(x，1)。函数DfnLow(u，v)使用的另一个函数min2返回两个参数中较小的一个。JYP，16，在DfnLow的基础上进一步处理后，连通图的边可以分成双连通分量。请注意，当DfnLow(w，u)返回时，loww已被计算。如果为lowwdfnu，则可以确定新的双连接组件。双连通分量的所有边都可以通过在堆栈中存储第一个遇到的边来获得。JYP，17，

7、让深度优先搜索中最近访问的顶点是u，并且顶点w与u相邻，但不是u的直接父代，那么在以下两种情况下，(u，w)是第一个遇到的边：(1)w是未访问的顶点(2)w是已经访问的顶点和u的祖先，因为未访问的顶点的dfn值初始化为0，所以祖先的dfn值小于后代的dfn值。JYP，18，注意：如果dfnw为dfnu，则边(w，u)必须作为后边(当在w点时)添加到堆栈中，如下所示：u，x，w，2，3，4，JYP，19，双连接函数实现上述过程：void dfn=new intn低=新国际号码；对于(int I=0；一. 1 .dfnu=lowu=num，JYP，20，对于(与u相邻的每个顶点w)/具体的代码与图

8、if (v！=w /后沿/表示结束，JYP，21，双连接时间复杂度为0(n e)。请注意，双连通函数假设输入连通图至少有两个顶点。只有一个顶点的连通图是无限的，但根据定义，它们也是双连通的。这可以特别处理。JYP，22岁，求解最小生成树的Prim算法(6.5.2)，假设TV是所选顶点的集合，t是最小生成树的所选边的集合。Prim算法首先在图G中选择一个顶点U，并将U添加到TV中。然后将成本最低的边(u，v)加到T上，这样T (u，v)仍然是一棵树。重复上述步骤，直到t包含n 1条边。请注意，与(u，v)相关的两个顶点必须一个在电视中，另一个不在电视中。JYP，23岁，普里姆算法的帧：电视=0；

9、/从顶点0开始，假设g至少有一个顶点(T=；t包含少于n -1条边；把(u，v)加到(t)上，使(u，v)成为一条满足电视需求的、电视成本最低的边；如果(没有这样的边缘)断裂；给电视添加视频；如果(T包含少于n-1条边)结束“没有最小生成树”；JYP，24岁，下图中用Prim算法构造最小生成树的过程：JYP，25岁，JYP，26岁，JYP，27岁，JYP，28岁，让它成为不属于TV的顶点集。对于任何v，将nearv定义为电视中最小化成本的顶点(nearv，v)(如果(v，w)E，让成本(v，w)=)，然后成本(nearv，v)=。下一台电视的顶点v应该满足：v和成本(近v，v)=。下一个增加t

10、的边自然是(nearv，v)。JYP，29，设w为v in的顶点。顶点v加入电视后，如果成本(nearw，w)成本(v，w)，则nearw变为v。如果图G由邻接矩阵costij表示，算法的时间复杂度为0(N2)，因为算法总共选择了n 1个顶点，并且只需要0(n)个时间来选择每个顶点V并处理V对Nearw(其中W和V是相邻的)的影响。JYP，30，如果图g由邻接表表示并且使用斐波那契堆，算法的性能会更好。对于v，distv=cost(nearv，v)被定义为从顶点v到构造的部分最小生成树的最近距离。每次将顶点添加到电视时，算法需要确定顶点v，以便v和distv=。这对应于上的删除最小元素操作。当

11、v被添加到电视时，与v in相邻的顶点的距离值可能会减小。这对应于上的关键字缩减操作。JYP，31岁，关键字缩减操作的总数最多是图形中的边数。删除最小元素的操作总数是n 1。最初，有n 1个顶点。如果dist被用作关键字，并且组织是Fibonacci堆，则需要n 1个插入操作来初始化Fibonacci堆。然后，需要执行n 1次删除最小元素和最多E次关键词缩减。所有这些操作的成本是每个操作的分摊成本的总和，即O(n log n e)。因此，该算法的时间复杂度变成了0。当e比n2小得多时，这显然是一种改进。斐波那契堆在最短路径算法中的应用，首先回忆经典的最短路径算法：1空图：3360最短路径(常数

12、int n，常数int v) 2为(int I=0；I n；i ) 3 si=假；disti=lengthvi4 if (i！=v，JYP，33，10表示(int w=0；w n；w ) 11 if(！SW)12 if(distu length uw distw)distw=distu length uw；path w=u；13/(I=0；)结束14，jyp，34，分析：第2行中的for循环需要0(n)时间。第7行中的for循环执行n次，每次选择第8行并更新第10至12行中的dist值需要0(n)个时间。因此，该循环的总时间为0(N2)。整个算法的时间为0(N2)。即使使用邻接表，行10到12

13、的总时间也可以减少到0(e)(因为只有与U的顶点相邻的距离可以改变)，并且行8的总时间仍然是0(N2)。JYP，35，算法的时间复杂度可以通过使用斐波那契堆和邻接表降低到0(n log n e)。每次迭代，我们需要确定顶点u，以便u和distu=。这对应于上的删除最小元素操作。随着u被加到s上，与u相邻的顶点的距离值可能会减小。这对应于上的关键字缩减操作。36岁的JYP最初包含n 1个顶点。如果dist被用作关键字，并且组织是Fibonacci堆，则需要n 1个插入操作。然后，需要执行n 2次删除最小元素和最多E次关键词缩减。所有这些操作的成本是每个操作的分摊成本的总和，即O(n log n

14、e)。因此，该算法的时间复杂度为0。当e比n2小得多时，这种实现显然更好。调查问题：P223 23(每个学生独立完成并提交一份报告作为本课程的主要成绩因素)，JYP，37，基于链表和映射表的排序结果排序(7.8)。对于基于链表的结果排序，有时需要在本地重新排列它们，以使它们在物理上是连续的。让我们假设记录表r0，rn-1的排序结果是一个按照关键字的非递减顺序链接的链表，并且首先是链表的第一个记录指针。R0和Rfirst的交换将被记录。如果第一个值为0，则表中应该有一个链接字段值为0的记录Rx。如果Rx的链接字段可以被修改为指向最初位于R0中的记录的第一个新位置，那么剩余的记录R1、RN-1也以

15、关键字的非递减顺序被链接。JYP，38岁，但是在单链表中，我们不能快速确定节点R0的前身Rx。因此，R0的链接字段可以设置为first，表示原来位于R0的记录已经移动到Rfirst。这样，R0也充当了R1的虚拟节点，rn-1链表。有了这个虚拟节点，我们可以找到剩余记录链表的第一个节点。重复上述过程n1次以完成重排。通常，假设记录表r0、Ri-1已经以物理顺序排列，并且Rfirst是剩余记录Ri、rn-1的链表中的第一个记录。在记录ri和Rfirst被交换后，新的ri记录的链接字段被设置为first，表示最初位于Ri的记录已经移动到Rfirst。39岁的JYP。同时，注意，第一，即剩余记录的链表的第一记录索引ri，rn-1，总是大于或等于I。我们可以通过虚拟节点找到剩余记录的链表的第一记录索引。函数列表实现上述方法：模板空列表(element * list，const int n，int first)/对链表中由first指向的记录进行重新排序，使list0，list n-1/中的关键字按(int I=0；I n1；/找到应该放在位置I的记录.由于位置0、1和1-1处的记录已经/就位，记录索引必须为1，同时(第一个1)第一个=列表第一。链接；/通过虚拟节点，JY