JavaScript中图用邻接表（对象/Map+数组/Set）或邻接矩阵（二维数组）表示；常用DFS（递归/栈）和BFS（队列）遍历；带权图需Dijkstra等算法；开发优先选邻接表，注意有向/无向区别与序列化问题。

JavaScript 中的“图”（Graph）是一种非线性数据结构，由顶点（Vertex/Node）和边（Edge）组成，用来表示实体及其之间的关系。它不强调层级或顺序，而是灵活建模多对多、循环、路径依赖等场景，比如社交网络、网页跳转、城市路线、依赖关系图等。

图在 JavaScript 中怎么表示？

图没有原生类型，常用两种方式手动实现：

• 邻接表（Adjacency List）：用对象或 Map 存储每个顶点，值是该顶点直接连接的顶点列表（数组或 Set）。空间效率高，适合稀疏图（边少），日常开发最常用。

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C']
};
// 或用 Map + Set 避免重复和方便增删
const graphMap = new Map();
graphMap.set('A', new Set(['B', 'C']));
graphMap.set('B', new Set(['A', 'D']));

• 邻接矩阵（Adjacency Matrix）：用二维数组（或二维布尔/数值矩阵）表示，matrix[i][j] 为 true 或权重值，表示顶点 i 到 j 是否有边。适合稠密图（边多）、需频繁查两点是否相连的场景，但空间复杂度为 O(V²)。

// 顶点按顺序映射为索引：A→0, B→1, C→2, D→3
const matrix = [
  [0, 1, 1, 0], // A 连 B、C
  [1, 0, 0, 1], // B 连 A、D
  [1, 0, 0, 1], // C 连 A、D
  [0, 1, 1, 0]  // D 连 B、C
];

图的常见搜索算法怎么写？

图搜索目标通常是遍历所有可达节点、找路径、检测环或求最短距离。核心是避免重复访问，需用集合（Set）记录已访问节点。

• 深度优先搜索（DFS）：用递归或栈模拟。适合路径探索、连通分量、拓扑排序（有向无环图）。

function dfs(graph, start, visited = new Set()) {
  if (visited.has(start)) return;
  visited.add(start);
  console.log(start);
  for (const neighbor of graph[start] || []) {
    dfs(graph, neighbor, visited);
  }
}

• 广度优先搜索（BFS）：用队列（数组 shift 或更优的 deque 实现）。适合找无权图的最短路径、层序遍历、最小跳数问题。

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set([start]);
  
  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node);
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

带权重图和更复杂需求怎么办？

如果边有权重（如距离、耗时），基础 DFS/BFS 不再适用最短路径。此时需升级算法：

• 单源最短路径 → 用 Dijkstra 算法（要求权重非负），借助优先队列（JS 可用最小堆库或简单数组模拟）；
• 含负权边 → 用 Bellman-Ford；
• 所有点对最短路径 → 用 Floyd-Warshall（适合小规模顶点）；
• 判断是否有环 → 对有向图用 DFS 标记三种状态（未访问/访问中/已访问），或用 Kahn 算法做拓扑排序；
• 找强连通分量（有向图）→ 用 Kosaraju 或 Tarjan 算法。

实际开发中要注意什么？

真实项目很少从零手写图算法，但理解底层很重要：

• 优先选邻接表，除非明确需要 O(1) 边存在性查询且顶点数稳定且不大；
• 顶点名尽量用字符串或 Symbol，避免数字索引导致歧义；
• 处理有向图和无向图要区分：无向图加边时需双向添加（A→B 和 B→A）；
• 注意循环引用风险——JSON.stringify 图会报错，序列化时需自定义逻辑；
• 大型图建议用成熟库，如 graphology（功能全、性能好）、cytoscape.js（侧重可视化）。