[알고리즘] DFS와 BFS

알고리즘 개념 정리

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

현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색

• 스택(Stack) or 재귀 함수로 구현
  

✔︎ 특징

• 모든 노드를 방문하고자 하는 경우에 사용
• 자기 자신을 호출하는 순환 알고리즘의 형태
• BFS 보다 간단한 편

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

현재 정점에서 연결된 가까운 점들부터 탐색

• 큐(Queue)로 구현

  방문한 노드들을 차례로 저장한 후 꺼낼 수 있기 때문이다.
  

✔︎ 특징

• 주로 최단거리 알고리즘에 사용 (혹은 임의의 경로)
• 재귀적으로 작동하지 않음
  

DFS vs. BFS

ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후,
핑구와 무지 사이에 존재하는 경로를 찾는 경우

• DFS(깊이 우선 탐색) - 모든 친구 관계를 다 살펴볼 수도 있다.
• BFS(너비 우선 탐색) - 핑구와 가까운 관계부터 탐색

참고

• [Algorithm] DFS와 BFS 기본과 예제 문제
• Problem Solving - 문제 풀이 팁 정리 (완전 탐색 - DFS & BFS)
• [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)