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

깊이 우선 탐색(Depth- First Search)

특정 노드에서 시작해 다음 분기(branch)로 넘어 가기 전에 해당 분기를 완벽하게 탐색하는 방법

- 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘
- 자기 자신을 호출하는 순환 알고리즘 또는 스택의 형태를 지님
- 마지막에 들어온것이 먼저나가는 방식. LIFO(Last In First Out)
- 알고리즘을 구현할때 노드의 방문여부 확인 필요

http://mishadoff.com/blog/dfs-on-binary-tree-array/

장점

- 현 경로상의 노드만 기억하면 되므로 저장공간의 수요가 비교적 적음
- 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음

단점

- 해가 없는 경로에 깊이 빠질 가능성 존재
- 얻어진 해가 최단경로가 된다는 보장이 없음

동작과정

1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
2-1. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리
2-2. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

너비 우선 탐색(Breadth-First Search)

특정 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

- 두 노드사이의 최단경로, 임의의 경로를 찾고 싶을 때 사용
- 재귀적으로 동작 하지 않음
- 어떤 노드를 방문했었는지 여부 검사 필요
- 큐를 사용 → FIFO(First In First Out)

http://mishadoff.com/blog/dfs-on-binary-tree-array/

장점

- 출발노드에서 목표노드까지의 최단 길이 경로를 보장


단점

- 경로가 매우 길 경우 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간이 필요

동작과정

1. 탐색 시작 노드를 큐에 삽입 후 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중에서 방문하지않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복

DFS BFS 차이