[알고리즘] DFS(depth first search, 깊이우선탐색), BFS(breadth first search, 너비우선탐색)

참고블로그

https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

[자료구조] 그래프(Graph)란 - Heee's Development Blog

그래프 vs 트리

- 그래프 중 방향성이 있는 비순환 그래프 -> 트리

- 그래프 루트 노드 개념x, 부모-자식 개념x

- 그래프 (node-edge), 트리(이진트리, 이진탐색트리, AVL트리, red-black, heap(max-heap, min-heap)

 

1. 깊이 우선 탐색 (DFS, Depth-First Search)
- 최대한 깊이 내려간 뒤 옆으로 이동

- stack 또는 재귀함수로 구현

- ex) 미로찾기 시 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가, 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향을 탐색

 

- 모든 노드를 방문하고자 하는 경우 DFS선택

- BFS보다 간단함

- 속도는 BFS비해 느림

 

 

 

2. 너비 우선 탐색 (BFS, Breadth-First Search)
- 최대한 넓게 옆으로 이동한 뒤, 아래로 이동

- queue이용해서 구현

- 루트 노드(혹은 다른 임의의 노드)에서 시작 -> 인접한 노드 먼저 탐색

   시작 정범으로부터 가까운 정점을 먼저 방문

-  ex) 최단경로 찾고 싶을 때 이 방법 선택 

 

 

[문제 유형]

1) 그래프 모든 정점 방문 - 둘다 사용

2) 경로 특징 저장 - DFS (ex) a-b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다. - 특징 저장)

3) 최단거리 - BFS (현재 노드에서 가장 가까운 곳부터 찾기에)

4) 검색 대상 그래프가 크다면 - DFS고려

5) 검색 대상의 규모 크지 않고, 검색 시작 지점에서 찾는 대상 별로 멀지 않다면 - BFS