DFS scan on a completed graph

Question

I have some interesting question that I would like to get your help:

Let's say I have a graph (Data structure) with n(n-1)/2 edges, which means, completed graph.
How many possible different DFS trees can I get from one DFS scan from some random element in the graph?

Answer 1

Your question is interesting. I believe you are talking about complete graph with n vertices and n(n-1)/2 edges in between them.
If we begin depth first search (DFS) from any vertex, it will end up visiting exactly n vertices. In DFS, we keep track of visited vertices so that we will not visit them once they are visited and hence outgoing option reduces as long as DFS progresses. We can summarize this as:

• There are total n options to choose first vertex.
• There are total n-1 options to choose second vertex as 1 vertex is already visited.
• There are total n-2 options to choose third vertex as 2 vertices are already visited.

• There are total n-3 options to choose third vertex as 3 vertices are already visited.

• And so on . . .

• There is only 1 option to choose nth vertex.

Hence, different possible DFS trees that we can get from DFS in such graph is :

Total ways = n*(n-1)*(n-2)*(n-3)*....*1
           = n! ( n factorial )