| AOV网络、拓扑排序、拓扑序列 | 您所在的位置：网站首页 › aov是一种有向无环图 › AOV网络、拓扑排序、拓扑序列 |
AOV网络、拓扑排序、拓扑序列
|
AOV网络
AOV网是有向图的一类应用，在AOV网中，用顶点表示某个有一定规模的“工程”里的不同活动，用图中的边表示各项活动之间的先后顺序关系。一种常见的AOV网实例是大学课程的先修关系，以下表格列出了计算机专业若干课程及其先修课程： 课程编号课程名称先修课程C1高等数学 C2程序设计基础 C3数据结构C1，C2C4离散数学C1C5普通物理C1C6编译原理C2，C3，C4C7计算机原理C3，C4，C5C8操作系统C3，C4，C6C9数据库原理C3，C7，C8C10计算机网络C4，C7，C8对应的AOV网络为：
可以把AOV网络里的有向边看作一种“顺序”关系。拓扑排序问题就是问，在一个AOV网里的活动能否排成一种全序。 设G是一个具有n个顶点的有向无环图，图中的顶点序列v1、v2、...、vn，称为一个拓扑序列，当且仅当该顶点序列满足下面的条件，若vi, vj之间有边直接相连，则在序列中 vi 必须排在 vj 之前。构造拓扑序列的过程称为拓扑排序。 显然一个AOV网存在拓扑序列，当且仅当它不存在回路。一个存在拓扑序列的AOV网络的拓扑序列不唯一。 下面两个序列都是上图AOV网络的拓扑序列： C1,C2,C3,C4,C5,C6,C7,C8,C9,C10 C2,C1,C4,C3,C6,C8,C5,C7,C10,C9 拓扑排序算法任何无回路AOV网N都可以做出拓扑序列，方法很简单： 从中选出一个入度为0的顶点作为序列的下一顶点。从N网中删除所选顶点及其所有的出边。反复执行上面两步操作，直到已经选出了图中的所有顶点，或者再也找不到入度非0的顶点时算法结束。如果剩下入度非0的顶点，就说明中有回路，不存在拓扑序列。 拓扑排序算法的python实现顶点之间的制约关系决定了顶点的入度。入度是一个整数，用一个整数表就能记录所有顶点的入度。下面算法里用一个表indegree，以顶点为下标。初始时，将表中各元素设置为对应的图中顶点的入度。在随后的计算中，一旦选中一个顶点，就可以根据其出边的情况将其邻接点的入度分别减1。 这里又出现了另一问题：工作中需要反复找出入度为0的顶点。通过扫描indegree的方法，需要花费线性时间，效率低。实际上，只有入度减1操作有可能把顶点的入度变成0，如果这时记下这种顶点，后面需要顶点时就可以直接取用了。 为了处理这类情况，人们提出了一种技巧：在indegree里维持一个“0度表"，表中记录当时已知的所有入度为0但还没有处理的顶点。具体做法是：用一个变量zerov记录“第一个"入度为0的顶点的下标；用表元素indegree[zerov]记录下一个入度为0的顶点的 下标；如此类推。如果最后一个入度为0的顶点的下标是v,就在indegree[v]中存入-1，表示“0度表"到此结束。 这个“0度表"就像在indegree里保存了一个顶点栈：变量zer记录栈顶的位置（下标），-1表示栈结束。如果发现新的0度顶点，例如v，就把当时的zerov值存入indegree[v]，然后把v存入zerovo这相当于将v入栈。如果要选一个0度元素，就用zerov的值，并把zerov修改为indegree[zerov]的值（对应于栈元素的弹出）。 函数topological_sort的基本工作过程是： 确定所有顶点的入度存入indegree，用0度表记录其中入度为0的顶点。反复选择入度为0的顶点并维护0度表。最后返回拓扑序列，失败（无拓扑序列）时返回False def toposort(graph): vnum=graph.vertex_num() indegree,toposeq=[0]*vnum,[] zerov=-1 for vi in range(vnum): #建立初始的入度表 for v,w in graph.out_edges(vi): indegree[v]+=1 for vi in range(vnum): #建立初始的0度表 if indegree[vi]==0: indegree[vi]=zerov zerov=vi for n in range(vnum): if zerov==-1: #没有入度为0的节点，不存在拓扑序列 return False vi=zerov #从0度表弹出顶点vi zerov=indegree[zerov] toposeq.append(vi) #把一个vi加入拓扑序列 for v,w in graph.out_edges(vi): #检查vi的出边 indegree[v]-=1 if indegree[v]==0: indegree[v]=zerov zerov=v return toposeq
|
【本文地址】