JavaScript数据结构_图算法实现-js教程-PHP中文网

JavaScript数据结构_图算法实现

幻影之瞳

发布： 2025-11-23 21:34:57

原创

232人浏览过

图由顶点和边组成，可用邻接表或矩阵表示；JavaScript中常用邻接表实现无向图。1. 广度优先搜索（BFS）使用队列逐层遍历，适合查找未加权图的最短路径。2. 深度优先搜索（DFS）通过递归或栈深入遍历，适用于连通分量与拓扑排序。3. Dijkstra算法利用优先队列计算带权图的单源最短路径，维护距离表并持续更新邻居节点的最短距离。

javascript数据结构_图算法实现

图是一种用来表示对象之间多对多关系的非线性数据结构，由顶点（节点）和边（连接）组成。在JavaScript中实现图及其常见算法，有助于解决路径查找、依赖分析等问题。下面介绍图的基本实现以及常用的图算法：广度优先搜索（BFS）、深度优先搜索（DFS）和最短路径（Dijkstra算法）。

图的表示与基本结构

图可以用邻接表或邻接矩阵表示。邻接表更节省空间，适合稀疏图；邻接矩阵适合稠密图。这里使用邻接表实现无向图。

代码实现：

class Graph {
  constructor() {
    this.vertices = new Map(); // 存储顶点及其邻接列表
  }

  // 添加顶点
  addVertex(v) {
    if (!this.vertices.has(v)) {
      this.vertices.set(v, []);
    }
  }

  // 添加边（无向图）
  addEdge(v1, v2) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.vertices.get(v1).push(v2);
    this.vertices.get(v2).push(v1);
  }

  // 获取邻接列表
  getAdjacencyList() {
    return this.vertices;
  }
}

登录后复制

广度优先搜索（BFS）

BFS从起始顶点出发，逐层遍历相邻节点，常用于找最短路径（未加权图）。

立即学习“Java免费学习笔记（深入）”；

实现说明：

使用队列存储待访问节点
用Set记录已访问节点，避免重复处理
返回遍历顺序或从起点到目标的路径

bfs(start, callback) {
  const visited = new Set();
  const queue = [start];
  const result = [];

  visited.add(start);

  while (queue.length > 0) {
    const vertex = queue.shift();
    result.push(vertex);

    const neighbors = this.vertices.get(vertex);
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  if (callback) callback(result);
  return result;
}

登录后复制

深度优先搜索（DFS）

DFS沿一个方向深入到底，再回溯，适合拓扑排序或连通分量分析。

基于VC与Matlab的混合编程实现图像的三维显示 WORD版

本文档主要讲述的是基于VC与Matlab的混合编程实现图像的三维显示；介绍了VC++与Matlab混合编程的一般实现方法，并实现对二维影像图的三维效果显示。 MATLAB既是一种直观、高效的计算机语言,同时又是一个科学计算平台。它为数据分析和数据可视化、算法和应用程序开发提供了最核心的数学和高级图形工具。希望本文档会给有需要的朋友带来帮助；感兴趣的朋友可以过来看看

查看详情

实现方式： 使用递归或栈。以下是递归版本。

dfs(start, callback) {
  const visited = new Set();
  const result = [];

  const traverse = (vertex) => {
    if (!vertex) return;
    visited.add(vertex);
    result.push(vertex);

    const neighbors = this.vertices.get(vertex);
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        traverse(neighbor);
      }
    }
  };

  traverse(start);
  if (callback) callback(result);
  return result;
}

登录后复制

Dijkstra最短路径算法

适用于带权图，找出从起点到其他所有顶点的最短路径。

实现要点：

使用优先队列（最小堆），按距离排序
维护每个顶点的最短距离和前驱节点
不断更新邻居的距离值

dijkstra(start) {
  const distances = new Map();
  const previous = new Map();
  const pq = new MinPriorityQueue(); // 可使用简单数组模拟或自定义类

  // 初始化
  for (const vertex of this.vertices.keys()) {
    distances.set(vertex, Infinity);
    previous.set(vertex, null);
  }
  distances.set(start, 0);
  pq.enqueue(start, 0);

  while (!pq.isEmpty()) {
    const { element: current } = pq.dequeue();

    const neighbors = this.vertices.get(current);
    for (const neighbor of neighbors) {
      const edgeWeight = this.getWeight(current, neighbor); // 假设有权重存储
      const newDist = distances.get(current) + edgeWeight;

      if (newDist < distances.get(neighbor)) {
        distances.set(neighbor, newDist);
        previous.set(neighbor, current);
        pq.enqueue(neighbor, newDist);
      }
    }
  }

  return { distances, previous };
}

登录后复制

注：MinPriorityQueue需额外实现，可用数组排序模拟，或引入外部库简化。

基本上就这些。图的实现灵活，结合实际需求调整边的存储方式（如加入权重）即可扩展功能。算法选择取决于具体问题：BFS求无权最短路径，DFS用于探索结构，Dijkstra处理加权最短路径。不复杂但容易忽略细节，比如访问标记和初始化。

以上就是JavaScript数据结构_图算法实现的详细内容，更多请关注php中文网其它相关文章！