拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧<v，w>或存在从顶点v到w的路径则在该有向图的任一拓扑序列中，v一定在w之前。下面有向图的拓扑序列是

根据定义，拓扑序列中任一顶点的入度都为0，因此可以先找到入度为0的顶点。在下面的有向图中，入度为0的顶点有A和B。我们可以先将A和B加入拓扑序列中，并删除它们的出边。此时C和D的入度都为0，可以将它们加入拓扑序列中并删除它们的出边。最后，E的入度为0，将其加入拓扑序列中并删除其出边。因此，一个可能的拓扑序列是ABCD、ABDC、BACD、BADC、BCAD、BDAC。

A---->C---->E
 \        /
  \      /
   -->B--
       |
       v
       D

相关问题

使用DFS遍历一个无环有向图，退出时输出相应顶点，得到的顶点序列是拓扑有序吗

对于一个无环有向图，使用深度优先搜索（DFS）进行遍历，退出时输出的顶点序列是拓扑有序的。

拓扑排序是对有向无环图（DAG）的顶点进行线性排序，使得对于任何一条有向边 (u, v)，顶点 u 都排在顶点 v 的前面。拓扑排序可以用来解决很多实际问题，如任务调度、依赖关系等。

在使用DFS遍历无环有向图的过程中，我们可以利用递归的方式，在访问一个顶点时，首先访问其所有的邻接顶点，直到没有未被访问的邻接顶点为止。然后将当前顶点加入到结果序列中。由于在无环有向图中不存在回路，因此我们可以保证在遍历过程中不会出现后退的情况。

因此，使用DFS遍历无环有向图并在退出时输出相应顶点，得到的顶点序列是拓扑有序的。

如果从有向图 G 的每一点均能通过深度优先搜索遍历到所有其它顶点，那么该图一定不存在拓扑序列。

这个结论是不正确的。事实上，如果有向图 G 的每个顶点都可以通过深度优先搜索遍历到所有其他顶点，那么该图一定存在拓扑序列。

拓扑排序是一种将有向无环图（DAG）中的顶点进行排序的算法，使得对于任意一条有向边 (u, v)，在排序后的序列中顶点 u 都排在顶点 v 的前面。如果一个 DAG 存在拓扑序列，那么它一定是 DAG 的一个线性序列。

如果一个 DAG 中每个顶点都可以通过深度优先搜索到达所有其他顶点，那么这个 DAG 一定是强连通的。在这种情况下，我们可以使用 Kosaraju 算法计算出强连通分量，并将每个强连通分量缩成一个点，这样得到的新图一定是一个有向无环图。因为在强连通分量内部不存在环，所以缩点后也不会形成环。而新图中的每个点都对应原图中的一个强连通分量，因此新图中也不存在拓扑序列。因此，如果原图中每个顶点都可以通过深度优先搜索遍历到所有其他顶点，那么它一定是一个强连通的 DAG，因此一定存在拓扑序列。