깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS)

깊이 우선 탐색 (DFS)과 너비 우선 탐색 (BFS)은 둘 다 그래프를 탐색하는 방법이다.

그래프란?

• 정점(node)과 그 정점(node)을 연결한는 간선(edge)으로 이루어진 자료구조의 일종을 말한다.
• 그래프를 탐색하는 것은 하나의 정점(node)에서 시작하여 차례대로 모든 정점(node)들을 한 번씩 들르는 것을 말한다.

 

깊이 우선 탐색 (DFS) _ Depth - First Search

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다.

• 모든 노드를 방문하고자 할 때, 이 방법을 선택한다.
• 깊이 우선 탐색(DFS)이 너무 우선 탐색(BFS)보다 간결하다.
• 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

 

너비 우선 탐색 (BFS) _ Breadth - First Search

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

• 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 사용한다.

 

출처: https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90