0
$\begingroup$

What is the number of distinct BFS, DFS in a complete graph?


My approach is like this-->

For DFS take a node, we have (n-1) possible tree edges, next we have all possible (n-2) tree edges,.......finally 1 possible tree edge. and we can choos any of n nodes as rooot node. hence no of distinct DFS trees= n*(n-1)(n-2)....1= n!

For BFS tree if we take a node as root, we have to explore all its neighbors , so the number distinct of BFS trees =no of nodes we can choose as root ie. n .

Is this approach correct?

$\endgroup$
  • $\begingroup$ Please help... :( $\endgroup$ – HIRAK MONDAL Aug 11 at 4:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.