拓扑排序数据结构的课程设计-拓扑排序的算法

拓扑排序  时间:2021-08-09  阅读:()

数据结构拓扑排序有哪几种序列?

拓扑排序序列有6种。

先找到第一个没有被指的,就是C1,加入序列。

然后擦掉跟C1有关的边,此时C2和C3都满足没有被指,选一个,比如选C2,加入序列,擦掉和C2有关的边,这个时候可以选C3,C4,C5或C6,如此而已。

数据结构拓扑排序实际上是离散数学中的概念。

这里不打算说太多形式化的定义,形式化的定义教科书上或者上面给的链接中就说的很详细。

还是以上面选课的例子来描述这两个概念。

假设我们在学习完了算法这门课后,可以选修机器学习或者计算机图形学。

这个或者表示,学习机器学习和计算机图形学这两门课之间没有特定的先后顺序。

因此,在我们所有可以选择的课程中,任意两门课程之间的关系要么是确定的(即拥有先后关系),要么是不确定的(即没有先后关系),绝对不存在互相矛盾的关系(即环路)。

以上就是偏序的意义,抽象而言,有向图中两个顶点之间不存在环路,至于连通与否,是无所谓的。

所以,有向无环图必然是满足偏序关系的。

理解了偏序的概念,那么全序就好办了。

所谓全序,就是在偏序的基础之上,有向无环图中的任意一对顶点还需要有明确的关系(反映在图中,就是单向连通的关系,注意不能双向连通,那就成环了)。

可见,全序就是偏序的一种特殊情况。

回到我们的选课例子中,如果机器学习需要在学习了计算机图形学之后才能学习(可能学的是图形学领域相关的机器学习算法……),那么它们之间也就存在了确定的先后顺序,原本的偏序关系就变成了全序关系。

? 实际上,很多地方都存在偏序和全序的概念。

比如对若干互不相等的整数进行排序,最后总是能够得到唯一的排序结果(从小到大,下同)。

这个结论应该不会有人表示疑问吧:)但是如果我们以偏序/全序的角度来考虑一下这个再自然不过的问题,可能就会有别的体会了。

拓展到拓扑排序中,结果具有唯一性的条件也是其所有顶点之间都具有全序关系。

如果没有这一层全序关系,那么拓扑排序的结果也就不是唯一的了。

在后面会谈到,如果拓扑排序的结果唯一,那么该拓扑排序的结果同时也代表了一条哈密顿路径。

拓扑排序的应用

一个复杂的工程通常可以分解成一组小任务的集合,完成这些小任务意味着整个工程的完成。

例如,汽车装配工程可分解为以下任务:将底盘放上装配线,装轴,将座位装在底盘上,上漆,装刹车,装门等等。

任务之间具有先后关系,例如在装轴之前必须先将底板放上装配线。

任务的先后顺序可用有向图表示——称为顶点活动( Activity On Vertex, AOV)网络。

有向图的顶点代表任务,有向边(i, j) 表示先后关系:任务j 开始前任务i 必须完成。

图1 - 4显示了六个任务的工程,边( 1 , 4)表示任务1在任务4开始前完成,同样边( 4 , 6)表示任务4在任务6开始前完成,边(1 , 4)与(4 , 6)合起来可知任务1在任务6开始前完成,即前后关系是传递的。

由此可知,边(1 , 4)是多余的,因为边(1 , 3)和(3 , 4)已暗示了这种关系。

在很多条件下,任务的执行是连续进行的,例如汽车装配问题或平时购买的标有“需要装配”的消费品(自行车、小孩的秋千装置,割草机等等)。

我们可根据所建议的顺序来装配。

在由任务建立的有向图中,边( i, j)表示在装配序列中任务i 在任务j 的前面,具有这种性质的序列称为拓扑序列ological ological sequences)。

根据任务的有向图建立拓扑序列的过程称为拓扑排序ological sorting)。

图1 - 4的任务有向图有多种拓扑序列,其中的三种为1 2 3 4 5 6,1 3 2 4 5 6和2 1 5 3 4 6,序列1 4 2 3 5 6就不是拓扑序列,因为在这个序列中任务4在3的前面,而任务有向图中的边为( 3 , 4),这种序列与边( 3 , 4)及其他边所指示的序列相矛盾。

可用贪婪算法来建立拓扑序列。

算法按从左到右的步骤构造拓扑序列,每一步在排好的序列中加入一个顶点。

利用如下贪婪准则来选择顶点:从剩下的顶点中,选择顶点w,使得w 不存在这样的入边( v,w),其中顶点v 不在已排好的序列结构中出现。

注意到如果加入的顶点w违背了这个准则(即有向图中存在边( v,w)且v 不在已构造的序列中),则无法完成拓扑排序,因为顶点v 必须跟随在顶点w 之后。

贪婪算法的伪代码如图1 3 - 5所示。

while 循环的每次迭代代表贪婪算法的一个步骤。

