[Section2][자료구조/알고리즘] 자료구조 - BFS / DFS

DFS (Depth-First Search)  란?

깊이를 먼저 탐색하는 탐색 방법이다.

한 깊이를 끝까지 탐색한 뒤 더 이상 탐색할  하위가 없을 경우 다른 깊이를 탐색한다.

DFS의 종류로는 아래와 같다

• 전위 순회 (PreOrder)
• 중위 순회 (InOrder)
• 후위 순회 (PostOrder)

- 구현 가능 방법 종류

Stack 이용.

재귀 이용.

 

 

BFS (Breadth-First Search)  란?

같은 레벨의 노드들을 먼저 탐색 하는 방법이다.

쉽게 말하자면,

root의 기준에서 자식 레벨의 모든 노드를 다 방문하고,

그 다음은 자식의 자식 노드들을 다 방문하기를 반복한다.

 

- 구현 가능 방법 종류

Queue 이용

 

참조 : https://www.youtube.com/watch?v=_hxFgg7TLZQ&t=1s