💡 知识点抢先看

什么是图结构？
图结构有什么应用场景？
图结构有什么方法？
如何实现一个图结构？
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 方法

实现这个方法的关键在于，理清每一个层级之间的关系

实现思路

先遍历顶点列表
在邻接表中找到顶点列表对应的对象
拼接字符串，实现输出

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());

输出结果战术

符合我们的预期，完成封装

七、LeetCode 实战

推荐几道 LeetCode 中关于图结构的题目

65. 有效数字

417. 太平洋大西洋水流问题

133. 克隆图

207. 课程表

997. 找到小镇的法官

📖 总结

在这篇文章中我们详细讲解了图结构，如何表示一个图结构，如何手写一个图结构，博主在自己写博客的时候，也能学到很多东西，从理解到实现，都需要站在另一个角度去思考，如何能清晰的将内容输出，也希望各位读者能从这个系列的文章中真正的学习到一些东西~

本文关于图的内容就到这里结束了，相信你一定能从中学到很多东西。接下来我们将开启算法之路，可能这段时间还不会更新这部分的内容，还请耐心等待