生活
拓扑序列 、拓扑序列怎么算
2023-04-08 01:45  浏览:41

什么叫拓扑排序

拓扑排序(Topological Sort)

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若u,v ∈E(G),则u在线性序列中出现在v之前。

通常,这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列,简称拓扑序列。

注意:

①若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的。

②若图中存在有向环,则不可能使顶点满足拓扑次序。

③一个DAG的拓扑序列通常表示某种方案切实可行。

【例】一本书的作者将书本中的各章节学习作为顶点,各章节的先学后修关系作为边,构成一个有向图。按有向图的拓扑次序安排章节,才能保证读者在学习某章节时,其预备知识已在前面的章节里介绍过。

④一个DAG可能有多个拓扑序列。

【例】对图G9进行拓扑排序,至少可得到如下的两个(实际远不止两个)拓扑序列:C0,C1,C2,C4,C3,C5,C7,C8,C6和C0,C7,C9,C1,C4,C2,C3,C6,C5。

⑤当有向图中存在有向环时,拓扑序列不存在

【例】下面(a)图中的有向环重排后如(b)所示,有向边v3,vl和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划,则找不到该图的拓扑序列(即含有向环),就意味着该方案或计划是不可行的。

无前趋的顶点优先的拓扑排序方法

该方法的每一步总是输出当前无前趋(即人度为零)的顶点,其抽象算法可描述为:

NonPreFirstTopSort(G){//优先输出无前趋的顶点

while(G中有人度为0的顶点)do{

从G中选择一个人度为0的顶点v且输出之;

从G中删去v及其所有出边;

}

if(输出的顶点数目|V(G)|)

//若此条件不成立,则表示所有顶点均已输出,排序成功。

Error("G中存在有向环,排序失败!");

}

对G9执行上述算法的执行过程【参见动画演示】和得到的拓扑序列是C0,C1,C2,C4,C3,C5,C7,C9,C6。

注意:

无前趋的顶点优先的拓扑排序算法在具体存储结构下,为便于考察每个顶点的人度,可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空间,可设一个栈或队列暂存所有入度为零的顶点:

在开始排序前,扫描对应的存储空间,将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时,只需做出栈(队)操作即可。

什么是拓扑序列?

1,2,3,4,5,6,7

1,2,3,5,6,7,4

1,3,2,4,5,6,7

拓扑序列就是从没有箭头指的那个开始,下一个必须也没有被箭头指(这个叫什么不记得了)。。

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

拓扑排序序列有6种。先找到***个没有被指的,就是C1,加入序列。然后擦掉跟C1有关的边,此时C2和C3都满足没有被指,选一个,比如选C2,加入序列,擦掉和C2有关的边,这个时候可以选C3,C4,C5或C6,如此而已。

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

这里不打算说太多形式化的定义,形式化的定义教科书上或者上面给的链接中就说的很详细。还是以上面选课的例子来描述这两个概念。假设我们在学习完了算法这门课后,可以选修机器学习或者计算机图形学。这个或者表示,学习机器学习和计算机图形学这两门课之间没有特定的先后顺序。

因此,在我们所有可以选择的课程中,任意两门课程之间的关系要么是确定的(即拥有先后关系),要么是不确定的(即没有先后关系),绝对不存在互相矛盾的关系(即环路)。以上就是偏序的意义,抽象而言,有向图中两个顶点之间不存在环路,至于连通与否,是无所谓的。所以,有向无环图必然是满足偏序关系的。

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

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

实际上,很多地方都存在偏序和全序的概念。比如对若干互不相等的整数进行排序,最后总是能够得到唯一的排序结果(从小到大,下同)。这个结论应该不会有人表示疑问吧:)但是如果我们以偏序/全序的角度来考虑一下这个再自然不过的问题,可能就会有别的体会了。

拓展到拓扑排序中,结果具有唯一性的条件也是其所有顶点之间都具有全序关系。如果没有这一层全序关系,那么拓扑排序的结果也就不是唯一的了。在后面会谈到,如果拓扑排序的结果唯一,那么该拓扑排序的结果同时也代表了一条哈密顿路径。

拓扑序列的介绍就聊到这里吧,感谢你花时间阅读本站内容,更多关于拓扑序列怎么算、拓扑序列的信息别忘了在本站进行查找喔。

发表评论
0评