[알고리즘] 그래프의 깊이 우선 탐색과 너비 우선 탐색

이 내용은 프로그래밍 대회에서 배우는 알고리즘 문제해결전략이라는 도서를 통해 공부한 내용을 정리하였습니다.

탐색 알고리즘이란?

트리의 순회와 같이 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색 알고리즘이라고 한다.

탐색 과정을 통해 어떤 간선이 사용되었는지, 또 어떤 순서로 정점들이 방문되었는지를 통해 그래프의 구조를 알 수 있다.

 

깊이(depth) 우선 탐색이란?

그래프의 모든 정점을 발견하는 가장 방법으로서 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 존재한다면 해당 간선을 따라간다. gif 이미지를 통해 보면 다음과 같다.

즉, 이름 그대로 자식 노드를 먼저 탐색하고, 그 다음 형제 노드를 탐색하는 방법이 dfs이다.

 

깊이 우선 탐색의 중요한 특징은 더 따라갈 간선이 없을 경우에 이전으로 돌아간다는 점이다. 이를 구현하기 위해서는 지금까지 거쳐온 정점들을 모두 저장해두어야하는데, 재귀 호출을 이용해 이를 구현할 수 있다.

 

 

너비(breadth) 우선 탐색이란?

시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘을 너비 우선 탐색이라고 한다.

 

 

위 gif에서도 알 수 있듯이, 자식 노드를 먼저 방문하는 dfs와는 달리 형제 노드를 먼저 방문하는 것이 bfs임을 알 수 있다.

이미지에서는 검정색으로 바뀐 것이 해당 노드를 지나고 있음을 나타낸다.

 

너비 우선 탐색은 각 정점을 방문할 때마다 모든 인접 정점을 검사한다. 이 중 처음 보이는 정점을 발견하면 이 정점을 방문 예정이라고 기록해둔 뒤, 별도의 위치에 저장한다. 인접한 정점을 모두 검사하고 나면 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문하게 된다. 따라서 너비우선탐색의 방문 순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정된다.

 

너비 우선 탐색에서의 각 정점들은 다음과 같은 세 개의 상태를 순서대로 거쳐가게 된다.

1. 아직 발견되지 않음

2. 발견되었으나 방문하지 않음. (이 정점들은 queue에 저장됨.)

3. 방문

 

위 두 알고리즘을 어떤 상황에 사용하느냐를 정립하기 위해서는 두 알고리즘의 장단점을 파악해야한다.

	장점	단점
DFS	구현이 bfs보다 간단하다. 현재 경로상의 노드만 기억하면 되기에 저장 공간이 bfs에 비해 덜필요하다. 목표 노드가 깊은 노드에 있을 경우 해를 빨리 구할 수 있다.	단순 검색은 bfs가 더 빠르다. 해가 없는 경우에 빠질 수 있다. dfs는 해를 구하면 탐색이 종료되기 때문에 이 해가 최단 경로라는 보장이 없다.
BFS	너비를 우선으로 탐색하기에 최단경로임을 보장한다. 최단 경로가 존재한다면, 경로가 깊어진다하더라도 반드시 최단 경로를 찾을 수 있다. 노드의 수가 적고 깊이가 얕은 해가 존재할 때 유리하다.	다음에 탐색할 노드를 저장해야하는 공간이 필요하다. 노드의 수가 늘어나면 탐색해야할 노드가 많아지기 때문에 현실적으로 어렵다.

 

 

참고 자료 및 출처

• 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 2
• dfs 이미지 출처: https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
• bfs 이미지 출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89