어떤 의미에서 DFS는 BFS보다 빠릅니까?

Question

DFS 대 BFS를 읽는 동안 DFS가 BFS보다 빠르며 메모리가 덜 필요하다는 성명서를 읽었습니다.

내 구현은 DFS 용 스택과 BFS 용 대기열을 만드는 두 가지 모두를위한 C++입니다. 누군가 설명해 주시겠습니까? 속도와 메모리 요구 사항은 어떻게 다릅니 까?

Answer 1

• 메모리 요구는 : 큐 크기는 폭에 구속되는 반면, 스택 사이즈가 깊이에 의해 결합된다. n 노드를 가진 균형 이진 트리의 경우 스택 크기는 log (n)이지만 대기열 크기는 b O (n)입니다. 모든 경우에 명시 적 큐가 BFS에 필요하지 않을 수 있음에 유의하십시오. 자식 인덱스의 스택을 유지하는 것이 가능한 경우에 충분할 수 있습니다.

• 속도 : 저는 그것이 사실이라고 생각하지 않습니다. 전체 검색의 경우 두 경우 모두 상당한 추가 오버 헤드없이 모든 노드를 방문합니다. 일치하는 요소가 발견되었을 때 검색을 중단 할 수 있다면 검색된 요소가 일반적으로 레벨별로 올라 가기 때문에 검색 트리에서 더 높은 위치에 있으면 일반적으로 BFS가 더 빠릅니다. 검색된 요소가 일반적으로 상대적으로 깊고 많은 요소 중 하나가 충분하다면 DFS가 더 빠를 수 있습니다.