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 不再适用最短路径。此时需升级算法：
立即学习“Java免费学习笔记（深入）”；
- 单源最短路径 → 用 Dijkstra 算法（要求权重非负），借助优先队列（JS 可用最小堆库或简单数组模拟）；
- 含负权边 → 用 Bellman-Ford；
- 所有点对最短路径 → 用 Floyd-Warshall（适合小规模顶点）；
- 判断是否有环 → 对有向图用 DFS 标记三种状态（未访问/访问中/已访问），或用 Kahn 算法做拓扑排序；
- 找强连通分量（有向图）→ 用 Kosaraju 或 Tarjan 算法。
实际开发中要注意什么？
真实项目很少从零手写图算法，但理解底层很重要：
- 优先选邻接表，除非明确需要 O(1) 边存在性查询且顶点数稳定且不大；
- 顶点名尽量用字符串或 Symbol，避免数字索引导致歧义；
- 处理有向图和无向图要区分：无向图加边时需双向添加（A→B 和 B→A）；
- 注意循环引用风险——JSON.stringify 图会报错，序列化时需自定义逻辑；
- 大型图建议用成熟库，如
graphology（功能全、性能好）、cytoscape.js（侧重可视化）。
