J*aScript数据结构_图算法实现_石家庄创泽智能科技有限公司

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

J*aScript数据结构_图算法实现

2025-11-23

浏览次数：次

返回列表

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

javascript数据结构_图算法实现

图是一种用来表示对象之间多对多关系的非线性数据结构，由顶点（节点）和边（连接）组成。在J*aScript中实现图及其常见算法，有助于解决路径查找、依赖分析等问题。下面介绍图的基本实现以及常用的图算法：广度优先搜索（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从起始顶点出发，逐层遍历相邻节点，常用于找最短路径（未加权图）。

实现说明：

使用队列存储待访问节点
用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沿一个方向深入到底，再回溯，适合拓扑排序或连通分量分析。

I-Shop购物系统

部分功能简介：商品收藏夹功能热门商品最新商品分级价格功能自选风格打印结算页面内部短信箱商品评论增加上一商品，下一商品功能增强商家提示功能友情链接用户在线统计用户来访统计用户来访信息用户积分功能广告设置用户组分类邮件系统后台实现更新用户数据系统图片设置模板管理CSS风格管理申诉内容过滤功能用户注册过滤特征字符IP库管理及来访限制及管理压缩，恢复，备份数据库功能上传文件管理商品类别管理商品添加/修改/

0 查看详情 I-Shop购物系统

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

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

  const tr*erse = (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)) {
        tr*erse(neighbor);
      }
    }
  };

  tr*erse(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 };
}