[JAVA] BFS와 DFS

BFS와 DFS는 그래프나 트리구조에서 모든 노드를 탐색할 때 사용되는 알고리즘이다.

BFS와 DFS에 대해 알아보고, 두 개념의 차이에 대해서 알아보도록 하자.

 

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

BFS는 시작 노드에서 인접한 노드를 먼저 탐색하는 방식이다.

 

BFS의 접근 방식을 차례대로 알아보자.

 1) 시작점(1번 노드)에 접근한다.

 2) 시작점과 인접한 노드인 2,3,4번 노드에 차례대로 접근한다.

 3) 2,3,4번 노드에 인접한 그 다음 노드들에 접근한다.

 

이 구조를 살펴보면 시작점에서 depth가 1인 노드가 모두 접근되고,

이후에 depth가 2인 노드가 접근이 되는 형태인 것을 알 수 있다.

 

BFS는 선입선출 구조인 큐를 이용하여 구현할 수 있다.

 

이전에 말했던 접근 방식을 큐로 예시를 들어보자.

 1) 시작점(1번 노드)를 큐에 넣는다.

      큐 : 1

 2) 1번 노드를 삭제하면서, 1번 노드와 인접한 2,3,4번 노드를 큐에 넣는다.

      큐 : 2, 3, 4

 3) 2번 노드를 삭제하면서, 2번 노드와 인접한 5,6번 노드를 큐에 넣는다.

      큐 : 3, 4, 5, 6

 4) 3번 노드를 삭제하면서, 3번 노드와 인접한 7번 노드를 큐에 넣는다.

      큐 : 4, 5, 6, 7

 5) 4번 노드를 삭제하면서, 4번 노드와 인접한 8, 9번 노드를 큐에 넣는다.

      큐 : 5, 6, 7, 8

 6) 계속해서 같은 행위를 큐가 완전히 빌 때까지 반복한다.

 

이 과정을 잘 살펴보면, 큐에 들어오는 노드들이 시작점에서 가까운 것부터 차례대로 들어온다.

따라서 최단 경로를 찾기 위한 알고리즘으로 많이 쓰인다.

 

 

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

DFS는 시작점에서 한 방향으로 갈 수 있는 만큼 깊이 탐색한 후,

더 이상 갈 수 없으면 가장 가까운 지름길로 되돌아와 다른 경로를 탐색하는 방식이다.

 

DFS의 방식은 다음과 같다.

 1) 시작점(1번 노드)에 접근한다.

 2) 1번노드의 경로는 2, 5, 7이 있고, 가장 앞에 있는 2번 노드에 접근한다.

 3) 2번 노드의 경로는 3, 4가 있고, 가장 앞에 있는 3번 노드에 접근한다.

 4) 3번 노드에는 더 이상 경로가 없으므로 가장 가까운 2번 노드로 가서 새로운 경로인 4번 노드에 접근한다.

 5) 위와 같은 방식을 모든 노드에 접근할 때 까지 반복한다.

 

자세히 살펴보면 각 노드에서는 다음과 같은 행동이 반복된다.

자신의 하위 노드 중 방문하지 않은 가장 앞 노드를 방문한다.

또한, 하위의 노드를 모두 방문하면 부모 노드로 돌아간다.

 

따라서, DFS는 스택 또는 재귀를 이용해서 구현할 수 있다.

 

간단하게 스택으로 구현을 해보면 다음과 같다.

 1) 1번 노드를 스택에 넣는다.

      스택 : 1

 2) 1번 노드를 삭제하면서, 1번 노드와 인접한 7, 5, 2를 스택에 넣는다.

      스택 : 7, 5, 2

 3) 2번 노드를 삭제하면서, 2번 노드와 인접한 4, 3을 넣는다.

      스택 : 7, 5, 4, 3

 4) 3번 노드를 삭제한다. 인접한 노드가 없으므로 추가는 하지 않는다. ( 4번 노드도 동일)

      스택 : 7, 5

  5) 5번 노드를 삭제한다. 5번 노드와 인접한 6번 노드를 추가한다.

      스택 : 7, 6

  6) 계속해서 스택이 완전히 빌 때 까지 반복한다.

 

3. BFS와 DFS의 차이점

실제로 BFS와 DFS의 시간 복잡도는 O(V+E)로 동일하다.

(V = 노드 수, E = 간선 수)

 

하지만, 검색 속도는 DFS가 BFS에 비해 느리다.

BFS는 가운데 점을 기준으로 퍼져나가는 형태이고, DFS는 한방향씩 차례대로 보는 형태이기 때문이다.

BFS는 시작 지점에서 가까운 노드를 빨리 찾을 수 있다.

 

또한, DFS는 깊이 우선 탐색으로 인해 깊이가 길어질수록 스택에 많은 노드를 저장해야 하기 때문에 공간복잡도가 크다.

항목	BFS(Breadth First Search)	DFS(Depth First Search)
자료 구조	큐	스택 또는 재귀
주요 특징	레벨별 탐색, 최단 경로 탐색에 적합	깊이 탐색, 백트래킹에 적합
탐색 속도	시작 노드에 가까운 노드를 빨리 찾음 분기 수가 많아도 효율적	목표 노드가 깊이 있을 경우 오래 걸림 분기 수가 많으면 시간 소요 증가
사용 예	최단 경로 탐색, 최단 거리 문제	특정 경로 찾기, 사이클 탐색, 위상 정렬, 백트래킹

 

4. 추천자료

https://bbangson.tistory.com/42

[Java] DFS, BFS 정리