DFS(Depth First Search)와 BFS(Breadth First Search)에 대해서 알아보도록 하겠습니다.

DFS(Depth First Search)

루트 노드에서 시작해서 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방법.

1. 넓게 탐색하기 전에 깊게 탐색함.

2. 모든 노드를 방문할 때 이 방법을 사용함.

3. DFS가 BFS보다 좀 더 간편함.

4. 검색 속도 자체는 BFS에 비해서 느림.

DFS 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 지님

• 그래프 탐색 시 어떤 노드를 방문했는지 반드시 검사를 해줘야함.

DFS 과정

1. a 노드를 방문
   • 방문한 노드는 방문했다고 표시
2. a와 인접한 노드들을 차례로 순회
   • a와 인접한 노드가 없다면 종료
3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노트들을 전부 방문해야함
   • b를 시작으로 DFS다시 시작
4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾는다

BFS(Breadth First Search )

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법.

1. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법.

2. 깊게 탐색하기 전에 넓게 탐색.

3. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택함.

BFS 특징

• BFS는 재귀적으로 동작하지 않는다.

• 어떤 노드를 방문했는지 여부를 반드시 검사해야 한다.

• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 Queue를 사용.

• 선입선출 원칙으로 탐색.

BFS 과정

• 깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 후에는 3인 노드를 방문하는 식으로 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

DFS와 BFS의 차이점

출처 : https://namu.wiki/w/BFS