depth-first-search - 我应该测量时间数以在有向图上进行拓扑排序吗？

Question

我正在使用 DFS 在有向图上实现拓扑排序而不修改图。所以我选择了一种时间测量方法。

IMO，只要有布尔标志指示所有顶点的开始或完成就足够了。

1. 如果我访问已开始但未完成的顶点，则它是一个后边和一个循环。
2. 如果我按完成的顺序保存顶点，则它是拓扑排序列表。

但是网上所有的文字都只是说要测量时间数，所以我不确定我的观点是否正确。（我是自学者，不擅长算法）我错过了什么吗？或者这只是一个概念性的描述？

Answer 1

使用 DFS 可以轻松测量此问题的时间复杂度。由于该排序实现了与 DFS 相同的搜索，其时间复杂度为 O(V+E)，因此总体拓扑排序也是 O(V+E)，因为它只是在实现中添加了一个堆栈。

拓扑排序图通常使用邻接列表实现，这意味着您可以通过在线性时间 O(V) 中遍历列表一次来发现每个顶点的邻居。由于这是一个有向图，每个顶点的列表的总和大小是它的边总数，O(E)。由于您执行这两个过程，您将得到 O(V+E)。

考虑到你的时间复杂度现在是 O(V+E)，如果你能找到你的 V 和 E，你可以更准确地测量你的程序的时间。