Major applications of DFS:-
- To check if the graph is connected. And to find number of connected and/or strongly connected components. Also, to find the number of nodes in a connected component.
- To check if the graph is cyclic or acyclic.
- To find cut vertices (articulation points) and cut edges (bridges) — both in $O(E)$ time.
- Topological sorting.
Major applications of BFS:-
- To check if the graph is connected. And to find number of connected and/or strongly connected components. Also, to find the number of nodes in a connected component.
- To check if the graph is cyclic or acyclic.
- Topological sorting
- Finding single source shortest path for unweighted (or equally weighted, which we can consider unweighted) graphs. It's like a lightweight version of Dijkstra (which can handle weighted graphs).
- To check if graph is bipartite. (Option B is FALSE)
Why is Option C true? We need infix and along with that either prefix or postfix will do. But if we don't have infix, we can't uniquely construct a Binary Tree.