图结构的两种表示方法：邻接表与邻接矩阵

图是一种强大的非线性数据结构，用于表示对象间的多对多关系，广泛应用于社交网络、导航和推荐系统等领域。本文深入探讨了图的定义、特点及其在JavaScript中的实现方式，重点介绍了**邻接表**和**邻接矩阵**两种主流表示方法。邻接表通过对象或数组存储顶点的相邻顶点，尤其适合稀疏图和动态操作；而邻接矩阵则使用二维数组表示顶点间的连接关系，更适用于稠密图。文章还提供了使用JavaScript实现图结构的示例代码，包括添加顶点、边，以及广度优先搜索（BFS）和深度优先搜索（DFS）等关键操作，助你轻松掌握图结构在JS中的应用。选择合适的图表示方法，优化你的数据结构，提升程序性能！

图在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, 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）是实现这两种遍历的核心机制。实际项目里，你可能还会遇到带权图（边有权重）、有向图（边有方向）、多重图（两点间有多条边）等更复杂的场景，但核心的表示和遍历思想是相通的，只需在边的存储和遍历逻辑上做相应调整。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~