그래프를 탐색하는 알고리즘의 하나로, 시작 정점으로부터 하나의 방향을 잡아 끝까지 탐색한 후 마지막 분기점으로 돌아와 다시 다른 방향으로 끝까지 탐색을 반복하는 방식.
DFS알고리즘은 스택(Stack) 자료 구조나 재귀를 통해서 구현할 수 있다.
function dfs(graph, start, visited) {
const stack = [];
stack.push(start);
while (stack.length) {
let v = stack.pop();
if (!visited[v]) {
console.log(v);
visited[v] = true;
for (let node of graph[v]) {
if (!visited[node]) {
stack.push(node);
}
}
}
}
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);
dfs(graph, 0, visited);
// 0 4 3 2 5 1
재귀 함수는 항상 탈출 조건이 있어야 함을 기억하자!
const dfs = (graph, v, visited) => {
// 현재 노드를 방문 처리
visited[v] = true;
console.log(v);
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (let node of graph[v]) {
if (!visited[node]) {
dfs(graph, node, visited);
}
}
}
const graph = [[1, 2, 4], [0, 5], [0, 5], [4], [0, 3], [1, 2]];
const visited = Array(7).fill(false);
dfs(graph, 0, visited);
// 0 1 5 2 4 3
예를 들어 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제와 같이 각각의 경로마다 특징을 저장해야 할 때 DFS를 주로 사용한다.
단지 현 경로상의 정점들만을 기억하면 되므로 저장 공간의 수요가 비교적 적고, 목표한 정점이 깊은 단계에 있으면 방문할 수 있는 루트를 빨리 구할 수 있다는 장점이 있다.
백트래킹 = 더 이상 탐색할 필요가 없다면, 앞선 선택으로 되돌아와 탐색을 반복
DFS = 그래프의 탐색 기법으로 단순하게 이어진 길을 쭉 반복하는 과정
실제로 둘은 뗄레야 뗄 수 없다네요... DFS에서 백트래킹을 자주 사용한다고 함.
가장 먼저 시작 정점을 방문한 후, 그 시작 정점과 인접한 모든 정점들을 우선적으로 탐색해나가는 방법
출발점을 먼저 큐에 넣고, 큐가 빌 때까지 아래 과정을 반복한다.
Dequeue
한다.length
가 0
이 아닐 때 까지 아래 과정을 반복const graph = {
A: ["B", "C"],
B: ["A", "D"],
C: ["A", "G", "H", "I"],
D: ["B", "E", "F"],
E: ["D"],
F: ["D"],
G: ["C"],
H: ["C"],
I: ["C", "J"],
J: ["I"]
};
// graph 자료구조와 startNode를 입력
const BFS = (graph, startNode) => {
let visited = []; // 탐색을 마친 노드들
let needVisit = []; // 탐색해야할 노드들
needVisit.push(startNode); // 노드 탐색 시작
while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
const node = needVisit.shift(); // 가장 오래 남아있던 정점을 뽑아냄.
if (!visited.includes(node)) { // 해당 노드 방문이 처음이라면,
visited.push(node);
needVisit = [...needVisit, ...graph[node]];
}
}
return visited;
};
console.log(BFS(graph, "A"));
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]
DFS와 BFS는 노드 수 + 간선 수 만큼의 복잡도를 지닌다. 즉, O(n)