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 方法从指定顶点开始深度优先搜索。

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 方法从指定顶点开始深度优先搜索。

打赏

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,您说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在