[알고리즘] DFS, BFS 개념

BFS와 DFS

• 두가지 모두 그래프를 탐색하는 방법
• 그래프: 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종
• 그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것

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

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방식
• 예를 들어 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더이상 갈 수 없게되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길로부터 다시 다른 방향으로 탐색을 진행하는 방식

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

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택

DFS vs BFS

• DFS (깊이 우선 탐색)
  • 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
  • 스택 또는 재귀하수로 구현
• BFS (너비 우선 탐색)
  • 현재 정점에 연결된 가까운 점들부터 탐색
  • 큐를 이용해서 구현