-
[CS & Algorithm-3] DFS, BFS 알고리즘 에 대하여CS & Algorithm 2021. 1. 1. 17:32
D F S (Depth - First Search) & B F S (Breadth - First Search)
D F S 란
- 깊이 우선 탐색이라고 불림, 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조 (또는 재귀)를 이용함.
- 처음 시작하는 노드를 스택에 push
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있다면 또다시 조회
- 이를 지속적으로 반복 (끝날 때 까지)
B F S 란
- BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘,
- 큐 자료구조를 이용
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 함.
- 큐에서 노드를 꺼낸 뒤에 해동 노드의 인접 노드 중에서 방문하지 않는 노드를 큐에 삽입
- 이를 지속적으로 반복 (끝날 때 까지)
'CS & Algorithm' 카테고리의 다른 글
[CS & Algorithm-6] 동전 0 (Greedy) (0) 2021.08.18 [CS & Algorithm-5] BaekJoon 설탕 배달 문제 (Greedy) (0) 2021.08.18 [CS & Algorithm-4] BaekJoon ATM 문제 (Greedy) (0) 2021.08.18 [CS & Algorithm-2] Algorithm repository (0) 2020.12.06 [CS & Algorithm-1] linkedlist , queue, stack (0) 2020.12.04