알고리듬 #17 | BFS, DFS

BFS (너비 우선 탐색)

개요

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

특징

• Queue 를 이용하여 구현할 수 있습니다.
• 시작 정점에서 가까운 정점부터 탐색합니다.
• V 가 정점의 수, E 가 간선의 수일 때 시간복잡도는 O(V+E) 입니다.

DFS (깊이 우선 탐색)

개요

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

특징

• Stack 을 이용하여 구현할 수 있습니다.
• 시작 정점에서 깊은 것(먼 것) 부터 찾습니다.
• V 가 정점의 수, E 가 간선의 수일 때 시간복잡도는 O(V+E) 입니다.