拓扑排序数据结构代码 中的图非常感谢你的阅读，不对的地方欢迎指正>

你们好，我是小丞朋友，一名大二的后端爱好者

这篇文章将讲解数据结构中的图

特别谢谢你的阅读，不对的地方欢迎见谅

>愿你忠于自己，热爱生活

知识点抢鲜看

碎碎念

太棒了，这篇文章是数据结构部份的最后一篇文章了，敲按键都累了，呼呼~，图结构是一个我觉得十分有意思的结构，它能表示我们生活中很常见的场景，也能解决好多的问题，一上去找寻一下吧

一、什么是图结构？

图结构是一种网路结构的具象模型，是一组由边联接而成的节点

同时图可以表示任何二元关系，例如公路、航班…

那为何可以表示二元关系呢？

在我们生活中，每天使用的陌陌等社交软件，我们的好友关系网也能被形象成一种图结构，如图，图能表示各类丰富的关系结构

在JS中没有图结构，我们可以用对象或则链表来建立一个图结构

这么具象的图结构，我们该怎么来表示它们呢，我们这儿会提到3中技巧

二、图的相关术语

一个图由G=(V,E)组成，V表示一组顶点，E表示一组边，联接V中的顶点

就比如，下边这个图结构，key表示顶点，value表示与这个顶点相连的节点

const graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
};

怎样来理解这种术语呢？我们来结合图结构解释一下

还是这个图，我们对节点A剖析一下

有向图

图中节点之间边线是双向的

无向图

图中节点之间的边线是单向的，或则没有方向，称为无向图

三、如何表示一个图？

图的表示有好多种方式，不存在绝对的方式，须要依照待解决的问题来确定图的类型

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)

输出结果：2013

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

输出结果：2031

还有好多类似于最短路径、拓扑排序、关键路径等问题，难度有点大，就不讨论了有兴趣的自己去研究吧~

五、图结构有什么方式？

按照前面的介绍，我们对图结构有了一定的了解，接出来我们封装一个图结构，首先，先了解图结构有什么方式

六、手写实现无向图结构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());

输出结果战术

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

七、LeetCode实战

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

65.有效数字417.太平洋大西洋水流问题133.克隆图207.课程表997.找到小镇的法院总结

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

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

欢迎你们关注本专栏，持续关注最新文章~

彩蛋

数据结构和算法之路还没有结束，这篇文章的结束，也只是基础数据结构告一段落了，在数据结构当中，还有相对多的中级内容没有涉及，比如哈希表的实现、单调栈、红黑树、AVL树等等等…这种内容都须要我们在未来的日子中不断学习，不断积累，能够有更多的收获，在未来的日子里，希望和你们一起学习，交流，共同进步~

在这儿特别谢谢你们近几天来的阅读和交流

同时也特别谢谢周日妈妈对我的帮助和鼓励，很幸好能在后端路上遇到

最后，可能在好多地方讲诉的不够清晰，请指正

假如文章有哪些错误的地方，或则有哪些疑惑，欢迎留言，也欢迎私信交流