그래프 탐색이요?…
간단합니다. 하나의 정점에서 시작하여 차례대로 모든 정점들을 한 번씩 방문하는것이죠!
그렇다면 방문하는 기준이 다른 여러가지 방식들이 존재하겠죠?
오늘은 깊이 우선 탐색! 이라는것에 대해 알아보도록 하겠습니다!
- 깊이 우선 탐색 DFS(Depth-First Search)
DFS (Depth-First Search)
말 그대로 루트 노드(혹은 다른 임의의 노드)에서 시작하여 다음 분기로 가기전에 해당 분기를 끝까지 탐색하는 방법
- 넓게~ 탐색하는게 아닌 (근처에 노드들을 다 방문해가는게 아닌) 깊게!!!(한가지 분기점의 끝까지) 탐색하는것입니다.
- 완전탐색을 하고자할때 DFS탐색방식을 이용합니다.
- 미로를 예로들어보면 한방향으로 일단 끝까지 갔다가 막혀있으면 다시 되돌아가 처음 만나는 분기점에서 다시 끝까지
- 가보는것입니다.
특징:
- 자기 자신을 호출하는 순환 알고리즘의 형태입니다. (재귀호출)
- 트리 자료구조의 모든 순회 방식은 DFS방식의 한 종류 입니다.
- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것입니다.
728x90
'Algorithem' 카테고리의 다른 글
| 페이지 교체 알고리즘 feat. LRU (0) | 2023.01.16 |
|---|---|
| 행렬의 곱셈 (0) | 2023.01.13 |
| 페이지 교체 알고리즘 feat. LRU (0) | 2023.01.13 |
| Linear Search(선형검색), Binary Search(이진검색) (0) | 2023.01.13 |
| 정렬을 하는 원시적인 방법 3가지 (Bubble, Selection, Insertion) (0) | 2023.01.13 |
