图 - 数据结构训练营

从现在开始将开始处理值相互引用的数据结构。 我们有一堆用线连接的 Node (节点)(A、B、C、D……)。 这些节点结构如下所示: Node { value: ..., lines: [(Node), (Node), ...] } 整个图结构如下所示: Graph { nodes: [ Node {...}, Node {...}, ... ] } 实现图数据结构可以提供以下一些运算: 一个生成空图的构造函数; 将节点插入到图中; 判断节点是否在图中; 连接图内的两个节点; 下面我们将依次介绍其实现。 一个生成空图的构造函数 我们将在常规 JavaScript 数组中保存所有节点。这并不是为了保存节点的顺序,而是因为需要一种方法来存储所有内容的引用。 constructor() { this.nodes = []; } 将节点插入到图中 我们可以创建一个没有任何线连接的节点来向图添加值。 addNode(value) { } 判断节点是否在图中 接下来需要能够在图中查找节点。一般数情况下,为了加快搜索速度,会在图上使用另一种数据结构。 但是对于我们的例子,只需简单地搜索所有节点以找到具有匹配值的节点。 这很慢,但是可以找到。 find(value) { } 连接图内的两个节点 接下来,可以通过从一个节点到另一个节点创建一条“线”来连接两个节点。首先找到要连接的两个节点,然后从 startNode 的 lines 里添加对 endNode 的引用。 addLine(startValue, endValue) { } 最后,可以像这样使用图表: var graph = new Graph(); graph.addNode(1); graph.addNode(2); graph.addLine(1, 2); var two = graph.find(1).lines[0]; 这看起来有点简单,但它实际上是一个非常强大的结构,很多复杂程序中都用到了它。 通常会通过优化数据之间的连接而不是操作数据。一旦在图中新建了一个节点,就可以非常简单地找到图中的所有相关项。 很多事情都可以用这种方式表示,好友关系,node_modules 文件夹中的 800 个错综复杂的依赖项,另外,互联网本身就是一个通过链接连接在一起的网页图。
使用正确的数据结构可以大大简化原本复杂的逻辑。如果很注重性能或想节约内存,那么就需要选择正确的数据结构。来和我一起用 JavaScript 语言来实现一些常用数据结构吧。


运行