现在用贪婪算法来求解图1 - 4的有向图。

首先从一个空序列V开始,第一步选择V的第一个顶点。

此时,在有向图中有两个候选顶点1和2,若选择顶点2,则序列V = 2,第一步完成。

第二步选择V的第二个顶点,根据贪婪准则可知候选顶点为1和5,若选择5,则V = 2 5。

下一步,顶点1是唯一的候选,因此V = 2 5 1。

第四步,顶点3是唯一的候选,因此把顶点3加入V 得到V = 2 5 1 3。

在最后两步分别加入顶点4和6 ,得V = 2 5 1 3 4 6。

1. 贪婪算法的正确性 为保证贪婪算法算的正确性,需要证明: 1) 当算法失败时,有向图没有拓扑序列; 2) 若 算法没有失败,V即是拓扑序列。

2) 即是用贪婪准则来选取下一个顶点的直接结果, 1) 的证明见定理1 3 - 2,它证明了若算法失败,则有向图中有环路。

若有向图中包含环qj qj + 1.qk qj , 则它没有拓扑序列,因为该序列暗示了qj 一定要在qj 开始前完成。

定理1-2 如果图1 3 - 5算法失败,则有向图含有环路。

证明注意到当失败时| V |<n, 且没有候选顶点能加入V中,因此至少有一个顶点q1 不在V中,有向图中必包含边( q2 , q1)且q2 不在V中,否则, q1 是可加入V的候选顶点。

同样,必有边(q3 , q2)使得q3 不在V中,若q3 = q1 则q1 q2 q3 是有向图中的一个环路;若q3 ≠q1,则必存在q4 使(q4 , q3)是有向图的边且q4 不在V中,否则,q3 便是V的一个候选顶点。

若q4 为q1 , q2 , q3 中的任何一个,则又可知有向图含有环,因为有向图具有有限个顶点数n,继续利用上述方法,最后总能找到一个环路。

2. 数据结构的选择 为将图1 - 5用C + +代码来实现,必须考虑序列V的描述方法,以及如何找出可加入V的候选顶点。

一种高效的实现方法是将序列V用一维数组v 来描述的,用一个栈来保存可加入V的候选顶点。

另有一个一维数组I n D e g r e e,I n D e g r e e[ j ]表示与顶点j相连的节点i 的数目,其中顶点i不是V中的成员,它们之间的有向图的边表示为( i, j)。

当I n D e g r e e[ j ]变为0时表示j 成为一个候选节点。

序列V初始时为空。

I n D e g r e e[ j ]为顶点j 的入度。

每次向V中加入一个顶点时,所有与新加入顶点邻接的顶点j,其I n D e g r e e[ j ]减1。

对于有向图1 - 4,开始时I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 3 , 1 , 3 ]。

由于顶点1和2的I n D e g r e e值为0,因此它们是可加入V的候选顶点,由此,顶点1和2首先入栈。

每一步,从栈中取出一个顶点将其加入V,同时减去与其邻接的顶点的I n D e g r e e值。

若在第一步时从栈中取出顶点2并将其加入V,便得到了v [ 0 ] = 2,和I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 2 , 0 , 3 ]。

由于I n D e g r e e [ 5 ]刚刚变为0,因此将顶点5入栈。

程序1 3 - 2给出了相应的C + +代码,这个代码被定义为N e t w o r k的一个成员函数。

而且,它对于有无加权的有向图均适用。

但若用于无向图(不论其有无加权)将会得到错误的结果,因为拓扑排序是针对有向图来定义的。

为解决这个问题,利用同样的模板来定义成员函数AdjacencyGraph, AdjacencyWGraph,L i n k e d G r a p h和L i n k e d W G r a p h。

这些函数可重载N e t w o r k中的函数并可输出错误信息。

如果找到拓扑序列,则Topological 函数返回t r u e;若输入的有向图无拓扑序列则返回f a l s e。

当找到拓扑序列时,将其返回到v [ 0 :n- 1 ]中。

3. Network:Topological 的复杂性 第一和第三个f o r循环的时间开销为(n )。

若使用(耗费)邻接矩阵,则第二个for 循环所用的时间为(n2 );若使用邻接链表,则所用时间为(n+e)。

在两个嵌套的while 循环中,外层循环需执行n次,每次将顶点w 加入到v 中,并初始化内层while 循环。

使用邻接矩阵时,内层w h i l e循环对于每个顶点w 需花费(n)的时间;若利用邻接链表,则这个循环需花费dwout 的时间,因此,内层while 循环的时间开销为(n2 )或(n+e)。

所以,若利用邻接矩阵,程序1 3 - 2的时间复杂性为(n2 ),若利用邻接链表则为(n+e)。

