图在JavaScript中常用邻接表表示，适合稀疏图和动态操作，邻接矩阵适用于顶点固定且边密集的场景，边列表则用于特定算法；实际应用如社交网络、导航和推荐系统均依赖图结构。
图，简单来说，就是由一些“点”（我们称之为顶点或节点）和连接这些点的“线”（我们称之为边）构成的抽象结构。它最核心的作用是用来描述事物之间的关系。在JavaScript中，表示图结构最常见也最灵活的方式是使用邻接表（Adjacency List），当然，邻接矩阵（Adjacency Matrix）和边列表（Edge List）也是可选的方案，具体用哪种，得看你的实际需求和图的特性。
解决方案
在JavaScript中表示图结构，我个人最常用且推荐的是邻接表。它本质上是一个映射（Map或Object），每个键代表一个顶点，而对应的值通常是一个数组或Set，里面存储着与该顶点直接相连的所有邻居顶点。这种方式对于稀疏图（边相对较少）来说，在空间效率上表现出色。
1. 邻接表 (Adjacency List)
class Graph {
constructor() {
this.adjList = new Map(); // 使用Map来存储邻接表，键是顶点，值是Set（方便快速去重和查找）
}
addVertex(vertex) {
if (!this.adjList.has(vertex)) {
this.adjList.set(vertex, new Set()); // 新增顶点，并初始化一个空的邻居集合
}
}
addEdge(vertex1, vertex2, isDirected = false) {
// 确保两个顶点都存在
if (!this.adjList.has(vertex1)) {
this.addVertex(vertex1);
}
if (!this.adjList.has(vertex2)) {
this.addVertex(vertex2);
}
this.adjList.get(vertex1).add(vertex2); // 添加从vertex1到vertex2的边
if (!isDirected) { // 如果是无向图，需要双向添加
this.adjList.get(vertex2).add(vertex1);
}
}
removeVertex(vertex) {
if (!this.adjList.has(vertex)) return;
// 移除所有指向该顶点的边
for (let [v, neighbors] of this.adjList.entries()) {
neighbors.delete(vertex);
}
// 移除顶点自身
this.adjList.delete(vertex);
}
removeEdge(vertex1, vertex2, isDirected = false) {
if (this.adjList.has(vertex1) && this.adjList.get(vertex1).has(vertex2)) {
this.adjList.get(vertex1).delete(vertex2);
}
if (!isDirected && this.adjList.has(vertex2) && this.adjList.get(vertex2).has(vertex1)) {
this.adjList.get(vertex2).delete(vertex1);
}
}
getNeighbors(vertex) {
return this.adjList.get(vertex) || new Set();
}
printGraph() {
for (let [vertex, neighbors] of this.adjList.entries()) {
console.log(`${vertex} -> ${[...neighbors].join(', ')}`);
}
}
}
// 示例使用
// const myGraph = new Graph();
// myGraph.addVertex('A');
// myGraph.addVertex('B');
// myGraph.addEdge('A', 'B');
// myGraph.addEdge('B', 'C');
// myGraph.addEdge('A', 'C', true); // 有向边 A -> C
// myGraph.printGraph();
/*
A -> B, C
B -> A, C
C -> B
*/2. 邻接矩阵 (Adjacency Matrix)
当图的顶点数量固定且边非常密集时，邻接矩阵可能是一个不错的选择。它使用一个二维数组
matrix[i][j]来表示顶点
i和顶点
j之间是否存在边（通常用1表示有边，0表示无边，或者存储边的权重）。
// 假设顶点是0到n-1的数字
class AdjacencyMatrixGraph {
constructor(numVertices) {
this.numVertices = numVertices;
this.matrix = Array(numVertices).fill(0).map(() => Array(numVertices).fill(0));
}
addEdge(v1, v2, weight = 1, isDirected = false) {
if (v1 < 0 || v1 >= this.numVertices || v2 < 0 || v2 >= this.numVertices) {
console.error("Invalid vertex index.");
return;
}
this.matrix[v1][v2] = weight;
if (!isDirected) {
this.matrix[v2][v1] = weight;
}
}
hasEdge(v1, v2) {
if (v1 < 0 || v1 >= this.numVertices || v2 < 0 || v2 >= this.numVertices) {
return false;
}
return this.matrix[v1][v2] !== 0;
}
getWeight(v1, v2) {
if (this.hasEdge(v1, v2)) {
return this.matrix[v1][v2];
}
return null;
}
// ... 其他操作，比如移除边、获取邻居等，都围绕这个二维数组展开
}3. 边列表 (Edge List)
最简单粗暴的方式，就是直接列出所有的边，每条边通常表示为一个包含两个顶点（和可能的权重）的数组。这种方式在图算法的某些特定阶段可能会用到，比如Kruskal算法（需要对边进行排序），但对于图的遍历和邻居查询则效率较低。
// const edgeList = [
// ['A', 'B'],
// ['B', 'C'],
// ['A', 'C', { weight: 5, type: 'friend' }] // 也可以存储额外信息
// ];图在现实世界中到底有什么用？为什么它这么重要？
说实话，我一直觉得图是计算机科学里最优雅也最实用的抽象之一，它把复杂的关系网变得一目了然。你可能每天都在和图打交道，只是没意识到。比如，我们用的各种社交网络，像微信朋友圈、微博关注，它们的关系链条就是典型的图结构，每个人是一个节点，关注或好友关系就是边。推荐系统也是图的天下，它会分析你和商品、你和朋友、朋友和商品之间的关系，然后给你推荐可能喜欢的东西。
再比如，导航系统，从A点到B点怎么走最快？这不就是找图上最短路径的问题吗？每个路口是节点，每段路是边，边的权重可以是距离或时间。甚至我们日常的项目管理，任务之间的依赖关系，哪个任务必须先完成，哪个可以并行，这都可以用图来清晰地表示和调度。还有软件工程里的依赖管理（比如npm包之间的依赖），编译器的AST（抽象语法树），数据库的关系模型，这些背后都有图论的影子。理解图，就像是掌握了一种描述世界底层逻辑的强大工具。
邻接表和邻接矩阵，我到底该选哪个？
这是一个很实际的问题，我在做项目时也经常权衡。其实没有绝对的“最好”，只有“最适合”。
邻接表的优势在于：
- 空间效率高： 对于稀疏图（边数远小于顶点数的平方），它只存储实际存在的边，所以占用的内存更少。想一下，如果一个图有1000个节点，但每人只认识10个朋友，用邻接矩阵就需要1000x1000的二维数组，而邻接表只存储1000个节点和1000x10个边。
- 动态性好： 添加或删除顶点、边都相对灵活，不需要像邻接矩阵那样频繁调整大小或重建。
- 遍历邻居快： 获取一个顶点的所有邻居非常直接，直接访问对应的列表即可。
但它的缺点是：
- 判断两点间是否有边稍慢： 需要遍历一个顶点的邻居列表，最坏情况下是O(度)的时间复杂度。
邻接矩阵的优势在于：
-
查询效率高： 判断任意两点之间是否有边，是O(1)的操作，直接访问
matrix[i][j]
就行。 - 实现简单： 对于固定数量的顶点，用二维数组表示直观且易于实现。
它的缺点是：
- 空间效率低： 对于稀疏图，它会存储大量的0，造成空间浪费。
- 动态性差： 如果需要添加或删除顶点，通常需要重新构建整个矩阵，这在JS中尤为麻烦。
我的选择偏好： 通常情况下，我个人更倾向于使用邻接表。原因很简单，大多数实际应用中的图都是稀疏的，而且对动态性有要求。比如社交网络，你不可能预先知道会有多少用户，以及用户之间会有多少边。只有当你明确知道图的顶点数量是固定的，并且图非常密集（比如完全图），或者你需要频繁地执行“查询任意两点间是否有边”这种操作时，我才会考虑邻接矩阵。
实际操作中，如何用JS实现图的常见操作？
图的基本操作除了上面提到的添加/删除顶点和边，最核心的莫过于图的遍历了。理解遍历是掌握图算法的关键一步，因为很多复杂的图问题（比如最短路径、连通分量）都是在遍历的基础上进行的。
1. 广度优先搜索 (BFS - Breadth-First Search)
BFS就像在水面上扩散的波纹，它会一层一层地访问节点，先访问起始节点的所有邻居，再访问这些邻居的邻居，以此类推。它通常用于寻找最短路径（在无权图中）或者遍历所有可达节点。
// 基于前面定义的Graph类
Graph.prototype.bfs = function(startVertex) {
const visited = new Set();
const queue = [startVertex]; // 使用数组模拟队列
visited.add(startVertex);
while (queue.length > 0) {
const currentVertex = queue.shift(); // 取出队列头部元素
console.log(`Visited: ${currentVertex}`); // 访问当前节点
for (const neighbor of this.getNeighbors(currentVertex)) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor); // 将未访问的邻居加入队列
}
}
}
};
// 示例：
// const bfsGraph = new Graph();
// bfsGraph.addEdge('A', 'B');
// bfsGraph.addEdge('A', 'C');
// bfsGraph.addEdge('B', 'D');
// bfsGraph.addEdge('C', 'E');
// bfsGraph.addEdge('D', 'F');
// bfsGraph.bfs('A'); // 输出顺序可能是 A, B, C, D, E, F2. 深度优先搜索 (DFS - Depth-First Search)
DFS则像是在迷宫里探险，它会尽可能深地探索一条路径，直到无路可走，然后回溯，再探索另一条路径。DFS通常用于检测环、拓扑排序、寻找连通分量等。
// 基于前面定义的Graph类
Graph.prototype.dfs = function(startVertex) {
const visited = new Set();
const _dfs = (vertex) => {
visited.add(vertex);
console.log(`Visited: ${vertex}`); // 访问当前节点
for (const neighbor of this.getNeighbors(vertex)) {
if (!visited.has(neighbor)) {
_dfs(neighbor); // 递归访问未访问的邻居
}
}
};
_dfs(startVertex);
};
// 示例：
// const dfsGraph = new Graph();
// dfsGraph.addEdge('A', 'B');
// dfsGraph.addEdge('A', 'C');
// dfsGraph.addEdge('B', 'D');
// dfsGraph.addEdge('C', 'E');
// dfsGraph.addEdge('D', 'F');
// dfsGraph.dfs('A'); // 输出顺序可能是 A, B, D, F, C, E (取决于邻居的迭代顺序)实现这些操作时，通常会用到一个
visited集合来跟踪已经访问过的节点，避免无限循环（尤其是在有环图中）。而队列（BFS）和递归调用栈（DFS）是实现这两种遍历的核心机制。实际项目里，你可能还会遇到带权图（边有权重）、有向图（边有方向）、多重图（两点间有多条边）等更复杂的场景，但核心的表示和遍历思想是相通的，只需在边的存储和遍历逻辑上做相应调整。
