BFS, DFS

BFS

정의

Breadth-First Search 의 약자로 너비 우선 탐색 알고리즘을 뜻함

그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘

---

특징

• Queue 를 이용하여 구현 가능
• 시작 지점에서 가까운 정점부터 탐색
• V 가 정점의 수, E 가 간선의 수일 때 BFS 의 시간복잡도는 O(V + E)

---

DFS

정의

Depth-First Search 의 약자로 깊이 우선 탐색 알고리즘을 뜻함

그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘

---

특징

• Stack 을 이용하여 구현
• 시작 정점에서 깊은 것부터 탐색
• V 가 정점의 수, E 가 간선의 수일 때 DFS 의 시간복잡도는 O(V + E)