天顺娱乐-天顺平台注册站
 
 
拓扑排序_1
来源:网络 时间:2024-02-28 00:10
播报
编辑
一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程的开始是以它的所有前序子工程的结束为先决条件的,但有些子工程没有先决条件,可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系,可用一个有向图来表示,图中的顶点代表活动(子工程),图中的有向边代表活动的先后关系,即有向边的起点的活动是终点活动的前序活动,只有当起点活动完成之后,其终点活动才能进行。通常,我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network),简称AOV网。
图3-5 这种先后关系的AOV网
例如,假定一个计算机专业的学生必须完成图3-4所列出的全部课程。在这里,课程代表活动,学习一门课程就表示进行一项活动,学习每门课程的先决条件是学完它的全部先修课程。如学习《数据结构》课程就必须安排在学完它的两门先修课程《离散数学》和《算法语言》之后。学习《高等数学》课程则可以随时安排,因为它是基础课程,没有先修课。若用AOV网来表示这种课程安排的先后关系,则如图3-5所示。图中的每个顶点代表一门课程,每条有向边代表起点对应的课程是终点对应课程的先修课。从图中可以清楚地看出各课程之间的先修和后续的关系。如课程C5的先修课为C2,后续课程为C4和C6。 [2]
一个AOV网应该是一个有向无环图,即不应该带有回路,因为若带有回路,则回路上的所有活动都无法进行。如图3-6是一个具有三个顶点的回路,由<A,B>边可得B活动必须在A活动之后,由<B,C>边可得C活动必须在B活动之后,所以推出C活动必然在A活动之后,但由<C,A>边可得C活动必须在A活动之前,从而出现矛盾,使每一项活动都无法进行。这种情况若在程序中出现,则称为死锁或死循环,是必须避免的。
在AOV网中,若不存在回路,则所有活动可排列成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,我们把此序列叫做拓扑序列(Topological order),由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的,满足上述定义的任一线性序列都称作它的拓扑序列。
由AOV网构造出拓扑序列的实际意义是:如果按照拓扑序列中的顶点次序,在开始每一项活动时,能够保证它的所有前驱活动都已完成,从而使整个工程顺序进行,不会出现冲突的情况。 [2]
播报
编辑
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之;
(2) 从网中删除此顶点及所有出边
循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列 [2]
播报
编辑
拓扑排序常用来确定一个依赖关系集中,事物发生的顺序。例如,在日常工作中,可能会将项目拆分成A、B、C、D四个子部分来完成,但A依赖于B和D,C依赖于D。为了计算这个项目进行的顺序,可对这个关系集进行拓扑排序,得出一个线性的序列,则排在前面的任务就是需要先完成的任务。
注意:这里得到的排序并不是唯一的!就好像你早上穿衣服可以先穿上衣也可以先穿裤子,只要里面的衣服在外面的衣服之前穿就行。
播报
编辑
拓扑序列 Pascal代码(无优化)
program?TopSort; var map,link:array[1..100,1..100]ofinteger; v,pnt:array[1..100]ofinteger; n,m,a,b,i,j,k:integer; begin fillchar(map,sizeof(map),0); fillchar(link,sizeof(link),0); fillchar(v,sizeof(v),0);//初始化 readln(n,m); for?i:=1?to?m?do begin?//读图 readln(a,b); map[a,b]:=1; v[b]:=v[b]+1; end; i:=0; link:=map; while?(i<n)?do begin?//开始排序 j:=1; while?(v[j]<>0)?do?inc(j); v[j]:=-1; for?k:=1?to?n?do if?link[j,k]=1?then begin dec(v[k]); link[j,k]:=0; end; inc(i); pnt[i]:=j; end; for?i:=1?to?n?do writeln(pnt[i]); end.
拓扑序列 C++(STL)核心代码
这里的代码可以参考这本书 [3],这里用了容器,感觉能看明白点。
queue<int>q; //priority_queue<int,vector<int>,greater<int>>q; //优先队列的话,会按照数值大小有顺序的输出 //此处为了理解,暂时就用简单队列 int?topo() { for(inti=1;i<=n;i++) { if(indegree[i]==0) { q.push(i); } } int?temp; while(!q.empty()) { temp=q.front();//如果是优先队列,这里可以是top() printf("%d->",temp); q.pop(); for(inti=1;i<=n;i++)//遍历从temp出发的每一条边,入度-- { if(map[temp][i]) { indegree[i]--; if(indegree[i]==0)q.push(i); } } } }
拓扑序列 Pascal代码(邻接表+队列优化)
program?topsort; type node=^link; link=record procedure?addd(x,y:longint); var?p:node; begin new(p); p^.g:=y;p^.next:=nd[x]; nd[x]:=p; inc(ru[y]); end; begin readln(n,m); for?a:=1?to?m?do begin readln(x,y); addd(x,y); end; for?a:=1?to?n?do if?ru[a]=0?then?begin inc(stk); stack[stk]:=a; end; be:=0; repeat inc(be); x:=stack[be]; p:=nd[x]; write(x,''); while?p<>nil?do begin dec(ru[p^.g]); if?ru[p^.g]=0?then?begin inc(stk); stack[stk]:=p^.g; end; p:=p^.next; end; until?be=stk; readln; end.
这里主要是将入度为零的点加入队列stack,直接在队列内扩展即可,效率为O(n+m)
播报
编辑
拓扑学是近代发展起来的一个研究连续性现象的数学分支。中文名称起源于希腊语Τοπολογ?α的音译。Topology原意为地貌,于19世纪中期由科学家引入,当时主要研究的是出于数学分析的需要而产生的一些几何问题。发展至今,拓扑学主要研究拓扑空间在拓扑变换下的不变性质和不变量。
 

联系我们

400-123-4567 仅限中国 9:00-20:00
微信二维码
Copyright © 2002-2022 天顺娱乐-天顺平台注册站 版权所有    粤IP********    

平台注册入口