1. DFS와 BFS
BFS란 Breadth First Search(너비우선탐색)이고 DFS는 Depth First Search(깊이우선탐색)이다. 이 둘은 그래프 자료구조에서 루트 노드에서 시작하여 완전 탐색을 수행하는 탐색 기법이다.
- DFS
DFS는 깊이 우선 탐색으로, 한 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 검색 속도 자체는 BFS에 비해 느리지만 조금 더 간단하다. 스택 혹은 재귀함수를 이용하여 구현한다.
- BFS
BFS는 너비 우선 탐색으로, 아래 그림과 같이 루트 노드에서 탐색을 시작하여 같은 레벨에 있는 노드를 모두 탐색한 다음 하위 레벨로 내려가 또 모두 탐색을 진행하다가, 더이상 탐색할 노드가 없을 때 탐색을 멈추는 방식으로 동작한다. 큐를 이용하여 구현한다.
2. Java에서 DFS와 BFS의 구현
- DFS의 Java구현
DFS는 스택과 재귀함수를 통해 구현할 수 있지만 일반적으로 재귀함수를 통하여 구현한다.
class Graph {
private int V;
private LinkedList<Integer> adj[]; // 링크드리스트의 배열
// constructor
Graph (int v) {
V = v;
adj = new LinkedList[v];
// v개의 LinkedList 선언 및 생성
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList();
}
}
void addEdge (int v, int w) { // v번째 LinkedList 에 w를 삽입
adj[v].add(w);
}
// DFS 함수
void DFS(int v) { // v를 시작노드로!
boolean visited[] = new boolean[V]; // 각 노드이 방문 여부를 저장하기 위해
DFSUtil(v, visited);
}
// DFS에서 호출되는 함수
void DFSUtil(int v, boolean visited[]) {
// 현재 노드를 방문한 것으로 체크 (visited의 v번째 요소를 true로)
visited[v] = true;
System.out.println(v + " ");
// 방문한 노드와 인접한 모든 노드를 가지고 온다
Iterator<Integer> it = adj[v].listIterator();
while (it.hasNext()) {
int n = it.next();
// 방문하지 않은 노드면 해당 노드를 다시 시작 노드로하여 DFSUtil을 호출
if (!visited[n])
DFSUtil(n, visited); // 재귀호출!
}
}
}-
BFS의 Java구현
BFS는 일반적으로 Queue를 이용하여 구현한다.
class Graph {
private int V;
private LinkedList<Integer> adj[]; // 링크드리스트의 배열
// constructor
Graph (int v) {
V = v;
adj = new LinkedList[v];
// v개의 LinkedList 선언 및 생성
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList();
}
}
void addEdge (int v, int w) { // v번째 LinkedList 에 w를 삽입
adj[v].add(w);
}
// DFS 함수
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) {
// 방문한 노드를 큐에서 추출하고 값을 출력
s = queue.poll();
System.out.println(s + " ");
// 방문한 노드와 인접한 모든 노드를 가져온다.
Itertor<Integer> i = adj[s].listIterator();
while (i.hasNext()) {
int n = i.next();
// 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입
if (!visited[n]) {
visited[n] = true;
queue.add();
}
}
}
}
}3. DFS, BFS를 활용하면 좋은 상황
DFS와 BFS를 활용하면 좋은 상황으로는 아래와 같은 상황들이 있다.
(1) 그래프의 모든 정점을 방문하는 것이 주요한 문제: DFS, BFS 모두 무방하다.
(2) 경로의 특징을 저장해둬야 하는 문제: 각 장점에 숫자가 있고 a 부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 하는 경우는 DFS를 사용해야 한다. BFS는 경로의 특징을 저장하지 못한다.
(3) 최단거리를 구하는 문제: BFS가 유리하다. DFS의 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만 BFS의 경우 먼저 찾아지는 해답이 곧 최단거리이기 때문이다.
Reference
