데이터는 선형구조와 비선형구조로 이루어져 있으며, 순차적으로 나열된 선형 구조에 비해서 비선형구조의 데이터는 탐색이 비교적 어렵다.
비선형 구조에서 탐색을 하기 위해서 BFS, DFS를 사용하는데 두 탐색 방법 모두 무차별 탐색(Brute Force Search, 모든 데이터를 하나씩 탐색) 방법을 사용한다.
자바스크립트에서는 DFS와 BFS를 구현하기 위해서 노드와 노드가 연결된 간선을 객체의 형태로 표현을 해야한다. 각각의 노드가 키로 사용되며, 연결된 노드들은 배열의 형태로 해당 키의 값에 사용된다. 위의 사진과 같은 트리는 다음과 같은 객체로 표현된다.
const graph = {
1: [2, 3],
2: [1, 4, 5],
3: [1, 6, 7],
4: [2, 8, 9],
5: [2, 10, 11],
6: [3, 12, 13],
7: [3, 14, 15]
}1. DFS(Depth First Search)
루트 노드에서 시작하여 한 분기(갈래)를 모두 방문하고 다음 분기로 넘어가는 방식이다. 인접한 노드를 깊이 우선으로 탐색하기 때문에 깊이 우선 탐색, DFS라고 부른다.
DFS의 예로는 미로가 있는데, 경로의 존재여부를 판별할 때 유용하게 사용된다.
위의 트리 구조에서 DFS는 A-B-D-F-H-L-I-M-P-C-E-G-J-N-K-O의 순서로 탐색한다.
구현
한 개의 스택과 한 개의 큐를 사용해서 DFS를 구현한다. DFS는 BFS와 달리 이전 노드가 아니라 자기 자신과 연결되었던 노드들을 먼저 탐색하기 때문에 스택을 사용한다.
// graph, 시작 노드
const dfs = (graph, startNode) => {
let needVisitStack = []; // 탐색을 해야 할 노드들
let visitedQueue = []; // 탐색을 마친 노드들
// 시작 노드부터 탐색 시작
needVisitStack.push(startNode);
// 탐색을 해야 할 노드가 남아 있다면 반복
while (needVisitStack.length !== 0) {
const node = needVisitStack.pop();
if (!visitedQueue.includes(node)) {
visitedQueue.push(node);
needVisitStack = [...needVisitStack, ...graph[node]];
}
}
return visitedQueue;
}
console.log(dfs(graph, 1));
// [1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15]
2. BFS(Breadth First Search)
정점에서부터 같은 레벨에 있는 노드들을 먼저 탐색하는 방식이다. 형제 노드들을 먼저 탐색하기 때문에 점점 넓어지는 모습을 보여 너비 우선 탐색이라 부른다.
두 개의 큐를 통해서 구현하며, 루트에서 가까운 노드들부터 탐색이 들어가므로 최단거리를 탐색할 때 유용하게 사용된다. 큐에 각 노드의 정보를 기록하기 때문에 메모리를 많이 사용하는 단점이 있으며 주로 타겟으로 하는 노드가 루트와 가깝게 있다고 예상될 때 BFS를 사용한다.
지도 어플에서 특정 위치까지의 최단거리, 소셜미디어의 친구 추천 등에서 이용된다.
구현
자신과 연결된 자식 노드들을 바로 탐색하기 때문에 두 개의 큐로 구현한다.
// graph, 시작 노드를 인자로 받음
const bfs = (graph, startNode) => {
let visited = []; // 탐색을 마친 노드들
let needVisit = []; // 탐색해야할 노드들
needVisit.push(startNode); // 노드 탐색 시작
while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
visited.push(node);
needVisit = [...needVisit, ...graph[node]];
}
}
return visited;
};
console.log(bfs(graph, "A"));
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]시간복잡도
DFS와 BFS는 노드의 수와 간선의 수만큼의 복잡도를 가지고 있다. 따라서 시간복잡도는 O(n) 이다.
