Thuật toán Breadth-First Search (BFS) là một trong những thuật toán cơ bản để duyệt đồ thị. BFS bắt đầu từ một đỉnh gốc và thăm tất cả các đỉnh kề của nó trước khi đi sâu hơn vào các đỉnh tiếp theo. BFS sử dụng hàng đợi (queue) để theo dõi các đỉnh cần thăm.
Dưới đây là cách thực hiện thuật toán BFS trên đồ thị trong JavaScript:
Mã Nguồn:
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(v1, v2) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1); // Nếu đồ thị có hướng thì chỉ cần v1 -> v2
}
// BFS sử dụng hàng đợi
bfs(start) {
const queue = [start];
const result = [];
const visited = {};
let currentVertex;
visited[start] = true;
while (queue.length) {
currentVertex = queue.shift();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor => {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
});
}
return result;
}
}
// Khởi tạo đồ thị và thêm các cạnh
let graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');
// Thực hiện BFS từ đỉnh 'A'
console.log(graph.bfs('A')); // Output: [ 'A', 'B', 'C', 'D', 'E', 'F' ]
Giải Thích:
-
Khởi Tạo Đồ Thị:
- addVertex: Thêm một đỉnh vào đồ thị.
- addEdge: Thêm một cạnh giữa hai đỉnh. Nếu đồ thị có hướng, chỉ cần thêm cạnh từ đỉnh v1 tới v2.
-
BFS Sử Dụng Hàng Đợi:
- queue: Sử dụng một hàng đợi để lưu trữ các đỉnh cần thăm. Khởi tạo hàng đợi với đỉnh bắt đầu.
- visited: Một đối tượng để theo dõi các đỉnh đã được thăm.
- result: Một mảng để lưu trữ các đỉnh theo thứ tự thăm.
- currentVertex: Đỉnh hiện tại đang được thăm.
- Duyệt Đồ Thị: Sử dụng vòng lặp
whileđể tiếp tục thăm các đỉnh cho đến khi hàng đợi rỗng. Mỗi đỉnh hiện tại được lấy từ đầu hàng đợi, thêm vàoresult, và các đỉnh kề chưa được thăm của nó được thêm vào cuối hàng đợi và đánh dấu đã thăm.
Tổng Quan:
- BFS Sử Dụng Hàng Đợi: BFS duyệt các đỉnh theo chiều rộng, thăm các đỉnh kề trước khi đi sâu hơn, sử dụng hàng đợi để quản lý các đỉnh cần thăm.
- Thích Hợp Cho Tìm Kiếm Ngắn Nhất: BFS thường được sử dụng để tìm đường đi ngắn nhất trong đồ thị không trọng số.
Ưu Điểm và Hạn Chế:
- Ưu Điểm: Đơn giản, dễ hiểu, hiệu quả cho đồ thị không trọng số và tìm đường đi ngắn nhất.
- Hạn Chế: Sử dụng nhiều bộ nhớ hơn DFS khi đồ thị có nhiều nhánh rộng.
Ví Dụ Thực Tế:
// Khởi tạo đồ thị và thêm các cạnh
let graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');
// Thực hiện BFS từ đỉnh 'A'
console.log(graph.bfs('A')); // Output: [ 'A', 'B', 'C', 'D', 'E', 'F' ]
Trong ví dụ trên, BFS bắt đầu từ đỉnh 'A' và thăm lần lượt các đỉnh theo thứ tự: A, B, C, D, E, F.
Comments