Thuật toán Depth-First Search (DFS) là một trong những thuật toán cơ bản để duyệt đồ thị. DFS bắt đầu từ một đỉnh gốc và đi sâu vào từng nhánh cho đến khi không còn đỉnh nào để đi tiếp, sau đó quay lại để thăm các đỉnh chưa được thăm.
Dưới đây là cách thực hiện thuật toán DFS trên đồ thị trong JavaScript, sử dụng cả phương pháp đệ quy và phương pháp sử dụng ngăn xếp (stack).
1. DFS Đệ Quy
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
}
// DFS đệ quy
dfsRecursive(start) {
const result = [];
const visited = {};
const adjacencyList = this.adjacencyList;
(function dfs(vertex) {
if (!vertex) return;
visited[vertex] = true;
result.push(vertex);
adjacencyList[vertex].forEach(neighbor => {
if (!visited[neighbor]) {
return dfs(neighbor);
}
});
})(start);
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 DFS đệ quy từ đỉnh 'A'
console.log(graph.dfsRecursive('A')); // Output: [ 'A', 'B', 'D', 'E', 'C', 'F' ]
2. DFS Sử Dụng Ngăn Xếp (Stack)
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
}
// DFS sử dụng ngăn xếp (stack)
dfsIterative(start) {
const stack = [start];
const result = [];
const visited = {};
let currentVertex;
visited[start] = true;
while (stack.length) {
currentVertex = stack.pop();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor => {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.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 DFS sử dụng ngăn xếp từ đỉnh 'A'
console.log(graph.dfsIterative('A')); // Output: [ 'A', 'C', 'E', 'F', 'D', 'B' ]
Giải Thích:
-
DFS Đệ Quy:
- Khởi tạo một đối tượng
Graphvà thêm các đỉnh và cạnh. - Hàm
dfsRecursivesử dụng một hàm đệ quy ẩn danh để duyệt qua các đỉnh của đồ thị. - Một mảng
visitedđược sử dụng để theo dõi các đỉnh đã được thăm, tránh vòng lặp vô hạn. - Bắt đầu từ đỉnh
start, hàm đệ quy thăm các đỉnh liên kết và thêm chúng vào mảngresult.
- Khởi tạo một đối tượng
-
DFS Sử Dụng Ngăn Xếp:
- Tương tự, nhưng sử dụng một ngăn xếp thay vì đệ quy.
- Hàm
dfsIterativekhởi tạo ngăn xếp với đỉnhstartvà duyệt qua các đỉnh bằng cách thêm các đỉnh kề chưa thăm vào ngăn xếp. - Đỉnh hiện tại được thăm và thêm vào mảng
result.
Tổng Quan:
- DFS Đệ Quy: Dễ hiểu và ngắn gọn, nhưng có thể gặp vấn đề stack overflow nếu đồ thị quá lớn.
- DFS Sử Dụng Ngăn Xếp: Thực hiện tương tự như DFS đệ quy nhưng sử dụng ngăn xếp để tránh vấn đề stack overflow.
Comments