[JAVA] 간단하게 이해하는 DFS, BFS

그래프 탐색에는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)가 존재한다. 

 

DFS는 리프 노드를 우선적으로 탐색하는 방식이다. 때문에 그래프의 깊이를 우선적으로 탐색하게 되어, 깊이 우선 탐색이라는 이름을 붙이게 된 것이다. DFS는 재귀적인 성격을 띄고 있는데, 이는 해당 노드가 갈 수 있는 곳들 중 리프 노드까지 우선적으로 방문 후, 다시 해당 노드가 갈 수 있는 다른 곳을 찾기 때문이다. 

아래 예시처럼 리프 노드까지 모두 방문하면 다른 곳을 방문하게 된다.

 

 

BFS는 현재 자신이 갈 수 있는 모든 방향을 차례로 접근한다. 때문에 리프 노드를 찾기보다는 본인이 갈 수 있는 같은 깊이의 노드를 모두 찾기 떄문에 해당 이름이 붙여졌다. BFS는 자신이 갈 수 있는 모든 인접 노드를 확인하면서 리프 노드까지 가기 때문에, 순차적이면서 큐 구조의 성격을 갖고 있다. 

아래 예시처럼 현재 상태에서 갈 수 있는 곳을 모두 방문하고 그 이후에 다음 곳을 방문한다.