NodeJs实现深度优先搜索(Depth-First Search,DFS)算法
Node.js 中实现深度优先搜索(DFS)算法,可以使用 JavaScript 语言。以下是一个简单的示例,展示如何使用 DFS 算法搜索图:
class Graph {
constructor() {
this.adjList = new Map();
}
addVertex(vertex) {
if (!this.adjList.has(vertex)) {
this.adjList.set(vertex, []);
}
}
addEdge(vertex, edge) {
if (this.adjList.has(vertex)) {
this.adjList.get(vertex).push(edge);
}
}
dfs(startingNode) {
const visited = new Set();
this.dfsUtil(startingNode, visited);
}
dfsUtil(vertex, visited) {
visited.add(vertex);
console.log(vertex);
const neighbors = this.adjList.get(vertex);
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
this.dfsUtil(neighbor, visited);
}
}
}
}
// 测试 DFS 实现
const g = new Graph();
const vertices = [0, 1, 2, 3, 4, 5];
for (const vertex of vertices) {
g.addVertex(vertex);
}
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
console.log("从顶点 2 开始的深度优先搜索:");
g.dfs(2);
代码说明:
Graph 类:
- 使用
Map
来存储图的邻接表。
- 使用
addVertex 方法: 向图中添加顶点。
addEdge 方法: 向图中添加边。
dfs 方法: 初始化访问集合并调用辅助函数开始搜索。
dfsUtil 方法: 递归函数,用于访问节点及其相邻节点。
测试 DFS 实现:
- 创建图对象并添加顶点和边。
- 调用
dfs
方法从指定顶点开始深度优先搜索。