Halit's blog

By Halit, history, 5 months ago, In English,

Hi --

Which one is better DFS/BFS. Someone says it can be change problem to problem. But I want to learn which type of problems are good for DFS, which type of problems are good for BFS?

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

There is not a general rule.
Probably you can use either of them in the vast majority of problems, but usually, it takes less time to write a DFS.
Anyway, you would use DFS for most of the tree-related problems.
BFS is useful when you want to process in a layer by layer order.
Just do different tasks and you will feel it ;)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! Are there any special problems to understand diffrences?

»
5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

BFS can find the answer which has the shortest path. DFS can be use when there are a lot of states, and you just need to find a right answer. They can take the place of the other in many problems. I think you should do more problems to have a clear understanding. :)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks! Is there any BIG complexity difference between DFS and BFS(in some problems)?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      In some special problems, you can only use one of them. Using the other one isn't a proper way to solve them.

      However, in most of the problems, they don't have big complexity difference.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes. There are some algorithms where implementations by one is better (faster/ lower time constant/ lower complexity) than the other. But dont worry about it, practice to practice you will know DFS or BFS should be use (or better use) in particilar problems