CODEWITHSUNDEEP
algorithmgraph-algorithmdepth-first-search
YogevAbr
YogevAbr

Reputation: 289

DFS scan on a completed graph

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?

Upvotes: 0

Views: 2578

Answers (2)

user10120190
user10120190

Reputation: 1

In fact it's not a tree but a list of nodes of the given complete graph. Thus, the question is: How many permutations of n nodes of the graph? Apparently, the answer is n!.

Upvotes: 0

BishalG
BishalG

Reputation: 1424

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 )

Upvotes: 2

Related Questions