DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

첫 정점에서부터 그래프에 존재하는 모든 정점들을 한 번씩 방문하는 것을 그래프의 탐색이라고 한다.

그래프의 탐색 방법에는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 2가지 방식이 있다.

말 그대로 '깊이'를 우선시해서 탐색하는지, '너비'를 우선시해서 탐색하는지에 차이가 있다.

아래 그림을 보면서 이해해보도록 하자.

DFS / BFS

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

---

깊이 우선 탐색 DFS는 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다.

간단히 재귀호출(Recurse)을 사용하여 구현하거나, 스택(Stack)을 사용하여 구현한다.

스택으로 구현할 때는 모든 노드가 중복 없이 딱 한 번씩만 담겨야 하고, 재귀로 구현할 때도 노드 방문 여부를 반드시 체크해서 무한루프에 빠지지 않게 주의해야 한다.

DFS를 사용하는 경우는 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다고 한다.

 

 

탐색 과정

1. 스택에 시작 노드 push, 방문 체크

2. 스택 최상단 노드에

    2-1) 방문하지 않은 인접 노드가 있으면 → 해당 노드 push, 방문 체크

    2-2) 방문하지 않은 인접 노드가 없으면 → 최상단 노드 pop

3. 2단계 반복

 

DFS의 장점

1. 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다.

2. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

3. BFS보다 간단히 구현 가능하다.

 

DFS의 단점

1. 해가 없는 경로가 깊을 경우 탐색 시간이 오래 걸릴 수 있다.

2. 얻어진 해가 최단 경로가 된다는 보장이 없다.

 

DFS의 과정 정리

 

깊이 우선 탐색(DFS)의 시간 복잡도

 

- DFS는 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함

 

인접 리스트로 표현된 그래프 : O(N+E)

인접 행렬로 표현된 그래프 : O(N^2)

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

---

BFS는 최대한 넓게 옆으로 이동한 후, 더 이상 갈 곳이 없을 때 아래로 이동하며 탐색하는 방법이다.

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

일반적으로 큐(Queue)를 이용해 구현 가능한데, 현재 위치에서 접근 가능한 모든 노드들을 큐에 넣는 형식이다.

이 때도 마찬가지로 해당 노드 방문 여부를 체크해야 한다.

BFS를 사용하는 경우는 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

 

동적으로 무한하게 생성되는 인터넷 페이지를 크롤링할 때, 가비지 컬렉션에도 BFS 방식이 사용된다고 한다.

EX) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우

깊이 우선 탐색의 경우는 모든 친구 관계를 다 살펴봐야 할지도 모른다.

하지만 너비 우선 탐색의 경우는 Ash와 가까운 관계부터 탐색하면 된다.

 

탐색 과정

1. 큐에 시작 노드 enqueue, 방문 체크

2. 큐에서 노드를 하나씩 꺼내며

    해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 enqueue, 방문 체크

3. 2단계 반복

 

BFS의 장점

1. 가능한 경로가 여러 개여도 최단 경로임을 보장

    (현재 노드에서 가까운 곳부터 찾기 때문에, 경로 탐색 시 먼저 찾는 경로가 곧 최단거리)

2. 최단경로 존재 시, 깊이가 아무리 깊어져도 언젠간 찾음

3. 검색 속도 자체는 DFS보다 빠름

4. 노드 수가 적고, 깊이가 얕을 때 빠름

 

BFS의 단점

1. 경로가 길어지면 메모리를 많이 요구함

    (DFS와 달리 다음에 탐색할 노드까지 저장해야 하기 때문)

2. 유한 그래프(해가 없을 때) → 모든 그래프 탐색 후 실패로 끝남

3. 무한 그래프 → 해를 찾지도, 끝내지도 못함

 

 

BFS의 과정 정리

깊이가 1인 모든 노드를 방문하고 나서 그다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

 

✅정리

DFS

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.

2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.

3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느리다.

 

BFS

1. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

2. 즉 깊게(Deep) 탐색하기 전에 넓게(Wide) 탐색하는 것

3. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

4. 선입선출(FIFO) 원칙으로 탐색한다.

 

 

DFS vs BFS

출처: https://joooing.tistory.com/entry/DFS깊이우선탐색-BFS너비우선탐색?category=914235