BFS와 DFS 비교표

BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)의 특징을 비교특징BFS(너비 우선 탐색)DFS(깊이 우선 탐색) 탐색 방식너비 우선 탐색깊이 우선 탐색구조큐(Queue) 사용스택(Stack) 또는 재귀 사용최단 경로가중치가 없는 경우 최단 경로 보장최단 경로 보장하지 않음메모리 사용O(V) (정점 수)O(V) (정점 수)시간 복잡도O(V + E) (정점과 간선 수)O(V + E) (정점과 간선 수)적용 분야최단 경로, 네트워크 탐색, 퍼즐 문제미로 찾기, 위상 정렬, 연결 요소 찾기방문 순서인접한 정점부터 탐색한 방향으로 깊게 탐색중복 경로동일한 정점 여러 번 방문 가능동일한 정점 여러 번 방문 가능전략레벨 단위로 탐색경로 단위로 탐색실제 적용 예시소셜 네트워크 분석, 웹 크롤러, GPS 내비게이션게..
자료구조 2024. 10. 21. 18:01
1