DFS와 BFS의 차이

샤핑

 

 

 

이번 시간에는 DFS와 BFS의 원리를 살펴보고 비교해보겠습니다. 위의 그래프를 가지고 설명하겠습니다.

 

 

 

왼쪽: DFS 요약, 오른쪽: BFS 요약

 

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

- "막힐 때까지 나아간다" 라고 이해하시면 됩니다.

- 막힐 때까지 계속 접근하다가 막히면(접근할 노드가 더 이상 없으면) 한 발짝만 되돌아간 후 접근하지 않은 노드로 접근합니다.

 

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

- "주위를 둘러본다" 라고 이해하시면 됩니다.

- 주위를 둘러보다가 더 이상 없으면 한 발짝만 접근한 후 다시 주위를 둘러봅니다.

 

 

(1) DFS의 구체적인 동작 원리는 아래와 같습니다. 막힐 때까지 계속 나아가는 모습을 볼 수 있습니다. 접근 순서는 (a)-(b)-(d)-(e)-(c) 입니다.

 

 

 

(2) BFS의 구체적인 동작 원리는 아래와 같습니다. 주위를 둘러보는 모습을 볼 수 있습니다. 접근 순서는 (a)-(b)-(c)-(d)-(e) 입니다.

 

 

 

[소스 코드]

https://github.com/jhs951101/DFSBFS

 

 

 

<출처>

나무위키: 깊이 우선 탐색

나무위키: 너비 우선 탐색

 

728x90