DFS和拓扑排序有什么区别？不使用DFS能实现拓扑排序吗？

Question

10

我试图编写代码来检测有向图中的循环，如果没有循环，则返回相同图的拓扑排序。

在搜索时，我发现了不同的技术，如深度优先搜索和拓扑排序，用于检测有向图中的循环。

这两者之间有什么区别吗？

- Dhananjay Tyagi

1

我之前也有类似的困惑，但现在我清楚了：DFS（深度优先搜索）：打印输出的同时一直往深处遍历。拓扑排序：选取每个未被访问的顶点，并在打印其父节点（自身）之前先打印输出其依赖项。 - Manish gour

4个回答

3

拓扑排序是基于深度优先搜索算法的，适用于有向无环图（DAG）。拓扑排序是对顶点的线性排序，使得每条有向边uv中，顶点u在排序中出现在v之前。

只有当图中没有有向环时，才能进行拓扑排序。但DFS算法可应用于有向或无向图。

- cong

1

拓扑排序使用DFS的方式如下：

运行时间：O（V+E）

由于拓扑排序算法本质上是在DAG上使用DFS，因此DFS属性对于返回的列表以正确的拓扑顺序出现至关重要。然而，正如上面的答案所示，如果不使用DFS，则无法实现有序排列。例如，Kahn's algorithm和并行排序。

- Colin Moody

什么是Yes Ordering？ - wilmol

1

如果你想要更清晰的了解，可以尝试下面的问题。

起初，你可能会尝试直接使用深度优先搜索（DFS），但在某些情况下它会失败。

例如：DFS 在以下测试用例中失败：

5 4（顶点和边的数量）

（边的描述）

1 2

2 3

1 4

4 3

- mastan shaik

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Konstantin Yovkov · Accepted Answer

拓扑排序是有向无环图节点的特定顺序，可以通过深度优先搜索实现。除了深度优先搜索之外，还有其他方法可以找到拓扑顺序，例如Kahn算法。