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?

# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

5 | Ashishgup | 182 |

6 | vovuh | 181 |

7 | Um_nik | 179 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

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?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/04/2020 05:03:54 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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 ;)

Thanks! Are there any special problems to understand diffrences?

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. :)

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

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.

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