What is the maximum number of possible topological sorts of N-order Direct Acyclic Graph?
I need to find the maximum number of topological sorts on Direct Acyclic Graph of N-order. I've checked by running Depth first search algorithm on various Direct Acyclic graphs, and it looks like it is the size of Depth first search algorithm forest that created after running DFS on the graph. Or maybe I completely wrong or miss something. I also need to prove it. Any help will be appreciated. Thank you.
Answer
If you have a total of n elements, the maximum number of possible ways to order those n elements is n! (the number of permutations of n elements). So you certainly can't do any better than that. If we can find a family of graphs with n nodes that have n! possible topological orderings, then we know that has to be the maximum possible number of topological orderings.
As a hint, it is indeed possible to find n-node DAGs with n! possible topological orderings. Try thinking about what that would mean about the possible edges between those nodes. Once you've found this family of graphs, it's very easy to show that they have the maximum possible number of topological orderings by using the above argument.
Hope this helps!