NodeJs实现深度优先搜索（Depth-First Search，DFS）算法

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);

代码说明：

1. Graph 类:

   • 使用 Map 来存储图的邻接表。

2. addVertex 方法: 向图中添加顶点。

3. addEdge 方法: 向图中添加边。

4. dfs 方法: 初始化访问集合并调用辅助函数开始搜索。

5. dfsUtil 方法: 递归函数，用于访问节点及其相邻节点。

6. 测试 DFS 实现:

   • 创建图对象并添加顶点和边。
   • 调用 dfs 方法从指定顶点开始深度优先搜索。