本文将探讨非线性数据结构，例如图。此外，我们还将介绍其核心概念和典型应用。
你可能经常使用涉及图和树的程序。例如，假设你想知道从工作地点到家的最短路径；你可以使用图算法来找到答案！我们将探讨这个问题以及其他有趣的挑战。
在上一篇文章中，我们探讨了数组、链表、集合、栈等线性数据结构。本文将在此基础上继续深入探讨。
您可以在Github代码库中找到所有这些实现以及更多内容：
amejiarosario / dsa.js-数据结构-算法-javascript
这是DSA.js 书籍的代码实现以及 NPM 包的仓库。
在这个代码库中，你可以找到 JavaScript 中算法和数据结构的实现。这些资料可以作为开发者的参考手册，也可以帮助你在面试前复习特定主题。此外，你还可以从中获得更高效的问题解决方法。
您可以克隆此仓库或从 NPM 安装代码：
npm install dsa.js
然后您可以将其导入到您的程序或命令行界面中。
const { LinkedList, Queue, Stack } = require('dsa.js');
有关所有可用数据结构和算法的列表，请参阅 index.js。
算法至关重要……
以下是本文将要介绍的操作概要：
| 邻接表 | 邻接矩阵 | |
|---|---|---|
| 添加顶点 | O(1) | O(|V| 2 ) |
| 移除顶点 | O(|V| + |E|) | O(|V| 2 ) |
| addEdge | O(1) | O(1) |
| 移除边缘（使用数组） | O(|E|) | O(1) |
| 移除边缘（使用 HashSet） | O(1) | O(1) |
| 获取相邻项 | O(|E|) | O(|V|) |
| isAdjacent（使用数组） | O(|E|) | O(1) |
| isAdjacent（使用 HashSet） | O(1) | O(1) |
| 空间复杂性 | O(|V| + |E|) | O(|V| 2 ) |
在深入探讨有趣的图算法之前，让我们先来明确一下命名约定和图的属性。
图是一种数据结构，其中一个节点可以有零个或多个相邻元素。
两个节点之间的连接称为边。节点也可以称为顶点。
度数是指与一个顶点相连的边的数量。例如，purple顶点 1 的度数为 3，而blue顶点 2 的度数为 1。
如果边是双向的，那么我们就得到了一个无向图。但是，如果边是有方向的，那么我们就得到了一个有向图（简称有向图）。你可以把它想象成一条单行道（有向图）或一条双向道（无向图）。
顶点可以有指向自身的边（例如，blue节点），这称为自环。
图可以包含环，这意味着如果遍历某个节点，可能会多次到达同一个节点。不含环的图称为无环图。
此外，无环无向图也称为树。我们将在下一篇文章中深入探讨树。
图中并非所有顶点都必须连通。可能存在孤立节点，甚至分离的子图。如果所有节点都至少有一条边，则该图为连通图。当所有节点都与其他所有节点连通时，则该图为完全图。
对于完全图，每个节点都应该有#nodes - 1边。在前面的例子中，我们有七个顶点，所以每个节点有六条边。
当图中的边被赋予权重/成本时，我们就称其为加权图。如果图中没有权重，我们可以假设其值为 1。
加权图有很多应用，具体取决于你需要解决问题的领域。例如：
航空交通（上图）
GPS导航
网络路由
一般来说，图表在现实世界中有很多应用，例如：
我们刚刚学习了图的基础知识及其一些应用。接下来，我们将探讨如何在 JavaScript 中表示图。
图的表示方法主要有两种：
让我们以下面的有向图为例来解释一下：
我们有一个有4个节点的有向图。当一个顶点有一条指向自身的链接时（例如a），称为自环。
邻接矩阵是使用二维数组（N×N 矩阵）表示图的一种方法。在节点的交集中，如果节点相连，则加 1（或其他权重）；如果不相连0，则不加 0。-
沿用之前的例子，我们可以构建如下邻接矩阵：
a b c d e
a 1 1 - - -
b - - 1 - -
c - - - 1 -
d - 1 1 - -
如您所见，该矩阵按水平和垂直方向列出了所有节点。如果连接较少，我们称之为稀疏图；如果连接较多（接近最大连接数），我们称之为稠密图。如果所有可能的连接都已达到，则我们得到的是完全图。
需要注意的是，对于无向图，邻接矩阵总是关于对角线对称的。然而，对于有向图（例如我们的例子），情况并非如此。
找出两个顶点之间的连接的时间复杂度是多少？
查询邻接矩阵中的两个节点是否相连需要常数时间或O(1)。
空间复杂度是多少？
将图存储为邻接矩阵的空间复杂度为O(n² )，其中 n
n是顶点数。也可以表示为O(|V| ² )。
添加一个顶点需要多长时间？
顶点以V*xV * 矩阵的形式存储。因此，每次添加顶点时，都需要将矩阵重构为V+1*xV+1 * 矩阵。
在邻接矩阵上添加一个顶点的复杂度为O(|V| 2 )
如何获取相邻节点？
由于该矩阵是一个 VxV 矩阵，要获取给定顶点的所有相邻节点，我们需要遍历该节点所在的行，并获取该节点与其他节点的所有边。
在之前的例子中，假设我们想要找到所有与节点 b 相邻的节点b。我们需要找到包含 b 以及所有其他节点的完整行。
a b c d e
b - - 1 - -
我们需要访问所有节点，所以
在邻接矩阵上获取相邻节点的时间复杂度为O(|V|)
想象一下，你需要用图来表示 Facebook 社交网络。你将不得不创建一个 20 亿 x 20 亿的矩阵，其中大部分都是空的！没有人会认识其他人，最多只有几千人彼此认识。
通常情况下，我们处理的是稀疏图，因此矩阵会浪费大量空间。这就是为什么在大多数实现中，我们会使用邻接表而不是矩阵的原因。
邻接表是表示图的最常用方法之一。每个节点都有一个与其相连的所有节点的列表。
图可以用邻接表表示，邻接表使用包含节点的数组（或哈希表）。每个节点条目都包含一个列表（数组、链表、集合等），其中列出了与其相邻的节点。
例如，在上图中，我们有a与 相连b，并且自身也形成一个自环。反过来，b又与 相连，c依此类推：
a -> { a b }
b -> { c }
c -> { d }
d -> { b c }
您可以想象，如果您想知道一个节点是否与另一个节点相连，您需要遍历该列表。
查询邻接表中两个节点是否相连的时间复杂度为O(n)，其中
nn 为顶点数。也可表示为O(|V|)。
空间复杂性又如何呢？
将图存储为邻接表的空间复杂度为O(n)，其中
nn 是顶点数和边数之和。也可以表示为O(|V| + |E|)。
邻接表是表示图的最常用方法。邻接表有多种实现方式：
其中一种方法是使用 HashMap。其中，`value`key是节点的值，`a`value是邻接关系数组。
const graph = {
a: ['a', 'b'],
b: ['c'],
c: ['d'],
d: ['b', 'c']
}
图通常需要以下操作：
添加和删除顶点涉及更新邻接表。
假设我们要删除顶点b。我们可以这样做delete graph['b'];，但是我们仍然需要删除邻接表中“d”和“a”的引用。
每次移除一个节点，我们都需要遍历所有节点的列表，时间复杂度为O(|V| + |E|)。我们能做得更好吗？我们很快就会解答这个问题，但首先，让我们用更面向对象的方式实现我们的列表，这样我们就可以轻松地切换实现方式。
我们先从Node保存顶点值及其相邻顶点的类开始。我们还可以添加辅助函数，用于在列表中添加和删除附近的节点。
class Node {
constructor(value) {
this.value = value;
this.adjacents = []; // adjacency list
}
addAdjacent(node) {
this.adjacents.push(node);
}
removeAdjacent(node) {
const index = this.adjacents.indexOf(node);
if(index > -1) {
this.adjacents.splice(index, 1);
return node;
}
}
getAdjacents() {
return this.adjacents;
}
isAdjacent(node) {
return this.adjacents.indexOf(node) > -1;
}
}
注意，adjacent运行时间是O(1)，而remove adjacentO (|E|)。如果我们用一个 🧐 代替数组呢HashSet？它的时间复杂度可能也是O(1)。但是，我们先让它能运行起来，之后再考虑如何提高速度。
让它运转起来。让它正确无误。让它更快。
好了，现在我们有了这个Node类，让我们来构建 Graph 类，它可以执行诸如添加/删除顶点和边之类的操作。
图形构造器
class Graph {
constructor(edgeDirection = Graph.DIRECTED) {
this.nodes = new Map();
this.edgeDirection = edgeDirection;
}
// ...
}
Graph.UNDIRECTED = Symbol('directed graph'); // one-way edges
Graph.DIRECTED = Symbol('undirected graph'); // two-ways edges
我们首先需要知道的是图是有向图还是无向图。这在添加边时会产生影响。
Graph.addEdge
要添加一条边，我们需要两个节点。一个是源节点，另一个是目标节点。
addEdge(source, destination) {
const sourceNode = this.addVertex(source);
const destinationNode = this.addVertex(destination);
sourceNode.addAdjacent(destinationNode);
if(this.edgeDirection === Graph.UNDIRECTED) {
destinationNode.addAdjacent(sourceNode);
}
return [sourceNode, destinationNode];
}
js
我们添加一条从源顶点到目标顶点的边。如果是无向图，由于它是双向的，我们还需要添加一条从目标节点到源节点的边。
从图的邻接表中添加一条边的运行时间为：O(1)
如果我们尝试添加一条边，但节点不存在，我们需要先创建它们。接下来我们就来创建它们！
Graph.addVertex
创建节点的方式是将其添加到this.nodesMap 中。Map 存储一个键值对，其中键key是顶点的值，而 Mapvalue本身是节点类的实例。请查看第 5-6 行：
addVertex(value) {
if(this.nodes.has(value)) {
return this.nodes.get(value);
} else {
const vertex = new Node(value);
this.nodes.set(value, vertex);
return vertex;
}
}
如果节点已存在，我们不希望覆盖它。因此，我们首先检查它是否已存在，如果不存在，则创建它。
从图的邻接表中添加顶点的运行时间为：O(1)
Graph.removeVertex
从图中移除一个节点稍微复杂一些。我们需要检查要删除的节点是否正在被用作相邻节点。
removeVertex(value) {
const current = this.nodes.get(value);
if(current) {
for (const node of this.nodes.values()) {
node.removeAdjacent(current);
}
}
return this.nodes.delete(value);
}
我们需要遍历每个顶点，然后遍历每个相邻节点（边）。
从图的邻接表中移除一个顶点的运行时间为O(|V| + |E|)。
最后，让我们移除移除边缘的实现！
Graph.removeEdge
去除边缘非常简单，类似于addEdge……
removeEdge(source, destination) {
const sourceNode = this.nodes.get(source);
const destinationNode = this.nodes.get(destination);
if(sourceNode && destinationNode) {
sourceNode.removeAdjacent(destinationNode);
if(this.edgeDirection === Graph.UNDIRECTED) {
destinationNode.removeAdjacent(sourceNode);
}
}
return [sourceNode, destinationNode];
}
addEdge两者之间的主要区别removeEdge在于：
Node.removeAdjacent代替Node.addAdjacent。由于removeAdjacent需要遍历所有相邻顶点，因此运行时间如下：
从图的邻接表中移除一条边的运行时间为O(|E|)。
我们将探讨如何从节点中搜索值。
广度优先搜索是一种从初始顶点开始，首先访问所有相邻节点，从而遍历图的方法。
让我们看看如何用代码实现这一点：
*bfs(first) {
const visited = new Map();
const visitList = new Queue();
visitList.add(first);
while(!visitList.isEmpty()) {
const node = visitList.remove();
if(node && !visited.has(node)) {
yield node;
visited.set(node);
node.getAdjacents().forEach(adj => visitList.add(adj));
}
}
}
如您所见，我们使用了一种Queue先进先出 (FIFO) 算法，其中第一个节点也是第一个被访问的节点。
我们还使用了JavaScript 生成器，请注意*函数前面的 `$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$('$(1$( '$(1$( '$( '$( '$( '$( '$( '$( '$( '$( ')')))))))))))))。'$( '$( ... '')))))))
以下是如何使用我们刚刚创建的广度优先搜索算法的示例：
const graph = new Graph(Graph.UNDIRECTED);
const [first] = graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(5, 2);
graph.addEdge(6, 3);
graph.addEdge(7, 3);
graph.addEdge(8, 4);
graph.addEdge(9, 5);
graph.addEdge(10, 6);
bfsFromFirst = graph.bfs(first);
bfsFromFirst.next().value.value; // 1
bfsFromFirst.next().value.value; // 2
bfsFromFirst.next().value.value; // 3
bfsFromFirst.next().value.value; // 4
// ...
您可以在测试用例中找到更多用法示例。接下来我们来看深度优先搜索！
深度优先搜索是另一种从初始顶点开始遍历图的方法，它递归地找到每个顶点的第一个相邻节点。
深度优先搜索（DFS）的迭代实现与广度优先搜索（BFS）相同，只是DFS使用迭代器而不是Queue迭代器Stack：
*dfs(first) {
const visited = new Map();
const visitList = new Stack();
visitList.add(first);
while(!visitList.isEmpty()) {
const node = visitList.remove();
if(node && !visited.has(node)) {
yield node;
visited.set(node);
node.getAdjacents().forEach(adj => visitList.add(adj));
}
}
}
我们可以按如下方式测试我们的图表。
const graph = new Graph(Graph.UNDIRECTED);
const [first] = graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(5, 2);
graph.addEdge(6, 3);
graph.addEdge(7, 3);
graph.addEdge(8, 4);
graph.addEdge(9, 5);
graph.addEdge(10, 6);
dfsFromFirst = graph.dfs(first);
visitedOrder = Array.from(dfsFromFirst);
const values = visitedOrder.map(node => node.value);
console.log(values); // [1, 4, 8, 3, 7, 6, 10, 2, 5, 9]
如您所见，BFS 和 DFS 的图基本相同，但访问节点的顺序却截然不同。BFS 按顺序从 1 到 10 访问节点，而 DFS 则尽可能深入地访问每个节点。
我们已经了解了图的一些基本操作，例如如何添加和删除顶点和边。以下是我们目前所学内容的总结：
| 邻接表 | 邻接矩阵 | |
|---|---|---|
| 空间 | O(|V| + |E|) | O(|V| 2 ) |
| 添加顶点 | O(1) | O(|V| 2 ) |
| 移除顶点 | O(|V| + |E|) | O(|V| 2 ) |
| addEdge | O(1) | O(1) |
| 移除边缘（使用数组） | O(|E|) | O(1) |
| 移除边缘（使用 HashSet） | O(1) | O(1) |
| 获取相邻项 | O(|E|) | O(|V|) |
| isAdjacent（使用数组） | O(|E|) | O(1) |
| isAdjacent（使用 HashSet） | O(1) | O(1) |
如您所见，邻接表在几乎所有操作中都更快。邻接矩阵唯一优于邻接表的操作是检查节点是否与其他节点相邻。但是，如果我们把实现方式从数组改为哈希集合，也能达到常数时间复杂度 :)
正如我们所见，图可以帮助我们模拟许多现实生活中的场景，例如机场、社交网络、互联网等等。我们介绍了一些最基本的算法，例如广度优先搜索（BFS）和深度优先搜索（DFS）。此外，我们还研究了实现方式的权衡，例如邻接表和邻接矩阵。订阅我的简讯，不要错过我的任何文章，因为我们很快将学习许多其他应用，例如寻找节点之间的最短路径以及其他令人兴奋的图算法！
文章来源：https://dev.to/amejiarosario/graph-data-structs-for-beginners-5edn