图在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, CB -> A, CC -> 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 = this.numVertices || 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 = this.numVertices || 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个朋友，用邻接矩阵就需要1000×1000的二维数组，而邻接表只存储1000个节点和1000×10个边。动态性好： 添加或删除顶点、边都相对灵活，不需要像邻接矩阵那样频繁调整大小或重建。遍历邻居快： 获取一个顶点的所有邻居非常直接，直接访问对应的列表即可。
但它的缺点是：
判断两点间是否有边稍慢： 需要遍历一个顶点的邻居列表，最坏情况下是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, F
2. 深度优先搜索 (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）是实现这两种遍历的核心机制。实际项目里，你可能还会遇到带权图（边有权重）、有向图（边有方向）、多重图（两点间有多条边）等更复杂的场景，但核心的表示和遍历思想是相通的，只需在边的存储和遍历逻辑上做相应调整。
以上就是图的定义是什么？JS如何表示图结构的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1517724.html
微信扫一扫 
支付宝扫一扫 
