DFS

• 깊이 우선 탐색으로 한 노드에서 최대한 깊숙히 탐색해서 더이상 갈수 없을때까지 들어가서 다음 분기로 넘어갑니다.
• 발견된 노드를 Stack 혹은 재귀호출로 저장합니다.
• 재귀와 스택을 활용하면 구현하기 쉽습니다.

BFS

• 너비 우선 탐색으로 한노드에서 인접 노드를 방문하고 해당 노드들의 인접 노드를 차례로 방문합니다.
• 발견된 노드를 큐에 저장하고, 먼저 들어온 노드를 꺼내어 방문합니다.
• 가까운 단계에 있는 노드를 먼저 방문하고 탐색합니다.
• 큐를 사용하면 구현하기가 쉽습니다.

공통 특징

• 그래프 최단 경로 등에 많이 활용됩니다.
• 둘 다 알고리즘 테스트 단골 문제입니다.

활용법

• 그래프 의 모든 노드를 방문 하는 것들이라면 DFS ,BFS모두 사용됩니다.
• a→b지점까지 가는데 특정 경로의 특징이나 그런 것들이 필요하면 DFS를 사용합니다.
• 최단거리 문제에는 BFS가 조금 유리합니다. → 시간복잡도는 동일합니다.