从现在开始将开始处理值相互引用的数据结构。
我们有一堆用线连接的 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 个错综复杂的依赖项,另外,互联网本身就是一个通过链接连接在一起的网页图。
运行