https://stackoverflow.com/questions/3332947/when-is-it-practical-to-use-depth-first-search-dfs-vs-breadth-first-search-bf/3332994#3332994
Q. When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?
Q. DFS와 BFS중 어느 것을 이용하는 것이 더 실용적인가요?
That heavily depends on the structure of the search tree and the number and location of solutions (aka searched-for items). 알고리즘을 적용할 자료의 수, 정답의 위치, 자료구조에 따라 다릅니다.
- If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better.
만약, 정답이 루트 노드에 가까운 경우엔 BFS를 이용하는 것이 좋을 것이고. - 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.
트리 자체에 데이터의 레벨이 매우 크고, 정답을 잘 찾을 수 없다면 DFS를 이용한 경우 매우 긴 시간 동안 함수를 수행해야 합니다. BFS가 아마 좀 빠를수도 있습니다. - If the tree is very wide, a BFS might need too much memory, so it might be completely impractical.
트리가 매우 광범위 할때에 BFS는 메모리를 많이 사용해서 실용적이지 않습니다.. - If solutions are frequent but located deep in the tree, BFS could be impractical.
정답을 찾을수 있지만 트리의 매우 깊은 곳에 위치한다면 BFS는 실용적이지 않습니다. - 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).
But these are just rules of thumb; you'll probably need to experiment.
그저 이론적인 규칙이며, 경험이 필요합니다.
Another issue is parallelism: if you want to parallelize BFS you would need a shared datastructure between threads, which is a bad thing.
또 주목해야 할 것은 병렬성 : BFS를 병렬적으로 수행한다면 쓰레드들 간에 자료 구조를 공유헤야하는데 이는 좋지않다.
DFS might be easier to distribute even between connected machines if you don't insist on the exact order of visiting the nodes.
DFS를 이용하면. 정확하게 노드를 visit 했는지 확인 하지 않고도 연결된 머신에 나눌 수 있을 것이다.
