IIT Kanpur written test

Question

Number of distinct BFS, DFS trees in a complete graph ?

Answer 1

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 .

Comments

Could you please clarify how this is wrong -

number of distinct dfs tree = C(C(n,2),n-1)?

The logic here is C(n,2) are total edges. Out of that select (n-1) edges.

---

@agoh,u cant use this formula as when u r choosing n-1 edges,it can also chosse those edges  which can form a cycle.

---

Thank you :)