BFS, DFS이 어느 상황에 더 적합한지

이태혁·2021년 1월 4일
0
  • 답의 깊이가 깊지 않으면 BFS가 더 적합하다
  • 답의 깊이가 깊고 답이 흔치 않다면 DFS는 오래걸릴수있고 BFS는 빠를 수 있다.
  • 트리의 너비가 엄청 넓으면 BFS는 많은 메모리를 필요로 하므로 부적합할 수 있다.
  • 답이 자주 있지만 깊이가 깊다면 BFS보다 DFS가 더 적합하다

If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better.

If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster.

If the tree is very wide, a BFS might need too much memory, so it might be completely impractical.

If solutions are frequent but located deep in the tree, BFS could be impractical.

If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

https://stackoverflow.com/questions/3332947/when-is-it-practical-to-use-depth-first-search-dfs-vs-breadth-first-search-bf

profile
back-end, cloud, docker, web의 관심이 있는 예비개발자입니다.

0개의 댓글