BFS와 DFS를 읽고 있는데 BFS가 큐를 사용하여 노드를 저장하는 반면 DFS는 스택을 사용하여 아직 방문하지 않은 노드를 저장합니다. 하지만 차이점을 겪을 때, 노드를 저장하기 위해 대기열을 필요로하기 때문에 Breadth First Search가 더 많은 메모리를 필요로한다고 언급 한 많은 웹 사이트를 발견했습니다. 왜 DFS조차도 노드를 유지하기 위해 스택을 사용하기 때문에 BFS가 더 많은 메모리 만 필요로하는지 이해하지 못했습니다. 내가 누락 된 것이 있으면 알려주시겠습니까?너비가 큰 첫 번째 검색을 사용하는 동안 메모리가 주된 제약 이유는 무엇입니까?
BFS와 DFS 스토리지의 주요 차이점은 BFS가의 큐를 유지한다는 것이다 DFS 스택은 루트에서 현재 노드로 이동하는 동안 방문한 노드를 유지하는 반면 (현재 노드의 하위 노드를 탐색 할 때 해당 노드로 돌아갈 것입니다) DFS 스택은 방문 할 노드를 찾습니다.
최악의 경우 BFS와 DFS는 대기열 또는 스택에 O (N) 노드를 저장합니다.
메모리 사용량 측면에서 DFS의 최악의 경우는 스택에 트리의 거의 모든 노드를 저장할 때, 즉 트리가 연결된 목록 (마지막 노드를 제외한 각 노드에 정확히 하나의 자식이 있음) . 이 경우 스택에 N-1 개 노드가 있습니다.
BFS의 경우 메모리 사용량 측면에서 루트 노드가 각 노드에 연결될 때 최악의 경우가 발생합니다.이 경우 N-1 노드가 대기열에 저장됩니다. DFS 저장소와 동일한 양 최악의 경우 스택에
하지만 균형 잡힌 나무 (평균적인 경우)를 생각하면 DFS는 매번 루트 노드에서 현재 노드까지의 경로 만 저장합니다 (로그 N 노드와 관련 있음). BFS는 균형을 위해 이진 트리는 트리의 맨 아래로 갈 때 N/2만큼 클 수 있습니다.
트리가 링크 된 목록 일 때 BFS와 DFS가 동일한 경우가 아닙니까 (각 노드에는 하나의 분기 만 있음)? 다른 모든 경우 DFS는 메모리를 적게 사용합니다. – slebetman
링크 된 목록의 경우 BFS는 DFS와 동일한 양의 메모리를 사용하지 않습니다. DFS 스택에는 마지막 노드에 도달 할 때를 제외하고 모든 노드가 포함되지만 BFS 대기열에는 매번 노드가 하나만 포함됩니다. – afenster
아 좋아. 함수 호출 값을 연결하여 결과를 빌드해야하는 알고리즘을 생각 중이었습니다. 그러나 정의상 DFS입니다. – slebetman
글쎄, 처음에는 균형 잡힌 나무가 더 커지는 경향이 있습니다. 균형 잡힌 트리에 깊이 수준을 추가 할 때마다 용량이 대략 두 배가되기 때문입니다.
그래서, 트리의 하단에, 당신의 폭을 16,383 항목을 저장하기 위해 8192입니다하지만 깊이는 14입니다 :
Level 1: 1
2: 2-3
3: 4-7
4: 8-15
5: 16-31
6: 32-63
7: 64-127
8: 128-255
9: 256-511
10: 512-1023
11: 1024-2047
12: 2048-4095
13: 4096-8191
14: 8192-16383
감사합니다 paxdiablo. 나는 분명히 이해했다. – kadina
http://www.quora.com/Why-is-DFS-usually-more-space-efficient-than-BFS – Skynet
다음을 확인하십시오. http://stackoverflow.com/questions/20429310/why- is-dfs-depth-first-searching-to-be-space-efficient –