一个有向无环图的拓扑排序序列是唯一的么

发布网友发布时间：2022-05-10 03:03

共3个回答

热心网友时间：2022-04-18 06:22

AOV网络构造的拓扑序列的拓扑排序算法主要通过以下两个步骤循环，直到没有度为0的顶点，选择度为0的顶点，输出，从网络中删除这个顶点和所有向外的边。

在循环结束时，如果输出的顶点数小于网络中的顶点数，则会输出“loop”信息，否则，输出顶点序列就是拓扑序列。

利用AOV网络构建拓扑序列的实际意义是：如果按照拓扑序列的顶点顺序，在启动每个活动时，可以保证其所有前体活动都已完成，从而使整个项目有序进行，不会产生冲突。

扩展资料：

拓扑排序是一个DAG（有向无环图）的所有顶点的线性序列。序列必须满足以下两个条件：每个顶点只出现一次。如果从顶点A到顶点B有一条路径，那么在序列中顶点A出现在顶点B之前。

拓扑排序通常用于确定事物在一组依赖项中发生的顺序。例如，在日常工作中，一个项目可能分为A，B，C和D，但取决于B和D和C取决于D计算项目的顺序，关系集可以拓扑排序产生一个线性序列，和第一个任务是需要首先完成。

参考资料：百度百科-拓扑序列

热心网友时间：2022-04-18 07:40

不是很简单的一个反例
三个顶点 1,2,3
两条边 1->3,2->3

1，2，3跟2,1,3都是合法的拓扑排序

热心网友时间：2022-04-18 09:15

不是,这要取决于图的构成