[알고리즘] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

 

그래프를 탐색하는 방법은 크게 1) 깊이 우선 탐색(Depth-First Search, DFS)과 2) 너비 우선 탐색(Breadth-First Search, BFS)이 있다.

 

이때, 그래프는 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조로,

그래프를 탐색한다는 것은 하나의 정점으로부터 시작해 차례대로 모든 정점을 한 번씩 방문하는 것을 의미한다.

 

BFS와 DFS의 노드 방문 차이

---

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

: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

 

DFS의 노드 탐색 순서, 한 branch가 끝나야 옆으로 넘어간다

 

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

• 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 더 간단함
• 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느림

---

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

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

 

BFS의 노드 탐색 순서, 같은 level의 노드를 우선 방문한다

 

루트 노드(또는 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법으로,

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

---

3. DFS vs. BFS

DFS	BFS
현재 node에서 갈 수 있는 점들까지 들어가며 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀 함수로 구현	큐를 이용해 구현

---

구현 코드 (Python)

백준 1260 문제-DFS와 BFS의 Python 구현 코드입니다.

 

2024.04.10 - [코딩테스트] - [백준]1260번 DFS와 BFS (Python/파이썬) - 런타임 에러(KeyError) 해결

[백준]1260번 DFS와 BFS (Python/파이썬) - 런타임 에러(KeyError) 해결

---

설명 출처:

https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

 

이미지 출처:

https://www.geeksforgeeks.org/difference-between-bfs-and-dfs/

Difference between BFS and DFS - GeeksforGeeks

https://developer-mac.tistory.com/64

[코딩테스트 대비] DFS, BFS 정리