Data Structure & Algorithm
알고리즘, Tree, BFS
준희닷
2024. 6. 27. 16:30
너비 우선 탐색(Breadth-First Search, BFS)은 그래프 또는 트리의 노드를 탐색하는 방법 중 하나입니다. BFS는 시작 노드에서 출발하여 인접한 노드를 먼저 탐색하고, 그 다음 인접한 노드들의 인접 노드를 탐색하는 방식으로 진행됩니다. 이는 주로 큐(queue) 자료 구조를 사용하여 구현됩니다.
BFS의 특징
- 레벨별 탐색: BFS는 트리 또는 그래프의 레벨을 기준으로 노드를 탐색합니다. 즉, 첫 번째 레벨(루트 노드)에서 시작하여 다음 레벨로 진행합니다.
- 최단 경로 탐색: 무방향 그래프에서 BFS는 시작 노드에서 다른 노드로 가는 최단 경로를 찾을 수 있습니다.
- 큐 사용: BFS는 FIFO(First In, First Out) 특성을 가진 큐를 사용하여 다음에 탐색할 노드를 관리합니다.
BFS의 구현 (자바스크립트 예제)
트리와 그래프를 위한 BFS의 구현 예제를 살펴보겠습니다.
트리에서의 BFS 구현
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
let newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (value === current.value) return undefined;
if (value < current.value) {
if (current.left === null) {
current.left = newNode;
return this;
}
current = current.left;
} else if (value > current.value) {
if (current.right === null) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
find(value) {
if (!this.root) return false;
let current = this.root;
let found = false;
while (current && !found) {
if (value < current.value) {
current = current.left;
} else if (value > current.value) {
current = current.right;
} else {
return true;
}
}
return false;
}
BFS() {
// Create a queue (this can be an array) and a variable to store the values of nodes visited
// Place the root node in the queue
// Loop as long as there is anything in the queue
// Dequeue a node from the queue and push the value of the node into the variable that stroes the nodes
// If there is a left property on the node dequeud - add it to the queue
// If there is a right property on the node dequeued - add it to the queue
// Return the variable that stores the values
let visited = [];
let queue = [];
let currentNode = this.root;
queue.push(currentNode);
while (queue.length) {
currentNode = queue.shift();
visited.push(currentNode.value);
if (currentNode.left) queue.push(currentNode.left);
if (currentNode.right) queue.push(currentNode.right);
}
return visited;
}
}
let tree = new BinarySearchTree();
console.log('tree is:', tree);
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(17);
tree.insert(7);
tree.insert(3);
tree.insert(13);
console.log('tree is:', tree);
console.log(tree.find(13));
console.log(tree.find(19));
console.log('BFS:', tree.BFS());
BFS의 동작 원리
- 큐 초기화: 시작 노드를 큐에 추가합니다.
- 큐가 빌 때까지 반복:
- 큐에서 첫 번째 노드를 꺼내 현재 노드로 설정합니다.
- 현재 노드를 방문 처리하고 결과 목록에 추가합니다.
- 현재 노드의 모든 인접 노드를 큐에 추가합니다(이미 방문한 노드는 제외).
- 반복 종료: 큐가 비면 탐색이 완료되고, 결과 목록을 반환합니다.
BFS의 시간 복잡도
BFS의 시간 복잡도는 그래프의 노드 수(V)와 엣지 수(E)에 따라 O(V + E)입니다. 이는 모든 노드와 엣지를 한 번씩 방문하기 때문입니다. 트리의 경우 노드 수가 n일 때, 시간 복잡도는 O(n)입니다.
BFS는 너비 우선으로 탐색하여 최단 경로를 찾는 문제에 적합하며, 모든 경로를 완전히 탐색해야 할 때 유용하게 사용됩니다.