DFS (깊이 우선 탐색, Depth-First Search)
"루트노드(혹은 다른 임의의 노드)에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법. 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색"
- 트리의 순회와 같이 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색(search) 알고리즘이라고 한며, 깊이 우선 탐색(DFS; depth-first search)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법.
- 미로찾기를 예로 들면 최대한 한 반향으로 갈수 잇을때까지 나가다가 막다른 길이 나오면 가장 최근의 갈림길로 돌아가서 다시 한 방향으로 나가는 것을 반복하는 방식.
- 특징
1) 자기 자신을 호출하는 순환 알고리즘의 형태.(재귀 or Stack)
2) 그래프 탐색 시 어떤 노드를 방문했는지 검사 필요. 검사하지 않으면 무한루프에 빠질 수 있음.
3) 최적의 경로를 찾다가 막다른 경로가 나오면 갈림길이 있는 노드로 돌아감.
4) 모든 노드를 다 방문 할 때 이 방법을 사용.
5) 너비 우선 탐색(BFS) 보다 간단하다. 하지만 너비 우선 탐색보다 속도가 느리다.
BFS (너비 우선 탐색, Bread-First Search)
"루트 노드(혹은 다른 임의의 노드)에서 시작한 인접 노드를 먼저 탐색하는 방법."
- 너비 우선 탐색(BFS; Breadth First Search)은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘으로, 동작 과정이 직관적이여서 이해하기 쉽다.
- 특징
1) 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색한다. (거리 1부터 2, 3 ,4순서대로...)
2) 그래프 탐색 시 어떤 노드를 방문했는지 검사 필요. 검사하지 않으면 무한루프에 빠질 수 있음.
3) 재귀적으로 동작하지 않음.
4) 방문한 노드들을 차례로 저장하고 꺼낼 수 있는 자료 구조인 Queue를 사용함.
5) FIFO ( First-In First-Out) 선입선출 원칙.
6) 두 노드 사이 최단 경로 혹은 임의의 경로를 찾고자 할 때 이 방법을 사용.
'Algorithm' 카테고리의 다른 글
| Algorithm #2 에라토스테네스의 체(Sieve of Eratosthenes) (1) | 2022.06.30 |
|---|