📍 DFS(깊이 우선 탐색) BFS(너비 우선 탐색)은 그래프를 탐색하는 대표적인 방법이다.
📝 1. DFS(깊이 우선 탐색)
시작한 노드에서 최대한 깊이 내려간 뒤, 더이상 내려갈 노드가 없으면 옆으로 이동
출처 https://developer-mac.tistory.com/64
✏️ 개념
임의의 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
- 모든 노드를 방문하고자 하는 경우
- DFS가 BFS보다 좀 더 간단함
- 검색 속도 자체는 BFS에 비해 느림
📝 2. BFS(너비 우선 탐색)
시작한 노드에 연결된 모든 노드에 접근하고, 다 접근했으면 다음 노드로 내려가 이러한 동작 반복
출처 https://developer-mac.tistory.com/64
✏️ 개념
임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 두 노드 사이의 최단 경로를 찾고 싶을 때 사용
- 깊이 우선 탐색은 모든 친구 관계를 살펴보게 될 수 있음
- 너부 우선 탐색은 원하는 노드의 모든 경로를 먼저 볼 수 있음
📝 3. DFS와 BFS 비교
| DFS | BFS |
|---|---|
| 현재 정점에서 갈 수 있는 점들까지 들어가며 탐색 | 현재 정점에 연결된 가까운 점들부터 탐색 |
| 스택이나 재귀로 구현 | 큐를 이용해 구현 |
✏️ 시간복잡도
둘 다 다음 노드가 방문하였는지 확인하는 시간과 각 노드를 방문하는 시간을 합하면 되기에 시간 복잡도는 동일
- 인접 리스트 : O(N + E)
- 인접 행렬 : O(N^2)
인접 행렬은 거의 모든 노드가 간선으로 연결 되었을 때 사용하면 효율적
하지만 거의 그럴 일은 없기에 인접 리스트를 사용하는 것이 일반적이다
✏️ 활용한 문제 유형
DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있다.
1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없다.
2) 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용한다. (BFS는 경로의 특징을 가지지 못함)
3) 최단거리 구해야 하는 문제
최단거리를 구해야 할 경우, BFS가 유리하다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문이다.
이밖에도
- 검색 대상 그래프가 정말 크다면 DFS를 고려
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
📝 4. 코드(JAVA)
- DFS Java로 구현(재귀사용)
/* 인접 리스트 이용, 재귀이용 */
class Graph {
private int V;
private LinkedList<Integer> adj[];
Graph(int v) {
V = v;
adj = new LinkedList[v];
// 인접 리스트 초기화
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) { adj[v].add(w); }
/* DFS */
void DFS(int v) {
boolean visited[] = new boolean[V];
// v를 시작 노드로 DFSUtil 재귀 호출
DFSUtil(v, visited);
}
/* DFS에 의해 사용되는 함수 */
void DFSUtil(int v, boolean visited[]) {
// 현재 노드를 방문한 것으로 표시하고 값을 출력
visited[v] = true;
System.out.print(v + " ");
// 방문한 노드와 인접한 모든 노드를 가져온다.
Iterator<Integer> it = adj[v].listIterator();
while (it.hasNext()) {
int n = it.next();
// 방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출
if (!visited[n])
DFSUtil(n, visited);
}
}
}- BFS Java로 구현 (큐 사용)
class Graph {
private int V;
private LinkedList<Integer> adj[];
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
void addEdge(int v, int w) { adj[v].add(w); }
/* BFS */
void BFS(int s) {
boolean visited[] = new boolean[V]; //방문여부 확인용 변수
LinkedList<Integer> queue = new LinkedList<Integer>(); //연결리스트 생성
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
// 방문한 노드를 큐에서 추출(dequeue)하고 값을 출력
s = queue.poll();
System.out.print(s + " ");
// 방문한 노드와 인접한 모든 노드를 가져온다.
Iterator<Integer> i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
// 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입(enqueue)
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
}