DFS & BFS

DFS(Depth-First Search)

개념

• 루트노드에서 시작해 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색
• 스택 or 재귀함수로 구현

특징

• 장점
  • 최단 경로 빠르게 찾을 수 있다.
• 단점
  • 경로가 매우 길 경우 많은 기억 공간 필요
  • 비연결 그래프일 경우, 모든 그래프 탐색 후 실패

 

BFS(Breadth First Search)

개념

• 루트 노드에서 시작해 인접한 노드를 먼저 탐색하는 방식으로 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문
• 큐를 이용해 구현

특징

• 장점
  • 적은 메모리 사용
  • 찾으려는 노드가 깊은 단계에 있는 경우 BFS보다 빠름
• 단점
  • 경로가 존재하지 않아도 끝날 때까지 탐색
  • 최단 경로 찾기 힘듬