오늘은 탐색법인 너비 우선탐색, 깊이 우선탐색에 대해 수강하였다.
BFS(너비 우선탐색), DFS(깊이 우선탐색) 이란?
그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘, 최대한 깊은 정점부터 탐색하는 알고리즘이다.
BFS의 특징은 Queue를 이용하여 구현되며, 시작부터 가장 가까운 정점부터 탐색한다.
나머지 특징은 아래와 같다.
BFS(너비 우선탐색)의 방법은 우선 시작지점인 최초정점인 A를 Queue에 넣는다. 그 후 A를 Dequeue 하며 A로부터 이동가능한 간선을 Queue에 넣는다. 그 후 추가된 간선들의 시작 정점을 Deque한 뒤 Dequeue된 정점의 이동가능 간선을 다시 넣는다. 이런식의 추가와 소거를 통해 탐색을 진행한다.
깊이 우선탐색에 대한 정의는 상단에 설명하였다.
DFS(깊이 우선탐색)는 Stack을 이용하여 구현하며 시작정점에서 깊은 것 부터 찾아 탐색한다.
시간복잡도는 빅오(V+E)를 가진다.
DFS의 탐색법은
스택에 A를 넣고 이동할 수 있는 정점인 B를 추가하고, 갈수 있는 정점인 B를 추가한다.
다시 B에서 갈 수 있는 정점인 F를 추가하고 G를 추가 한뒤 F로 돌아와서 G를 pop한 뒤 C를 추가한다.
위와같은 방식으로 깊이 우선탐색이 이루어진다.
'알고리즘 > 알고리즘' 카테고리의 다른 글
| 알고리즘 강의 16일차 - 소수 알고리즘 (0) | 2023.03.24 |
|---|---|
| 알고리즘 강의 15일차 - 그리디 기초 (0) | 2023.03.23 |
| 알고리즘 강의 13일차 - 정렬의 기초 (0) | 2023.03.21 |
| 알고리즘 강의 12일차 - 이진탐색 기초 (0) | 2023.03.20 |
| 알고리즘 강의 11일차 - 트라이 기초 (0) | 2023.03.17 |