我应该测量时间数字以获得有向图上的拓扑排序吗？

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，则可以更准确地测量程序的时间。