DFS, BFS
DFS, BFS 모두 그래프 탐색 알고리즘 입니다.
그래프 탐색 방향의 우선순위의 차이가 있습니다.
DFS (깊이 우선 탐색, Depth-First Search)
출처 : https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif
DFS는 깊이 우선 탐색 알고리즘으로,
시작점에서 출발하여 한 경로로 깊이 들어가 가능한 한 끝까지 탐색한 후, 더 이상 탐색할 수 없으면 다시 되돌아와 다른 경로를 탐색하는 방식입니다.
장점
- 특정 경로 탐색에 매우 유리합니다.
- BFS와 비교해 메모리를 적게 사용합니다(특히 노드 수가 많을 때).
- 조건을 만족하는 경로를 찾고, 조건을 만족하지 않으면 되돌아가는 문제에서 DFS가 효율적입니다.
동작
- 시작점을 지정합니다.
- 현재 노드를 재방문하지 않도록 방문 처리 합니다.
- 인접 노드를 계속 탐색 합니다.
- 이 경로에서 더 이상 탐색할 인접 노드가 없다면 이전 노드로 돌아가서 다른 경로를 탐색합니다.
- 모든 노드를 방문할때까지 or 조건을 만족하는 노드를 찾을때까지 반복합니다.
구현
재귀함수를 사용한 DFS
// 그래프를 저장할 인접 리스트
private static List<List<Integer>> graph = new ArrayList<>();
// 방문 여부를 저장할 배열
private static boolean[] visited;
private static void DFS(int node) {
visited[node] = true; // 현재 노드 방문 처리
// 현재 노드의 인접 노드를 하나씩 탐색
for (int adjacent : graph.get(node)) {
if (!visited[adjacent]) { // 방문하지 않은 노드가 있으면
DFS(adjacent); // 재귀 호출로 탐색
}
}
}재귀함수를 사용하면 코드가 간결하고 이해하기 쉬우며, 콜 스택을 자연스럽게 활용하여 노드 간의 깊이 우선 탐색을 처리할 수 있습니다. 하지만 그래프의 깊이가 매우 깊을 경우 스택 오버플로우가 발생할 수 있습니다.
스택을 사용한 DFS
private static List<List<Integer>> graph = new ArrayList<>();
private static boolean[] visited;
private static void DFS(int startNode) {
Stack<Integer> stack = new Stack<>();
stack.push(startNode); // 시작 노드를 스택에 추가
while (!stack.isEmpty()) {
int node = stack.pop(); // 스택에서 노드 꺼내기
if (!visited[node]) {
visited[node] = true; // 방문 처리
// 인접한 노드들을 스택에 추가
for (int adjacent : graph.get(node)) {
if (!visited[adjacent]) {
stack.push(adjacent); // 방문하지 않은 인접 노드 스택에 추가
}
}
}
}
}스택을 사용한 구현은 재귀 호출을 사용하지 않고 명시적으로 스택을 사용하여 탐색합니다. 이 방법은 스택 오버플로우 문제를 해결할 수 있고, 재귀에 익숙하지 않은 경우에도 쉽게 사용할 수 있습니다. 다만 코드가 다소 복잡해질 수 있습니다.
BFS(너비 우선 탐색, Breadth-First Search)
출처: https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif
BFS는 너비 우선 탐색 알고리즘으로
시작점에서 인접한 노드에서부터 인접한 노드를 모두 탐색한 후 더 이상 인접한 노드가 없으면 다음 깊이의 노드로 이동하여 더 방문하지 않은 노드가 없을 때 까지 인접한 노드를 탐색하는 방식입니다.
장점
- 최단 경로를 쉽게 찾을 수 있습니다. BFS는 모든 경로를 동시에 탐색하므로, 목표 노드를 가장 먼저 찾았을 때 그 경로가 최단 경로임을 보장합니다.
- BFS는 노드를 레벨별로 탐색하기 때문에 특정 레벨 내에 있는 모든 노드를 쉽게 찾을 수 있습니다.
- BFS는 시작 노드로부터 같은 거리만큼 떨어진 노드들을 모두 탐색한 후, 다음 레벨로 넘어가는 방식이기 때문에 계층적 탐색을 하고자 할 때 BFS가 유리합니다.
동작
BFS는 큐(Queue)를 사용하여 노드들을 순차적으로 탐색합니다.
- 탐색을 시작할 노드를 큐에 넣습니다.
- 큐에서 노드를 하나 꺼내 그 노드를 방문 처리합니다.
- 현재 노드에 인접한 노드들을 확인하여, 아직 방문하지 않은 노드들을 큐에 넣습니다.
- 큐에 더 이상 탐색할 노드가 없을 때까지 반복합니다.
구현
0 — 1 — 2
| |
3 — 4public static void main(String[] args) {
// 그래프 초기화
// 노드 0 -> graph의 인덱스 0에 0과 인접한 노드를 리스트로 저장
graph.add(Arrays.asList(1, 3)); // 노드 0의 인접 노드
graph.add(Arrays.asList(0, 2, 4)); // 노드 1의 인접 노드
graph.add(Arrays.asList(1)); // 노드 2의 인접 노드
graph.add(Arrays.asList(0, 4)); // 노드 3의 인접 노드
graph.add(Arrays.asList(1, 3)); // 노드 4의 인접 노드
// 방문 배열 초기화
visited = new boolean[5];
// BFS 시작 노드를 0으로 설정
BFS(0);
}
private static List<List<Integer>> graph = new ArrayList<>();
private static boolean[] visited;
private static void BFS(int startNode) {
Queue<Integer> queue = new LinkedList<>();
queue.add(startNode); // 시작 노드를 큐에 추가
visited[startNode] = true; // 시작 노드 방문 처리
while (!queue.isEmpty()) {
int node = queue.poll(); // 큐에서 노드를 꺼냄
System.out.println("Visited Node: " + node);
// 현재 노드의 인접 노드를 탐색
for (int adjacent : graph.get(node)) {
if (!visited[adjacent]) { // 방문하지 않은 노드가 있으면
queue.add(adjacent); // 큐에 추가
visited[adjacent] = true; // 방문 처리
}
}
}
}DFS가 BFS보다 메모리를 왜 더 적게 사용하는가?
BFS는 한 번에 많은 노드를 큐에 저장해야 하므로, 너비가 큰 그래프일수록 더 많은 메모리를 사용하게 됩니다.
반면 DFS는 깊이 우선 탐색이므로, 스택에 경로의 깊이 만큼의 노드를 저장하여 메모리 사용량이 적습니다. (재귀함수를 사용하더라도 시스템 스택을 사용하여 메모리 적으로는 크게 다르지 않습니다.)
-
BFS는 너비 우선 탐색 방식으로, 현재 레벨의 모든 노드를 저장한 후 다음 레벨로 넘어갑니다. 특정 노드의 인접 노드들을 모두 한꺼번에 큐에 넣기 때문에, 한 번에 큐에 저장되는 노드의 수가 많아집니다.
-
그래프의 너비가 클수록, 한 번에 탐색해야 하는 인접 노드의 수가 많을수록 큐에 저장해야 하는 노드가 많아지고 메모리 사용량이 커집니다.
