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

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적입니다.
그래프의 데이터는 배열처럼 정렬이 되어 있지 않기에, 원하는 자료를 찾으려면, 하나씩 모두 탐색해야한다.

그래프의 모든 정점 탐색 방법 중, 가장 대표적인 두 가지 방법인 DFS, BFS 알아봅니다.

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

stack 을 이용해서 구현)
DFS는 하나의 경로를 끝까지 탐색한 후, 찾고 싶은 노드가 아니라면 다음 경로로 넘어가 탐색한다.

• 장점 : 모든 노드를 완전히 탐색할 수 있다.
• 단점 : BFS보다 탐색 시간은 조금 오래 걸린다.
• 공통점 : 모든 정점을 한 번만 방문한다
  

하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번만에 경로를 찾을 수 있습니다. 또 미국으로 가는 길이 아님을 미리 체크할 수 있다면, 바로 그 순간 다음 탐색으로 넘어갈 수 있습니다.

한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용합니다. 만약, BFS로 탐색하게 된다면 제일 첫 번째 경로가 미국행이라도, 다른 모든 경로를 살펴보아야 합니다.

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

queaue 을 이용해서 구현)
한국을 기준으로 미국까지 가는 방법을 가까운 정점부터 탐색한다.

• 장점 : 주로 두 정점 사이의 최단 경로를 찾을 때 사용합니다.
• 단점 : 최악의 경우에는 모든 경로를 다 살펴보아야 합니다. (찾는 데이터가 마지막 노드에 있을때)
• 공통점 : 모든 정점을 한 번만 방문한다
  
  그리고 더는 탐색할 정점이 없을 때, 그다음 떨어져 있는 정점을 순서대로 방문합니다. 직항이라면 한국과 미국 사이에 어떠한 경유지도 없기 때문에 제일 가까운 정점에 미국이 있습니다. 경유지가 있다면 직항보다 거리가 멀다는 사실을 확인할 수 있습니다. 이렇게, 너비를 우선적으로 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색이라고 합니다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용합니다. 만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 확인해야한다.

출처
코드스테이츠
엔지니어대한민국