程序13-2 拓扑排序 bool Network::Topological(int v[]) {// 计算有向图中顶点的拓扑次序 // 如果找到了一个拓扑次序,则返回t r u e,此时,在v [ 0 : n - 1 ]中记录拓扑次序 // 如果不存在拓扑次序,则返回f a l s e int n = Ve r t i c e s ( ) ; // 计算入度 int *InDegree = new int [n+1]; InitializePos(); // 图遍历器数组 for (int i = 1; i <= n; i++) // 初始化 InDegree[i] = 0; for (i = 1; i <= n; i++) {// 从i 出发的边 int u = Begin(i); while (u) { I n D e g r e e [ u ] + + ; u = NextVe r t e x ( i ) ; } } // 把入度为0的顶点压入堆栈 LinkedStack<int> S; for (i = 1; i <= n; i++) if (!InDegree[i]) S.Add(i); // 产生拓扑次序 i = 0; // 数组v 的游标 while (!S.IsEmpty()) {// 从堆栈中选择 int w; // 下一个顶点 S . D e l e t e ( w ) ; v[i++] = w; int u = Begin(w); while (u) {// 修改入度 I n D e g r e e [ u ] - - ; if (!InDegree[u]) S.Add(u); u = NextVe r t e x ( w ) ; } } D e a c t i v a t e P o s ( ) ; delete [] InDegree; return (i == n); }

数据结构的课程设计-拓扑排序的算法

#include<stdio.h> int mat[105][105];/*存图的边*/ int indeg[105];/*存入度*/ int ans[105];/*结果*/ =0; void main() { int n;/*图大小*/ int m;/*边个数*/ int i,j; int a,b; scanf("%d%d",&n,&m); for(i=0;i<n;++i)indeg[i]=0; for(i=0;i<m;++i) { scanf("%d%d",&a,&b); /*a到b有一条边,输入范围[0,n-1]*/ indeg[b]++; mat[a][b]=1; } <n) { for(i=0;i<n;++i) if(indeg[i]==0) { indeg[i]=-1; break; } j=i; ++]=j; for(i=0;i<n;++i) if(mat[j][i]) mat[j][i]=0,--indeg[i]; } for(i=0;i&;++i) printf("%d ",ans[i]); puts(""); }

RackNerd新上圣何塞、芝加哥、达拉斯、亚特兰大INTEL系列,$9.49/年

racknerd怎么样?racknerd商家最近促销三款美国便宜vps,最低只需要9.49美元,可以选择美国圣何塞、西雅图、纽约和芝加哥机房。RackNerd是一家成立于2019年的美国高性价比服务器商家,主要从事美国和荷兰数据中心的便宜vps、独立服务器销售!支持中文工单、支持支付宝和微信以及PayPal付款购买!点击直达:racknerd官方网站INTEL系列可选机房:加利福尼亚州圣何塞、芝加...

Pacificrack:新增三款超级秒杀套餐/洛杉矶QN机房/1Gbps月流量1TB/年付仅7美刀

PacificRack最近促销上瘾了,活动频繁,接二连三的追加便宜VPS秒杀,PacificRack在 7月中下旬已经推出了五款秒杀VPS套餐,现在商家又新增了三款更便宜的特价套餐,年付低至7.2美元,这已经是本月第三波促销,带宽都是1Gbps。PacificRack 7月秒杀VPS整个系列都是PR-M,也就是魔方的后台管理。2G内存起步的支持Windows 7、10、Server 2003\20...

HostYun(月18元),CN2直连香港大带宽VPS 50M带宽起

对于如今的云服务商的竞争着实很激烈,我们可以看到国内国外服务商的各种内卷,使得我们很多个人服务商压力还是比较大的。我们看到这几年的服务商变动还是比较大的,很多新服务商坚持不超过三个月,有的是多个品牌同步进行然后分别的跑路赚一波走人。对于我们用户来说,便宜的服务商固然可以试试,但是如果是不确定的,建议月付或者主力业务尽量的还是注意备份。HostYun 最近几个月还是比较活跃的,在前面也有多次介绍到商...

拓扑排序为你推荐
网页图片显示不出来本地保存的网页,再打开图片显示不出来怎么办aftereffectafter effect (AE)有哪几层,层有哪些属性?作用是什么?订单详情在淘宝上买东西,显示订单已发货,但是没有订单详情。可能有几种原因?巴西时区巴西和中国的时差是多少 里约和北京时差怎么算replacewithjquery中replaceall和replacewith的区别wizardry哈利波特里的蛇院,狮院,獾院,鹰院. 分别指什么网站维护收费网站建设及维护需要多少钱?刷荣誉怎么刷荣誉最快的途径是什么?平均数计算器计算器算平均数怎么按啊?从零开始学android从零开始学android,是参加培训机构好还是买教程自学好呢?
高防服务器租用qy 网站域名备案 域名备案流程 万网域名证书查询 高防dns koss 搜狗抢票助手 网站实时监控 亚洲小于500m php空间推荐 网络空间租赁 福建铁通 重庆双线服务器托管 33456 网购分享 太原联通测速 美国凤凰城 免费asp空间 测速电信 服务器托管价格 更多