[자료구조] 그래프 탐색 BFS / DFS

그래프 탐색

• 하나의 정점에서 시작하여 그래프의 모든 정점을 순회하는 것이 목적
• 넓이 우선 탐색 (BFS), 깊이 우선 탐색(DFS)로 나뉜다.

넓이 우선 탐색 - BFS (Breadth-First Search)

• 가장 가까운 정점 부터 탐색한다. 
• 인접한 정점을 모두 탐색한후 다음 깊이(depth)의 정점들을 모두 탐색
  
  • 마지막 깊이의 정점들을 탐색할때까지 반복
• 주로 두 정점 사이에 최단 경로를 확인할때 사용한다.
• 깊이(depth)가 낮을때 사용하면 좋다.

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

• 하나의 경로를 끝까지 탐색한후 다음 경로를 탐색 한다.
• 하나의 경로에 최대 깊이(depth)까지 탐색한다.
• 다음 경로로 넘어가기전까지 하나의 경로를 완벽하게 탐색 할 수있으므로 운이 좋다면 몇번만에 목표 경로를 찾을 수있다.
• 깊이(depth)가 높을때 사용하면 좋다.