当前位置：首页 > JavaScript

js实现图

2026-02-28 19:40:53JavaScript

实现图的基本结构

在JavaScript中，图（Graph）可以通过邻接表或邻接矩阵实现。邻接表适合稀疏图，节省空间；邻接矩阵适合稠密图，便于快速查询。

邻接表实现

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(vertex1, vertex2) {
    this.adjacencyList.get(vertex1).push(vertex2);
    this.adjacencyList.get(vertex2).push(vertex1); // 无向图需双向添加
  }
}

邻接矩阵实现

class Graph {
  constructor(numVertices) {
    this.matrix = Array(numVertices)
      .fill()
      .map(() => Array(numVertices).fill(0));
  }

  addEdge(v1, v2) {
    this.matrix[v1][v2] = 1;
    this.matrix[v2][v1] = 1; // 无向图需对称设置
  }
}

图的遍历算法

图的遍历包括深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

dfs(startVertex) {
  const visited = new Set();
  const _dfs = (vertex) => {
    visited.add(vertex);
    console.log(vertex);
    for (const neighbor of this.adjacencyList.get(vertex)) {
      if (!visited.has(neighbor)) {
        _dfs(neighbor);
      }
    }
  };
  _dfs(startVertex);
}

广度优先搜索（BFS）

bfs(startVertex) {
  const visited = new Set();
  const queue = [startVertex];
  visited.add(startVertex);

  while (queue.length) {
    const vertex = queue.shift();
    console.log(vertex);
    for (const neighbor of this.adjacencyList.get(vertex)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

图的路径算法

常见路径算法包括Dijkstra（最短路径）和拓扑排序（有向无环图）。

js实现图

Dijkstra算法（加权图最短路径）

dijkstra(startVertex) {
  const distances = {};
  const priorityQueue = new PriorityQueue();
  this.adjacencyList.forEach((_, vertex) => {
    distances[vertex] = vertex === startVertex ? 0 : Infinity;
    priorityQueue.enqueue(vertex, distances[vertex]);
  });

  while (!priorityQueue.isEmpty()) {
    const currentVertex = priorityQueue.dequeue().value;
    for (const neighbor of this.adjacencyList.get(currentVertex)) {
      const edgeWeight = 1; // 假设权重为1，实际需根据具体图调整
      const newDistance = distances[currentVertex] + edgeWeight;
      if (newDistance < distances[neighbor]) {
        distances[neighbor] = newDistance;
        priorityQueue.enqueue(neighbor, newDistance);
      }
    }
  }
  return distances;
}

拓扑排序（有向无环图）

topologicalSort() {
  const visited = new Set();
  const result = [];
  const _visit = (vertex) => {
    visited.add(vertex);
    for (const neighbor of this.adjacencyList.get(vertex)) {
      if (!visited.has(neighbor)) {
        _visit(neighbor);
      }
    }
    result.unshift(vertex); // 逆序插入
  };
  this.adjacencyList.forEach((_, vertex) => {
    if (!visited.has(vertex)) _visit(vertex);
  });
  return result;
}

实际应用示例

社交网络关系图

const socialGraph = new Graph();
socialGraph.addVertex("Alice");
socialGraph.addVertex("Bob");
socialGraph.addVertex("Charlie");
socialGraph.addEdge("Alice", "Bob");
socialGraph.addEdge("Bob", "Charlie");
socialGraph.bfs("Alice"); // 输出: Alice, Bob, Charlie

路径规划（Dijkstra）

const cityGraph = new Graph();
cityGraph.addVertex("A");
cityGraph.addVertex("B");
cityGraph.addVertex("C");
cityGraph.addEdge("A", "B", 4); // 假设权重为4
cityGraph.addEdge("B", "C", 2);
console.log(cityGraph.dijkstra("A")); // 输出: { A: 0, B: 4, C: 6 }

标签: js