首页 > 文章 > 前端

图算法与JavaScript数据结构详解

时间：2025-12-09 16:07:41 454浏览收藏

推广推荐

支持 PC / 移动端，安全直达

一分耕耘，一分收获！既然都打开这篇《图算法实现与JavaScript数据结构解析》，就坚持看下去，学下去吧！本文主要会给大家讲到等等知识点，如果大家对本文有好的建议或者看到有不足之处，非常欢迎大家积极提出！在后续文章我会继续更新文章相关的内容，希望对大家都有所帮助！

图由顶点和边组成，可用邻接表或矩阵表示；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从起始顶点出发，逐层遍历相邻节点，常用于找最短路径（未加权图）。

实现说明：

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

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

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 
<p>注：MinPriorityQueue需额外实现，可用数组排序模拟，或引入外部库简化。</p>

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

好了，本文到此结束，带大家了解了《图算法与JavaScript数据结构详解》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！

图算法