你能通过像快速排序这样的经典排序算法对一个完整的无环有向图进行拓扑排序吗？
Could you topologically sort a complete acyclic directed graph through classical sorting algorithms like quicksort?
如果你有一个完整的有向无环图（即每个顶点都有一个与任何其他顶点的连续或出边），你可以用经典的拓扑排序算法对它进行拓扑排序 O(V+E) = O (V^2) 因为 E = O(V^2).
但是我们可以通过像快速排序这样的经典 O(n log n) 算法在 O(V log V) 中对它进行排序吗？因为我们总是可以比较两个顶点，所以我觉得这是可行的。有反例吗？
另外我想这只有在图表完整的情况下才有效。即使图形几乎完成，您最终也可能会比较两个没有边的顶点。
是的，如果输入图是无环的，那么它定义了一个严格的弱排序，其中 a < b 当且仅当是从 a 到 b 的弧，快速排序会给你唯一的拓扑顺序。
但是，一般来说，如果不探查所有弧线方向，就无法测试锦标赛是否是非循环的。
如果你有一个完整的有向无环图（即每个顶点都有一个与任何其他顶点的连续或出边），你可以用经典的拓扑排序算法对它进行拓扑排序 O(V+E) = O (V^2) 因为 E = O(V^2).
但是我们可以通过像快速排序这样的经典 O(n log n) 算法在 O(V log V) 中对它进行排序吗？因为我们总是可以比较两个顶点，所以我觉得这是可行的。有反例吗？
另外我想这只有在图表完整的情况下才有效。即使图形几乎完成，您最终也可能会比较两个没有边的顶点。
是的，如果输入图是无环的，那么它定义了一个严格的弱排序，其中 a < b 当且仅当是从 a 到 b 的弧，快速排序会给你唯一的拓扑顺序。
但是，一般来说，如果不探查所有弧线方向，就无法测试锦标赛是否是非循环的。