大家好，我是小丞同学，一名大二的前端爱好者
这篇文章将讲解数据结构中的图
非常感谢你的阅读，不对的地方欢迎指正
愿你忠于自己，热爱生活
知识点抢先看
什么是图结构？
图结构有什么应用场景？
图结构有什么方法？
如何实现一个图结构？
LeetCode 实战
欢迎大家关注本专栏，持续关注最新文章~
本专栏的其他内容
从这里开始 【化解数据结构】从这里开启数据结构和算法
栈 【化解数据结构】什么是栈？手写实现一个栈结构!
队列 【化解数据结构】详解队列，优先队列，循环队列，并实现一个队列
集合 【化解数据结构】详解集合结构，并实现一个集合
字典 【化解数据结构】详解字典结构，并实现一个字典
树 【化解数据结构】详解树结构，并实现二叉搜索树
堆 【化解数据结构】详解堆结构，并实现最小堆结构
碎碎念
太棒了，这篇文章是数据结构部分的最后一篇文章了，敲键盘都累了，呼呼~，图结构是一个我认为非常有意思的结构，它能表示我们生活中很常见的场景，也能解决很多的问题，一起来探寻一下吧
一、什么是图结构？
图结构是一种网络结构的抽象模型，是一组由边连接而成的节点
同时图可以表示任何二元关系，比如道路、航班…
那为什么可以表示二元关系呢？
因为图中的每一条边都是由两个节点相连而成的，因此图可以表示任何二元关系
在我们生活中，每天使用的微信等社交软件，我们的好友关系网也能被形象成一种图结构，如图，图能表示各种丰富的关系结构
在 JS 中没有图结构，我们可以用对象或者数组来构建一个图结构
如此抽象的图结构，我们该如何来表示它们呢，我们这里会讲到 3 中方法
邻接矩阵
邻接表
关联矩阵
二、图的相关术语
一个图由 G = (V,E) 组成，V 表示一组顶点， E 表示一组边，连接 V 中的顶点
就例如，下面这个图结构，key 表示顶点，value 表示与这个顶点相连的节点
const graph = { 0: [1, 2], 1: [2], 2: [0, 3], 3: [3] };
术语 含义
顶点 图的基本单元，也就是图中的节点
边 顶点之间的关联关系，被称为边
相邻顶点 由一条边连接在一起的顶点
度 一个顶点包含的相邻顶点的数量
如何来理解这些术语呢？我们来结合图结构解释一下
还是这个图，我们对节点 A 分析一下
A节点和 B 节点相邻，A 和 D 是相邻的，A 和 C 是相邻的，A 和 E 不是相邻的，因此 A 节点和 B,C,D 是相邻节点
图中的每一个节点都能作为顶点存在
A 节点的度，由于 A 与其他三个节点相连，因此 A 节点的度为 3 ，图中的 D 节点和其他 4 个节点相连，因此它的度为 4
可以看到图中 CDG 形成了一个环，因此这个图也称为有环的
如果图中每两个顶点间存在路径，则图是连通的
有向图
图中节点之间边线是单向的
无向图
图中节点之间的边线是双向的，或者没有方向，称为无向图
三、如何表示一个图？
图的表示有很多种方法，不存在绝对的方法，需要根据待解决的问题来确定图的类型
1. 邻接矩阵
我们可以采用一个二维数组来确定顶点间的连接关系，如果 A 能连接到 B 那么我们就置为 1 ，如果连不到就是 0
如图 A 连接 B 节点，因此 第一行第二列为 1，表示 A 连接 B
2. 邻接表
采用邻接表来表示一个图更形象更容易理解
它直接就表示哪个顶点和哪个顶点连接，十分清晰
如图 B 节点连接 C,D 节点，C节点连接 E 节点，十分的方便，推荐使用
四、图的操作
接下来的操作基于这个图结构来进行，这是用一个邻接表来表示的一个图结构
const graph = { 0:[1, 2], 1:[2], 2:[0, 3], 3:[3] }
1. 深度优先遍历（DFS）
尽可能深的搜索图的分支，类似于树的前序遍历
先访问根节点
对根节点的没访问过的相邻节点挨个进行深度优先遍历
代码实现
// 记录访问过的节点 const visited = new Set() // 深度优先遍历 const dfs = (n) => { console.log(n); visited.add(n) // 获取所有相邻节点 graph[n].forEach(c => { // 如果没有访问过 if (!visited.has(c)) { dfs(c) } }) } // 根节点 dfs(2)
输出结果 ：2 0 1 3
2. 广度优先遍历（BFS）
先访问离根节点最近的节点，类似于树的层序遍历
遍历的方法
新建一个队列，把根节点入队并访问
把对头没有访问过的相邻节点入队
重复，直至队列为空
代码实现
// 广度优先遍历 const bfs = (n) => { const visited = new Set(); visited.add(n); const q = [n]; while (q.length) { const n = q.shift(); console.log(n); graph[n].forEach(c => { if (!visited.has(c)) { q.push(c) visited.add(c); } }); } }
输出结果：2 0 3 1
还有很多类似于最短路径、拓扑排序、关键路径等问题，难度有点大，就不讨论了有兴趣的自己去研究吧~
五、图结构有哪些方法？
根据上面的介绍，我们对图结构有了一定的了解，接下来我们封装一个图结构，首先，先了解图结构有哪些方法
方法 含义
addVertex(value) 向图中添加一个顶点
addEdge(a,b) 向图中添加两点之间的边
getVertices() 返回图的顶点列表
toString() 以字符串的形式输出
六、手写实现无向图结构
1. 创建 Graph 类
首先我们需要创建一个 Graph 构造函数，用来存放图中的属性和方法
在这里我们添加了两个属性，一个 vertices 用来保存顶点， edgs 表示邻接表
class Graph { constructor() { this.vertices = [] // 保存顶点 this.edges = [] // 保存边，相当于邻接表 } }
2. 实现 addVertex 方法
添加这个顶点，我们先判断一下图中有没有这个顶点，有的话我们就不添加了，没有的话，添加到顶点列表中，同时添加到邻接表中来建立边关系
addVertex(value) { // 如果没有这个顶点 if(!this.vertices.includes(value)){ this.vertices.push(value) // 添加到顶点列表中 this.edges[value] = [] // 添加到邻接表中 } }
3. 实现 addEdge 方法
我们通过这个方法来建立边连接的关系，接收两个参数，表示需要进行连接的两个节点，当这两个节点都存在，并且没有进行连接时，我们再进行邻接表的修改操作，具体实现就是，将 a 放到 b 的连接数组中，b 放到 a 的连接数组中
addEdge(a,b) { if(this.vertices.includes(a) && this.vertices.includes(b)) { if(!this.edges[a].includes(b)) { this.edges[a].push(b) this.edges[b].push(a) } } }
4. 实现 getVertices 方法
只需要返回我们的顶点数组即可
getVertices() { return this.vertices }
5. 实现 toString 方法
实现这个方法的关键在于，理清每一个层级之间的关系
采用数组来实现邻接表，会造成遍历是时间复杂度变高，个人认为后期可以采用 map 或者 set 类进行实现
实现思路
先遍历顶点列表
在邻接表中找到顶点列表对应的对象
拼接字符串，实现输出
toString() { let s = ""; // 遍历图的顶点列表 for (let i = 0; i < this.vertices.length; i++) { // 采用模板字符串进行拼接 s += `${this.vertices[i]} -> `; // 获取顶点对应的邻接表数组 const neighbors = this.edges[this.vertices[i]] //遍历该邻接表数组，解构数组成字符串 for (let j = 0; j < neighbors.length; j++) { s += `${neighbors[j]} `; } // 每一个顶点单独成行 s += "\n"; } return s; }
这样一个简单的图结构，我们就实现了
6. 演示
基于上面的代码我们进行操作演示
const graph = new Graph() graph.addVertex(2) graph.addVertex(1) graph.addVertex(3) graph.addVertex(0) graph.addEdge(0,1) graph.addEdge(0,2) graph.addEdge(1,2) graph.addEdge(2,3) console.log(graph.toString());
输出结果战术
符合我们的预期，完成封装
