十七、图
本章包括图。图是表示对象之间联系的一种通用方式。在本章中，您将学习图基础知识，包括基本术语和图类型。本章还将介绍如何使用这些不同的图类型，以及在已经探索过的数据结构中表示图的方法。最后，探索遍历、搜索和排序图的算法，以解决诸如寻找两个图节点之间的最短路径等问题。
图基础
如简介中所述，图是对象之间联系的可视化表示。这种表示可以是许多事物，并有不同的应用；表 17-1 显示了一些例子。
表 17-1
图应用示例
|
应用
|
项目
|
关系
| | --- | --- | --- | | 网站 | 网页 | 链接 | | 地图 | 交集 | 路 | | 电路 | 成分 | 接线 | | 社会化媒体 | 人 | “友谊”/联系 | | 电话 | 电话号码 | 固定电话 |
图 17-1 显示了两个简单图的例子。
图 17-1
图的两个例子
在我们深入研究图之前，介绍一些基本的术语和概念是有用的。
图 17-5
B 上有圈的图
- 循环图:如果一个有向图有一条从顶点到自身的路径，那么这个有向图被认为是循环的。例如，在图 17-5 中，B 可以沿着边到 C，然后 D，然后 E，然后再到 B。
图 17-4
稠密图
- 稠密图:当不同顶点之间有大量连接时，一个图被认为是稠密的(见图 17-4 )。
图 17-3
稀疏图
-
顶点的度数:顶点的度数是指该顶点(节点)上的边数。
-
稀疏图:当顶点之间只存在一小部分可能的连接时，一个图被认为是稀疏的(见图 17-3 )。
图 17-2
顶点和边
-
顶点:顶点是构成图的节点。在这一章中，对于 Big-O 分析，节点将被标注为 V 。顶点用圆来表示，如图 17-2 所示。
-
边:边是图中节点之间的连接。从图上看，它是顶点之间的“线”。对于 Big-O 分析，它将被标记为 E 。用线条表示一条边，如图 17-2 所示。
相比之下，图 17-6 是非循环图的一个例子。
图 17-6
无圈图
图 17-7
带权重的有向图
- 权重:权重是边上的值。根据上下文，权重可以表示各种事物。例如，有向图上的权重可以表示从节点 A 到 B 所需的距离，如图 17-7 所示。
无向图
无向图是边之间没有方向的图。边意味着两个节点之间没有方向的相互连接。无向图关系的一个真实例子是友谊。只有双方都承认这种关系，友谊才会产生。友谊图内的边的值可以指示友谊有多近。图 17-8 是一个简单的无向图，有五个顶点和六条带权的无向边。
图 17-8
带权重的无向图
有多种方法可以将无向图示为数据结构类。两种最常见的方法是使用邻接矩阵或邻接表。邻接表使用顶点作为节点的关键字，其邻居存储在列表中，而邻接矩阵是 V 乘 V 矩阵，矩阵的每个元素指示两个顶点之间的连接。图 17-9 说明了邻接表和邻接矩阵的区别(这本书只涉及邻接表)。
图 17-9
图(左)、邻接表(中)和邻接矩阵(右)
到目前为止，已经讨论了图的概念和定义。现在，让我们实际开始在代码中实现这些想法，并学习如何添加和删除边和顶点。
添加边和顶点
在这个例子中，我们创建了一个加权的无向图并添加了顶点和边。首先，我们将为无向图创建一个新类。无向图应该有一个对象来存储边。这是如下面的代码块所示实现的:
1 function UndirectedGraph() {
2 this.edges = {};
3 }
要添加边，必须先添加顶点(节点)。该实现将采用邻接表方法，将顶点作为存储边值的this.edges对象内的对象。
1 UndirectedGraph.prototype.addVertex = function(vertex) {
2 this.edges[vertex] = {};
3 }
为了将加权边添加到无向图中，this.edges对象中的两个顶点都用于设置权重。
1 UndirectedGraph.prototype.addEdge = function(vertex1,vertex2, weight) {
2 if (weight == undefined) {
3 weight = 0;
4 }
5 this.edges[vertex1][vertex2] = weight;
6 this.edges[vertex2][vertex1] = weight;
7 }
这样，让我们用下面的代码添加一些顶点和边:
1 var graph1 = new UndirectedGraph();
2 graph1.addVertex(1);
3 graph1.addVertex(2);
4 graph1.addEdge(1,2, 1);
5 graph1.edges; // 1: {2: 0}, 2: {1: 0}
6 graph1.addVertex(3);
7 graph1.addVertex(4);
8 graph1.addVertex(5);
9 graph1.addEdge(2,3, 8);
10 graph1.addEdge(3,4, 10);
11 graph1.addEdge(4,5, 100);
12 graph1.addEdge(1,5, 88);
图 17-10 显示了该代码的图输出。
图 17-10
第一个无向图
移除边和顶点
继续同一个例子，让我们实现移除 graph 类的边和顶点的函数。
要从顶点移除边，在this.edges中查找该顶点的边对象，并使用 JavaScript 的delete操作符将其删除。
1 UndirectedGraph.prototype.removeEdge = function(vertex1, vertex2) {
2 if (this.edges[vertex1] && this.edges[vertex1][vertex2] != undefined) {
3 delete this.edges[vertex1][vertex2];
4 }
5 if (this.edges[vertex2] && this.edges[vertex2][vertex1] != undefined) {
6 delete this.edges[vertex2][vertex1];
7 }
8 }
接下来，让我们删除整个顶点。需要记住的重要一点是，任何时候一个顶点被移除，所有连接到它的边也必须被移除。这可以使用循环来完成，如以下实现所示:
1 UndirectedGraph.prototype.removeVertex = function(vertex) {
2 for (var adjacentVertex in this.edges[vertex]) {
3 this.removeEdge(adjacentVertex, vertex);
4 }
5 delete this.edges[vertex];
6 }
现在实现了删除，让我们创建另一个无向图对象，类似于第一个例子，但删除一些顶点和边。先去掉顶点 5，结果如图 17-11 所示。顶点 1 也被删除，如图 17-12 所示。最后，图 17-13 显示了移除 2 和 3 之间的边缘时的结果。
图 17-13
2 和 3 之间的边缘已移除
图 17-12
顶点 1 已移除
图 17-11
移除顶点 5
1 var graph2 = new UndirectedGraph();
2 graph2.addVertex(1);
3 graph2.addVertex(2);
4 graph2.addEdge(1,2, 1);
5 graph2.edges; // 1: {2: 0}, 2: {1: 0}
6 graph2.addVertex(3);
7 graph2.addVertex(4);
8 graph2.addVertex(5);
9 graph2.addEdge(2,3, 8);
10 graph2.addEdge(3,4, 10);
11 graph2.addEdge(4,5, 100);
12 graph2.addEdge(1,5, 88);
13 graph2.removeVertex(5);
14 graph2.removeVertex(1);
15 graph2.removeEdge(2,3);
有向图
有向图是指在顶点之间有方向的图。有向图中的每条边从一个顶点到另一个顶点，如图 17-14 所示。
图 17-14
有向图
在本例中，E 节点可以“行进”到 D 节点，而 D 节点只能行进到 C 节点。
现在让我们实现一个加权有向图类。将使用无向图实现中使用的类似邻接表方法。首先用如图所示的edges属性定义了DirectedGraph类，添加顶点的方法与从无向图类实现的方法相同。
1 function DirectedGraph() {
2 this.edges = {};
3 }
4 DirectedGraph.prototype.addVertex = function (vertex) {
5 this.edges[vertex] = {};
6 }
给定一条起始于原点并终止于目的顶点的边，要将边添加到有向图中，权重应仅设置在原点上，如下所示:
1 DirectedGraph.prototype.addEdge = function(origVertex, destVertex, weight) {
2 if (weight === undefined) {
3 weight = 0;
4 }
5 this.edges[origVertex][destVertex] = weight;
6 }
实现了添加顶点和边的函数后，让我们添加一些示例顶点和边。
1 var digraph1 = new DirectedGraph();
2 digraph1.addVertex("A");
3 digraph1.addVertex("B");
4 digraph1.addVertex("C");
5 digraph1.addEdge("A", "B", 1);
6 digraph1.addEdge("B", "C", 2);
7 digraph1.addEdge("C", "A", 3);
图 17-15 显示了添加在 A 和 B 顶点之间的边(第 5 行)。图 17-16 表示 B 和 C 之间的连接(6 号线)，图 17-17 表示 C 和 A 之间的连接(7 号线)。
图 17-17
将 C 添加到 A
图 17-16
将 B 添加到 C
图 17-15
将 A 添加到 B
有向图中删除顶点和删除边的实现与无向图中看到的实现相同，只是必须删除edges对象中的原始顶点，如下所示:
1 DirectedGraph.prototype.removeEdge = function(origVertex, destVertex) {
2 if (this.edges[origVertex] && this.edges[origVertex][destVertex] != undefined) {
3 delete this.edges[origVertex][destVertex];
4 }
5 }
6
7 DirectedGraph.prototype.removeVertex = function(vertex) {
8 for (var adjacentVertex in this.edges[vertex]) {
9 this.removeEdge(adjacentVertex, vertex);
10 }
11 delete this.edges[vertex];
12 }
图遍历
一个图可以用多种方式遍历。两种最常见的方法是广度优先搜索和深度优先搜索。类似于如何探索不同的树遍历技术，这一节将集中讨论这两种遍历技术以及何时使用它们中的每一种。
广度优先搜索
广度优先搜索 (BFS)指的是一种在图中的搜索算法，按顺序聚焦于连通节点及其连通节点。这个想法实际上已经在第 15 章中用层次顺序遍历的树进行了探索。图 17-18 显示了二叉查找树的层次顺序遍历。
图 17-18
二叉查找树的层次顺序遍历
请注意，遍历的顺序是根据从根节点算起的高度来确定的。注意与图 17-19 中的图相似。
图 17-19
广度优先搜索图
类似于树形数据结构的层次顺序遍历，BFS 需要一个队列。
对于每个节点，将每个连接的顶点添加到队列中，然后访问队列中的每个项目。让我们为图类编写一个通用的 BFS 算法。
1 DirectedGraph.prototype.traverseBFS = function(vertex, fn) {
2 var queue = [],
3 visited = {};
4
5 queue.push(vertex);
6
7 while (queue.length) {
8 vertex = queue.shift();
9 if (!visited[vertex]) {
10 visited[vertex] = true;
11 fn(vertex);
12 for (var adjacentVertex in this.edges[vertex]) {
13 queue.push(adjacentVertex);
14 }
15 }
16 }
17 }
18 digraph1.traverseBFS("B", (vertex)=>{console.log(vertex)});
时间复杂度: O( V + E
时间复杂度为 O( V + E ，其中 V 为顶点数， E 为边数。这是因为该算法必须遍历整个图的每个边和节点。
回忆一下本章前面使用的“无向图”中图 17-20 的图结构。
图 17-20
之前的无向图示例
将 BFS 应用于图，会打印出以下内容:1，2，5，3，4。
在图 17-21 和 17-22 中，浅阴影节点表示当前正在访问的节点，而深色节点表示该节点已经被访问过。
图 17-21
广度优先搜索，第 1 部分
在图 17-21 中，广度优先搜索从 1 节点开始。因为它有两个邻居 2 和 5，所以它们被添加到队列中。然后，2 被访问，它的邻居 3 被添加到队列中。5 然后出列，并且它的邻居 4 被添加到队列中。最后访问 3 和 4，搜索结束，如图 17-22 所示。
图 17-22
广度优先搜索，第 2 部分
深度优先搜索
深度优先搜索 (DFS)指的是图中的一种搜索算法，它专注于在访问其他连接之前深入遍历一个连接。
这个想法已经在第 15 章中用树中的顺序、后顺序和前顺序遍历进行了探讨。例如，后序树遍历在访问顶部根节点之前访问底部子节点(见图 17-23 )。
图 17-23
后序遍历
类似的情况如图 17-24 所示。
图 17-24
深度优先搜索图
注意最后 E 是如何被访问的。这是因为搜索在访问 e 之前访问了在深度中连接到 C 的所有节点。
类似于树数据结构的前置后置和有序遍历，递归被用于深入到节点中，直到该路径被用尽。
让我们为 graph 类编写一个通用的 DFS 算法。
1 DirectedGraph.prototype.traverseDFS = function(vertex, fn) {
2 var visited = {};
3 this._traverseDFS(vertex, visited, fn);
4 }
5
6 DirectedGraph.prototype._traverseDFS = function(vertex, visited, fn) {
7 visited[vertex] = true;
8 fn(vertex);
9 for (var adjacentVertex in this.edges[vertex]) {
10 if (!visited[adjacentVertex]) {
11 this._traverseDFS(adjacentVertex, visited, fn);
12 }
13 }
14 }
时间复杂度: O( V + E
时间复杂度为 O( V + E )，其中 V 为顶点数， E 为边数。这是因为该算法必须遍历整个图的每个边和节点。这与 BFS 算法的时间复杂度相同。
同样，让我们使用本章前面的图结构(见图 17-25 )。
图 17-25
图 17-20 中的早期图示例
将 DFS 应用于图，将打印出以下内容:1，2，3，4，5。
在图 17-26 和 17-27 中，浅阴影节点表示当前正在访问的节点，而深色节点表示该节点已经被访问过。
图 17-26
深度优先搜索，第 1 部分
在图 17-26 中，深度优先搜索从 1 节点开始。它的第一个邻居 2 被访问。然后，2 的第一个邻居 3 被访问。在访问 3 之后，下一个将访问 4，因为它是 3 的第一个邻居。最后，4 被访问，然后是 5，如图 17-27 所示。深度优先搜索总是递归地访问第一个邻居。
图 17-27
深度优先搜索，第 2 部分
加权图和最短路径
既然我们已经介绍了图的基本知识以及如何遍历它们，我们可以讨论加权边和 Dijkstra 算法，它使用最短路径搜索。
带权边的图
回想一下，图中的边表示顶点之间的连接。如果边建立了连接，则权重可以被分配给该连接。例如，对于表示地图的图，边上的权重是距离。
重要的是要注意，一条边的图长度对于该边的重量没有任何意义。它纯粹是为了视觉目的。在实现和代码中，不需要可视化表示。在图 17-28 中，权重告诉我们五个城市的图表示中城市之间的距离。例如，从图上看，从城市 1 到城市 2 的距离比从城市 2 到城市 3 的距离短。然而，边缘表明从城市 1 到城市 2 的距离是 50 公里，从城市 2 到城市 3 的距离是 10 公里，这是 5 倍大。
图 17-28
五个城市的图表示
加权边图最重要的问题是，从一个节点到另一个节点的最短路径是什么？图的最短路径算法有一系列。我们讨论的是 Dijkstra 算法。
Dijkstra 算法:最短路径
Dijkstra 算法的工作原理是在每一层选择最短的路径到达目的地。起初，距离被标记为无穷大，因为一些节点可能无法到达(见图 17-29 )。然后在每次遍历迭代中，为每个节点选择最短的距离(见图 17-30 和 17-31 )。
图 17-31
Dijkstra 阶段 3:现在已处理所有节点
图 17-30
Dijkstra 阶段 2: B 和 C 已处理
图 17-29
Dijkstra 阶段 1:所有标记为无穷大的东西
_extractMin用于计算给定顶点的距离最小的相邻节点。当从起点到目的地节点遍历图时，使用广度优先搜索大纲将每个顶点的相邻节点排队，更新并计算距离。
1 function _isEmpty(obj) {
2 return Object.keys(obj).length === 0;
3 }
4
5 function _extractMin(Q, dist) {
6 var minimumDistance = Infinity,
7 nodeWithMinimumDistance = null;
8 for (var node in Q) {
9 if (dist[node] <= minimumDistance) {
10 minimumDistance = dist[node];
11 nodeWithMinimumDistance = node;
12 }
13 }
14 return nodeWithMinimumDistance;
15 }
16
17 DirectedGraph.prototype.Dijkstra = function(source) {
18 // create vertex set Q
19 var Q = {}, dist = {};
20 for (var vertex in this.edges) {
21 // unknown distances set to Infinity
22 dist[vertex] = Infinity;
23 // add v to Q
24 Q[vertex] = this.edges[vertex];
25 }
26 // Distance from source to source init to 0
27 dist[source] = 0;
28
29 while (!_isEmpty(Q)) {
30 var u = _extractMin(Q, dist); // get the min distance
31
32 // remove u from Q
33 delete Q[u];
34
35 // for each neighbor, v, of u:
36 // where v is still in Q.
37 for (var neighbor in this.edges[u]) {
38 // current distance
39 var alt = dist[u] + this.edges[u][neighbor];
40 // a shorter path has been found
41 if (alt < dist[neighbor]) {
42 dist[neighbor] = alt;
43 }
44 }
45 }
46 return dist;
47 }
48
49 var digraph1 = new DirectedGraph();
50 digraph1.addVertex("A");
51 digraph1.addVertex("B");
52 digraph1.addVertex("C");
53 digraph1.addVertex("D");
54 digraph1.addEdge("A", "B", 1);
55 digraph1.addEdge("B", "C", 1);
56 digraph1.addEdge("C", "A", 1);
57 digraph1.addEdge("A", "D", 1);
58 console.log(digraph1);
59 // DirectedGraph {
60 // V: 4,
61 // E: 4,
62 // edges: { A: { B: 1, D: 1 }, B: { C: 1 }, C: { A: 1 }, D: {} }}
63 digraph1.Dijkstra("A"); // { A: 0, B: 1, C: 2, D: 1 }
时间复杂度:O(VT4】2+E)
这里的算法类似于 BFS 算法，但是需要使用时间复杂度为 O( n )的_extractMin方法。正因为如此，时间复杂度为 O(VT8】2+E)，因为在_extractMin方法中必须检查当前被遍历节点的所有邻居顶点。可以使用提取 min 的优先级队列来改进该算法，这将产生 O(log2(V)_extractMin，并且因此产生 O(E+V) O(log2(V*))= O(【T30)这甚至可以通过使用 Fibonacci 堆来优化，Fibonacci 堆有固定的时间来计算_extractMin。然而，为了简单起见，在这个演示中既没有使用 Fibonacci 堆，也没有使用优先级队列。
拓扑排序
对于有向图，对于各种应用程序，知道应该首先处理哪个节点是很重要的。这方面的一个例子是任务调度器，其中一个任务依赖于前一个正在完成的任务。另一个例子是 JavaScript 库依赖管理器，它必须确定在其他库之前导入哪些库。拓扑排序算法实现了这一点。它是一种改进的 DFS，使用栈来记录顺序。
简而言之，它的工作方式是从一个节点执行 DFS，直到其连接的节点被递归耗尽，并将其添加到栈，直到所有连接的节点都被访问(见图 17-32 )。
图 17-32
拓扑排序
拓扑排序有一个被访问的集合，以确保递归调用不会导致无限循环。对于给定的节点，该节点被添加到已访问过的集合中，并且在下一次递归调用中访问其未被访问过的邻居。递归调用结束时，使用 unshift 将当前节点的值添加到栈中。这确保了顺序是按时间顺序的。
1 DirectedGraph.prototype.topologicalSortUtil = function(v, visited, stack) {
2 visited.add(v);
3
4 for (var item in this.edges[v]) {
5 if (visited.has(item) == false) {
6 this.topologicalSortUtil(item, visited, stack)
7 }
8 }
9 stack.unshift(v);
10 };
11
12 DirectedGraph.prototype.topologicalSort = function() {
13 var visited = {},
14 stack = [];
15
16
17 for (var item in this.edges) {
18 if (visited.has(item) == false) {
19 this.topologicalSortUtil(item, visited, stack);
20 }
21 }
22 return stack;
23 };
24
25 var g = new DirectedGraph()
;
26 g.addVertex('A');
27 g.addVertex('B');
28 g.addVertex('C');
29 g.addVertex('D');
30 g.addVertex('E');
31 g.addVertex('F');
32
33 g.addEdge('B', 'A');
34 g.addEdge('D', 'C');
35 g.addEdge('D', 'B');
36 g.addEdge('B', 'A');
37 g.addEdge('A', 'F');
38 g.addEdge('E', 'C');
39 var topologicalOrder = g.topologicalSort();
40 console.log(g);
41 // DirectedGraph {
42 // V: 6,
43 // E: 6,
44 // edges:
45 // { A: { F: 0 },
46 // B: { A: 0 },
47 // C: {},
48 // D: { C: 0, B: 0 },
49 // E: { C: 0 },
50 // F: {} } }
51 console.log(topologicalOrder); // [ 'E', 'D', 'C', 'B', 'A', 'F' ]
时间复杂度: O( V + E
空间复杂度: O( V
拓扑排序算法就是带有额外栈的 DFS。因此，时间复杂度与 DFS 相同。拓扑排序在空间上需要 O( V )，因为它需要存储栈中的所有顶点。这种算法对于根据给定的依赖关系调度作业是非常有效的。
摘要
本章讨论了不同类型的图、它们的属性以及如何对它们进行搜索和排序。由顶点组成并通过边连接的图可以用许多不同的方式表示为数据结构。在这一章中，邻接表被用来表示图。如果图是密集的，最好使用基于矩阵的图表示。在图的边中，权重表示相连顶点的重要性(或不重要)。此外，通过给边分配权重，实现了 Dijkstra 的最短路径算法。最后，图是具有各种用例和有趣算法的通用数据结构。
表 17-2 显示了图的一些关键属性。
表 17-2
图属性摘要
|
财产
|
描述
| | --- | --- | | 稠密的 | 不同顶点之间有很多联系。 | | 稀少的 | 顶点之间只存在一小部分可能的连接。 | | 周期的 | 有一条路径将顶点带回到它们自己。 | | 传阅的 | 没有路径可以让顶点回到它们自己。 | | 定向的 | 图在边之间有一个方向。 | | 未受指导的 | 图在边之间没有方向。 |
表 17-3 总结了图算法。
表 17-3
图算法概述
|
算法
|
描述/使用案例
|
时间复杂度
| | --- | --- | --- | | 宽度优先搜索 | 通过一次访问一级邻居节点来遍历图 | O( V + E ) | | 深度优先搜索 | 通过一次深入一个邻居节点来遍历图 | O( V + E ) | | 最短路径 | 查找从一个顶点到其他顶点的最短路径 | o(VT3】2T5+E | | 拓扑排序 | 对有向图进行排序；对于作业调度算法 | O( V + E ) |
版权属于：月萌API www.moonapi.com，转载请注明出处
