please can anyone tell me if given a graph prblem
how we can tell whether we have to do it through bfs aor dfs. i mean the criteria for choosing whether to choose dfs or bfs for a particular search
and if you have problems in any online judge post the link here
Thank you
Oct '12
Jun '13
You can use depth first search if you k now that the number of paths to be covered will be minimal.
If you have to find the shortest path across an nxn room moving right or down only, then the number of paths will be exponential relative to n, therefore a DFS is a very bad idea.
If you have to find the path from node a to node b in a tree with n nodes, then a DFS will be linear in complexity. Since DFS is simpler to code usually, I would suggest a DFS in this case. The complexity of a BFS would be equal to the DFS in this case.
| Topic | Category | Replies | Views | Activity |
|---|---|---|---|---|
| Hosting a competition on SPOJ | Off-topic | 1 | 104 | Apr 9 |
