BFS 대 DFS 그래프 공간의 복잡도

Question

너비가 큰 첫 번째 검색에 대기열이 포함될 때 깊이 우선 검색과 폭 우선 검색에 가장자리 및 꼭지점이있는 그래프에서 필요한 메모리는 얼마입니까?

Answer 1

재귀 DFS는 현재 처리되는 모든 노드에 대해 함수 호출과 스택 프레임을 필요로하기 때문에 가장 많은 메모리 부담이됩니다. 명시 적 스택 및 대기열 데이터 구조에서는 소비 된 메모리에 큰 차이가 없습니다. 일반적으로 그래프의 모양과 현재 스택 또는 대기열에있는 노드의 수에 따라 다릅니다. 이전에 처리되었거나 아직 방문하지 않은 노드는 알고리즘에 의해 소비 된 메모리에 영향을 미치지 않습니다. 그러나 별 모양의 그래프와 같은 극단적 인 경우에는 그래프 전체를 읽을 수 있습니다. 그러나 다시 한 번 그것은 그래프의 구조에 달려 있습니다.