Hi~，我是 一碗周，一个在舒适区垂死挣扎的前端，如果写的文章有幸可以得到你的青睐，万分有幸~
🫐 写在前面
在上一篇文章中我们用了很大的篇幅来介绍红黑树，这篇文章我们来简单的学习一下图这个数据结构。
🍊 什么是图
数据结构中的图并不是图片的图，而是网络结构的抽象模型，更具体的说图是一组由边连接的节点。
图在我们的生活中无处不在，它可以用来表示任何的二元关系，例如北京的地铁线路图：
上图来源于网络，侵删
图这个数据结构还可以分为有向图和无向图，所谓的有向图和无向图就是有没有方向，如下图：
每个边也可以有权重，这个权重可以说是边的值，在地图中非常有用，例如上面的地铁线路图，这个权重可以表示两个站的距离。
🍉 JavaScript表示图
JavaScript并没有图这个数据结构，我们可以使用对象和数组来构建一个图。
图的表示方式通常为两种：
- 临界矩阵
邻接表
🍋 邻接矩阵表示法
使用邻接矩阵表示法时，我们让邻接矩阵中的每个节点和一个数组相关联，使用二维数组来表示，如下图：
在上图中，二维数组中的1表示有连线，0表示没有连线。
🍌 邻接表表示法
使用邻接表表示法时，邻接表由图中每个顶点以及和顶点相邻的顶点列表组成，这个列表可以是个数组，链表字典等结构；如下图所示：
🍍 图的常用操作
图的常用操作有两个，一个深度优先遍历，一个广度优先遍历，现在用下面这个图来实现这两个遍历：
const graph = {
A: ['B', 'D'],
B: ['A', 'C'],
C: ['B', 'E', 'G'],
D: ['A'],
E: ['C', 'F'],
F: ['E', 'G'],
G: ['C', 'F', 'H'],
H: ['G'],
}
module.exports = graph
🥭 深度优先遍历
实现深度优先遍历的思路如下：
访问根节点
对根节点中没有访问过 （避免重复访问）的相邻节点进行深度优先遍历。
实现代码如下：
const graph = require('./graph')
// 记录已经访问的节点
const visited = new Set()
const dfs = n => {
console.log(n)
// 把已经当问的节点加入集合
visited.add(n)
// 访问所有节点
graph[n].forEach(c => {
if (!visited.has(c)) {
dfs(c)
}
})
}
dfs('A')
/* * 结果*
A B C E F G H D*
/🍎 广度优先遍历
实现广度优先遍历的思路如下：
新建一个队列，把根节点入队；
把队头出队并访问；
把队头的没访问过的相邻节点入队；
重复前面两个步骤直到队列为空。
实现代码如下：
const graph = require('./graph')
// 记录已经访问的节点
const visited = new Set()
// 将根节点记录为已经访问过
visited.add('A')
// 定义一个队列
const q = ['A']
while (q.length) {
// 队头出队
const n = q.shift()
console.log(n)
// 相邻节点依次入队
graph[n].forEach(c => {
if (!visited.has(c)) {
q.push(c)
visited.add(c)
}
})
}
/* * 结果*
A B D C E G F H*
/
🍏 写在最后
这篇文章就简单的介绍了一下图这个数据结构，实现了深度优先搜索和广度优先搜索两个算法。
本专栏采用JavaScript作为编程语言，从前端的角度去介绍数据结构与算法，如果对你所有帮助，可以点个关注支持一下啊\~
