BFS, DFS

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

• 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
• Queue를 이용하여 구현
• 시작 지점에서 가까운 정점부터 탐색
• $V$가 정점의 수, $E$가 간선의 수 일 떄 BFS의 시간복잡도는 $O(V + E)$다.

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

• 최대한 깊은 정점부터 탐색하는 알고리즘
• Stack을 이용하여 구현
• 시작 정점에서 깊은 것부터 찾는다.
• $V$가 정점의 수, $E$가 간선의 수 일 떄 DFS의 시간복잡도는 $O(V + E)$다.