자료구조 & 알고리즘(너비 우선 탐색, 깊이 우선 탐색)

너비 우선 탐색

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

BFS의 특징

▶ Queue를 이용하여 구현할 수 있다.

▶ 시작 지점에서 가까운 정점부터 탐색한다.

▶ V가 정점의 수, E가 간선의 수일때 BFS의 시간복잡도는 0(V+E)다.

깊이 우선 탐색

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

DFS의 특징

▶ Stack을 이용하여 구현할 수있다.

▶ 시작 정점에서 깊은 것 부터 찾는다.

▶ V가 정점의 수, E가 간선의 수일 때 BFS의 시간 복잡도는 0(V+E)다.