time-complexity - 生成所有可能的拓扑类型的图的时间复杂度

Question

我正在研究解决方案，以使用带有 kahn 排序的回溯来查找和打印有向无环图的所有拓扑类型。

完整的解决方案在这里：https ://www.geeksforgeeks.org/all-topological-sorts-of-a-directed-acyclic-graph/

根据我的说法，这个解决方案的时间复杂度是 O(V!)，其中 V = 图的总顶点。最坏的情况是 V 个断开的顶点。在这种情况下，在每个第 i 次递归中，我们将遍历 (i-1) 个入度为 0 的顶点。在这种情况下，拓扑排序的总数 = O(V!)。

你能帮我解决解决方案的时间复杂度吗？会是 O(V!) 吗？

标签： time-complexitygraph-theorytopological-sort