깊이 우선 탐색(DFS) / 너비 우선 탐색(BFS)

https://sustainable-dev.tistory.com/44

BFS(너비우선탐색)와 DFS(깊이우선탐색)

위 블로그를 보고 필사

 

---

 

 

 

1. 깊이 우선 탐색 (DFS, Depth-First Search)

- 스택, 재귀를 사용해 어떤 정점에서 그 정점과 연결된 정점까지 계속해서 나아가다 목표 정점을 찾지 못하면 다시 가장 가까운 정점으로 돌아와 다른 경로를 택해 재탐색

- 여기서 다시 되돌아오는 과정: 백트래킹(Backtracking)

 

 

출처: https://blog.kakaocdn.net/dn/lf5Ls/btqxJxzhlYi/LCeEz9YQjkpOk9lc80uARk/img.gif

 

- 백트래킹을 하는 과정에서 LIFO 방식으로 탐색을 한다.

- DFS는 현재 탐색하고 있는 경로 상의 노드들만 기억하면 되기 때문에 BFS에 비해 저장 공간의 수요가 비교적 적다.

- 스택을 이용하기 때문에 후입선출(LIFO)의 방식으로 탐색한다.

 

 

- 장점 : 메모리 소비가 적음 (올바른 경우인 경우, 최소 실행 시간 가짐)

- 단점 : 내가 방문한 길이 shortest인지 모름 (오랜 시간)

 

 

 

 

 

---

 

 

 

 

2. 너비 우선 탐색 (BFS, Breadth-First Search)

 

- 큐를 사용하며 어떤 정점을 방문한 후, 그 정점에 연결된 다른 정점들을 큐에 줄을 세워가며 순차적으로 방문하는데, 방문하지 않은 정점이 없을 때 (더 이상 큐에 남아있는 정점이 없을 떄)까지 다른 모든 정점들에 대해 똑같은 방식으로 탐색을 함

 

출처: https://blog.kakaocdn.net/dn/LwOPK/btqxKq0HiQe/k8m9nAJdj4YHKNHw8iRTX1/img.gif

 

- 큐에 먼저 들어온 정점이 먼저 디큐되고, 그 정점과 연결된 정점들이 큐에 인큐되는 FIFO 형식

 

- 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법 사용

- 큐를 사용하므로 FIFO(선입선출)

 

 

- 장점 : 가장 가까운 노드 방문 -> 최단 코스 (shortest path(최적해)를 보장함)

- 단점 : 메모리 소비가 큼 (exponential한 node의 수를 기억해야 하므로)