(알고리즘) BFS/DFS

그래프 탐색 목적 : 모든 정점(vertex)들을 한 번씩 방문(탐색)하는 것

그래프의 데이터는 배열처럼 정렬되어 있지 않기 때문에 원하는 자료를 찾기 위해서 하나씩 모두 방문해야 한다.

 

출처: https://velog.io/@vagabondms/DFS-vs-BFS

 

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

시작점에서 가장 가까운 depth의 정점을 순서대로 방문. 주로 두 정점 사이의 최단 경로를 찾을 때 사용

만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 탐색해야할 수도 있다.

알고리즘 구현 : 큐를 이용해 다음에 탐색할 노드 저장. 노드 수가 많을수록 더 큰 저장 공간이 필요

 

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

하나의 경로를 끝가지 탐색한 후, 목표 도착지가 없다면 다음 경로로 넘어가 탐색.

하나의 노선을 끝가지 들어가서 확인하고 다음으로 넘어가기 때문에 운이 좋다면 단 몇 번만에 경로를 찾을 수도 있다.

또는 목표 도착지로 가는 길이 아님을 미리 체크할 수 있다면 바로 그 순간 다음 탐색으로 넘어갈 수 있다.

한 경로를 완벽하게 탐색할 때 사용. BFS보다 탐색 시간이 오래 걸릴 수도 있지만 모든 노드를 탐색할 수 있다.

알고리즘 구현 : 재귀호출 사용

 

질문

• DFS와 BFS의 장단점은 또 무엇이 있을까요? DFS(장점: BFS에 비해 저장공간의 필요성이 적다. 단점: 찾은 경로가 최단 경로라는 보장없음)
• 그래프가 굉장히 크다면 어떤 탐색 기법을 고려해야 할까요? 탐색시간을 줄이기 위해 BFS를 사용?
• 반대로, 그래프의 규모가 작고, depth가 얕다면 어떤 탐색 기법을 고려해야 할까요? DFS사용