第6章 图

6.1 图结构基础与特性

6.1.1 图的定义与特点

图结构在面试中的出现频率相对其他数据结构而言较低，但也是一种常见的数据结构，我们通过本章的学习来认识一下关于图的一些内容以及一些算法。图结构如果单独拿出来探讨，可以有非常多的内容，多到大于之前所学的所有数据结构的总和。因为图结构可以延伸到图论上，图论是一门通过“图”来研究事物之间关系及其规律的数学学科，它是计算机图结构和各种图算法的理论基础。

所以在本章节只会了解学习图结构的一些常见的内容。那什么是图？图结构可以认为是一种与树结构有些相似的数据结构，而在数学的概念上，树是图的一种（可见图的概念非常广泛）。由于图是图论的一部分，而图论又是数学的一个分支，因此想学好图结构是绕不开数学的，图论通过图来研究顶点和边组成的图形的数学理论和方法，主要研究的目的是事物之间的关系，顶点代表事物，边代表两个事物间的关系。

6.1.2 图的现实应用案例

我们在第5章知道了树结构可以用来模拟很多现实的数据结构，例如：家谱/公司组织架构等等，那么图长什么样子？或者什么样的数据使用图来模拟更合适呢？

人与人之间的关系网就是一种图结构，甚至科学家们在观察人与人之间的关系网时，还发现了六度空间理论。六度空间理论认为世界上任何两个互相不认识的两人，只需要很少的中间人就可以建立起联系，并非一定要经过6步，只是需要很少的步骤。这让我想起一段话，这个世界有多大，取决于我们认识多少人，每认识一个人，世界对我们来说就会变大一点，由朋友相互介绍的交朋友方式，难度是肯定比直接去认识完全陌生的人方便的，只要我们认真的去提升自己。通过这个六度空间理论，我们与整个世界的实际距离也只需要很少的步骤，世界随时向我们敞开怀抱啊！

整个世界那么广阔，那么多的人，仅仅需要那么几步就能联系在一起，这侧面印证的图结构的错综复杂。

图6-1 六度空间理论

图结构也有与生活息息相关的例子，例如北京地铁图，如图6-2所示。在北京地铁图中，每一个地铁站都可以视为一个顶点（节点），而连接两个站点的地铁线路就是边（Edge）。图结构恰好就是由“点”和“边”组成的，因此地铁图完全符合图的定义。我们现实生活中每天为了上下班、通勤、换乘，就是在不知不觉间遍历一张图。

当我们规划从国贸到中关村的路线时，实际做的就是：在图中找到两个节点间的路径，在所有路径中选一个“代价最小”的（最少换乘、最短时间、最少站数等），这对应的正是图论里的最短路径问题。不管你用的是地图 App、百度地图还是地铁 APP，它们后台都在基于Dijkstra或BFS类算法给出最佳路线。

图6-2 北京地铁图

除此之外还有村庄之间的关系网等等更多案例。

那么，什么是图呢？在前面的案例中，节点（其实图中叫顶点Vertex，一般不叫节点）之间的关系，是不能使用树来表示，使用任何的树结构都无法模拟。这个时候，我们就可以使用图来模拟它们。

图通常有一组顶点和一组边，通常用V（Vertex）表示顶点的集合，用E（Edge）表示边的集合。边是顶点和顶点之间的连线，边可以是有向的，也可以是无向的。例如A --- B，通常表示无向。 而A --> B，通常表示有向。

6.1.3 欧拉与七桥问题

18 世纪的东普鲁士城市——哥尼斯堡，有一条普雷格尔河流经市区，并将城市分成两个河岸与两个岛屿。为了方便人们往来，这里修建了 七座桥 将这些地区连接起来。当时当地居民常常在散步时讨论一个有趣的问题：能不能设计一条路线，使得一个人不重复、不遗漏地走完七座桥，最终回到起点？这个看似简单的生活娱乐问题，却一直没有人能找到完美的走法，成了当时城市里最有名的“数学谜题”。哥伦斯堡的七桥如图6-3所示。

图6-3 哥尼斯堡的七座桥

1735年，有几名大学生对这个问题产生了浓厚兴趣，但始终找不到答案，于是写信请教正在俄罗斯彼得堡科学院任职的年轻天才——莱昂哈德·欧拉（Euler）。欧拉接到请求后非常认真，他亲自研究了城市的布局与桥的连接方式，尝试了许多可能的路线。然而，无论他如何尝试，都无法找到满足条件的路径。这让欧拉意识到：这个问题可能不是“走法没找到”，而是从根本上无解。

但欧拉并没有停留在尝试走路的层面，而是做了一个革命性的抽象：

• 他把岛屿与河岸视为点（顶点）。
• 把桥视为连接这些点的线（边）。

这样一来，复杂的地理图就变成了一个由点与线组成的抽象结构。欧拉进一步发现：想不重复地走完每一条边并回到起点，就是现在所说的 欧拉回路（Eulerian circuit） 问题。他证明了：若一个图的所有点的度数都为偶数，则存在欧拉回路；若有超过两个点的度数为奇数，则一定不存在，而如图6-4所示的哥尼斯堡七桥问题的所有关键节点都是奇度，因此这个问题从一开始就无解。

图6-4 哥尼斯堡的七座桥（抽象）

在一笔画问题中，每个点的“度”（即连接的边数）决定了它在路径中的角色。路径在经过某个点时，进入一次就必须从另一条边离开一次，因此作为中途经过的点，边数必须成对出现，也就是“偶点”，才能保证“有来有去、进出配平”。但如果一个点的度数是奇数，就说明多出的一条边无法与其他边配对，这样的点只能作为路径的起点或终点来消化这条“多余的路”。因此，一张图想要被一笔画成，必须使奇点的数量不是零就是二：零个奇点表示既能一笔画完又能回到起点，而恰好两个奇点表示能一笔画完但起点和终点不同；若奇点超过两个，则不可能一笔画成。

1736 年，29 岁的欧拉向彼得堡科学院递交了著名论文《哥尼斯堡的七座桥》。这篇论文解决了这个长期困扰人们的问题，更重要的是：欧拉首次引入了图（Graph）的概念，将研究中心转移到“关系结构”而非几何形状，正式开创了现代图论（Graph Theory）与拓扑学（Topology）的两个重要分支。从此，数学史上开启了一段研究“点—线结构”的新旅程，而图论也成为现代计算机、网络、交通、社交媒体等无数领域的核心理论基础。

在 18 世纪，欧拉研究哥尼斯堡七桥问题时，提出了用“点与线”来抽象现实世界的结构。当时并没有“图结构”这个说法，更没有数据结构概念，欧拉的所有研究都是纯数学层面的理论抽象。因此历史上图论（1736 年）远早于计算机中的图结构，直到 20 世纪计算机科学兴起，人们才开始用邻接表、邻接矩阵等方式在内存中存储图，这些方法才被称为 图结构（Graph Data Structure）。

从历史上讲，是图论先出现；从计算机科学角度讲，图结构是为了实现图论而被发明的。coderwhy老师认为欧拉在思考这个问题的时候，并不是针对某一个特性的问题去考虑，而是将岛和桥抽象成了点和线，抽象是数学的本质，而编程我们也一再强调抽象的重要性。汇编语言是对机器语言的抽象，高级语言是对汇编语言的抽象。操作系统是对硬件的抽象，应用程序在操作系统的基础上构建。

6.2 图的常见术语

我们在学习树的时候，树有很多的相关术语。了解这些术语有助于我们更好的理解图结构以及更好的表达清楚。对图结构的学习也可以先了解一些图相关的术语，从而方便后续的学习，但是图的术语其实非常多，如果我们找一本专门讲图的各个方面的书籍，会发现只是术语就可以占据满满的一个章节。这里，我们先介绍几个比较常见的术语，某些术语后面用到的时候，再了解。没有用到的，在自行深入学习的过程中，可以通过查资料去了解。

我们先来看一个抽象出来的村庄图关系网，如图6-5所示。使用数字标记出每一个村庄，这更容易我们从整体来观察整个图结构。

图6-5 村庄关系网（抽象）

6.2.1 顶点、边与相邻顶点

• 顶点：刚才我们已经介绍过了，表示图中的一个节点，例如地铁站中某个站/多个村庄中的某个村庄/互联网中的某台主机/人际关系中的人。

• 边：刚才我们也介绍过了，表示顶点和顶点之间的连线，例如地铁站中两个站点之间的直接连线，就是一个边。需要注意：这里的边不要叫做路径，路径有其他的概念，待会儿我们会介绍到。图6-5中： 0-1有一条边，1-2有一条边，0-2没有边。

• 相邻顶点：而由一条边连接在一起的顶点称为相邻顶点。例如0-1是相邻的，0-3是相邻的。 0-2是不相邻的。

边不仅表达“连接”，每一条边都代表了一种直接关系，因此如果我们把所有边都看作一个整体，就能看到图中究竟哪些区域关系密集、哪些区域关系稀疏。边的分布会影响结构的连通性，例如如果某个重要顶点连接着多条边，一旦它失效，图结构可能会分裂成多个部分。因此，从边的角度也能反推出：哪些顶点对保持图的整体连通最关键。虽然这些概念最终会通向连通性、路径和网络结构分析，但它们本质上都起源于“边如何分布、边如何连接顶点”。

当两个顶点相邻时，意味着在图中它们之间有最直接的交互或关联，因此相邻关系形成了图结构中的“局部结构”。理解局部结构为什么重要？因为图的整体性质往往是由许多局部关系堆叠而成的。例如，如果一个顶点周围的相邻顶点非常集中且互相也密集连接，那么它所在区域就呈现出高度聚合；相反，如果一个顶点只有寥寥几条边相邻，它在图的整体结构中就显得孤立。

顶点、边与相邻顶点的总结如表6-1所示。

表6-1 顶点、边与相邻顶点

概念	定义与含义	特点与性质	示例说明
顶点（Vertex）	图中的一个基本元素，可代表真实世界的对象，如地铁站、城市、人、服务器等	顶点是图结构的核心；每个顶点通常有一个编号或标签；顶点之间通过边连接	在地铁图中，“人民广场站”是一个顶点；在社交网络中，每个用户都是一个顶点
边（Edge）	表示两个顶点之间的连接关系，可以是有方向的（有向边）或无方向的（无向边）	边表示“关系”或“通道”；无向图中边没有方向，有向图中边有箭头；可以带权重表示距离、开销等	地铁站 A–B 的直接连线是一条边；网络图中服务器之间的链路是一条边
相邻顶点（Adjacent Vertices）	被同一条边连接的两个顶点称为相邻顶点	相邻关系取决于是否存在“直接的边”；若没有边，则顶点不相邻；在有向图中通常考虑出边或入边来定义相邻关系	在图6-5中，0–1有边，因此是相邻；0–2没有边，因此不相邻

6.2.2 度、路径与回路

• 度：度指的是一个顶点的度是相邻顶点的数量，即一个顶点与多少个其他顶点直接连接。还是以图6-5为例，顶点0和其他两个顶点相连，顶点0的度是2。顶点1和其他四个顶点相连，顶点1的度是4。
• 路径：路径由一系列顶点组成，形式为 v₁ → v₂ → … → vₙ，每相邻的两个顶点之间都必须具有边。例如图6-5所示的0 1 5 9就是一条路径。路径还区分为简单路径和回路：

（1）简单路径：简单路径要求不包含重复的顶点。例如：0 1 5 9是一条简单路径。

（2）回路：第一个顶点和最后一个顶点相同的路径称为回路（路径的起点与终点相同）。例如：0 1 5 6 3 0。

因此路径是“通过多条边串起来的顶点序列”，而不是某一条边本身。强调的是连续的一段“走法”，由多个顶点串起来，反映的是图中“可到达性”和“经过的路线”。所以边是最小单位的连接，而路径是多个边串联后的结果，边与路径并不相同。

6.2.3 无向图与有向图

• 无向图：如图6-5所示的村庄关系网图就是一张无向图，因为所有的边都没有方向。
• 有向图：有向图表示的图中的边是有方向的。

无向图中的每一条边都没有方向，它表示的是一种“彼此相连”的关系。也就是说，如果 0 和 1 之间存在边，那么这条边同时代表 0 可以到达 1，1 也可以到达 0。这种图更像现实生活中“互相”的联系，例如两个人是朋友、两个城市之间有双向公路、两个设备之间能互相通信。无向图的核心含义是：连接是对称的，关系是双向的。

有向图中的边具有方向，因此它表达的是一种“从 A 指向 B”但是不一定能反过来的关系。比如一条边写作 0 → 1，就表示我们可以从 0 走到 1，但并不能保证能从 1 走回 0，除非另外有一条 1 → 0 的方向边。有向图更适合描述单向过程或单向依赖，例如微博的“关注关系”、城市中的“单行道”、任务调度中的“任务必须先做 A 再做 B”。有向图的本质是：连接不一定对称，关系具有方向性。

从直观上看，无向图更像是“互通”的网络，而有向图更像是“流程”或“限定方向的关系链”。同一对顶点，在无向图里只需一条边就能互达；而在有向图里，是否能互达完全取决于边的方向设置。也正因为方向性的存在，有向图通常适用于描述更复杂的系统，例如依赖关系、因果关系、流动方向等。

6.2.4 无权图与带权图

• 无权图：如图6-5所示的村庄关系网图就是一张无权图（边没有携带权重）。因此我们的村庄关系网的边是没有任何意义的，主要起装饰作用，不能说0-1的边，比4-9的边更远或者用的时间更长。
• 带权图：带权图表示边有一定的权重，这里的权重可以是任意我们希望表示的数据，例如距离或者花费的时间或者票价。无权图与带权图的对比如图6-6所示。

无权图中的每条边都只有“是否存在”这一个含义。它告诉我们：两个顶点之间是否直接相连，但不提供任何关于距离、时间或成本的额外信息。因此在无权图里，0–1 与 4–9 这两条边是完全等价的，它们唯一表达的是“这两个点之间有一条边”。至于实际距离是否远、消耗是否多，在无权图中根本无法判断。所以在像村庄关系网这样的场景里，边更多是“关系的连接线”，而不是衡量价值、距离或时间的工具。

带权图则增加了另一层含义——每条边都有一个权重。这个权重可以表示距离（公里数）、时间（分钟）、花费（票价）、流量容量，或任何想定义的指标。这样一来，边就不仅仅是“相连”，而是“相连且需要付出一定代价”。例如，0→1 可能代表 3 公里，而 4→9 可能代表 10 公里，那么在带权图中，这两条边之间的轻重差异就非常明显。带权图才使得最短路、最低成本路径等算法有意义。

图6-6 无权图与带权图

因此无权图强调的是“结构”，关注点是图是否连通、能否遍历、是否存在路径等拓扑关系；带权图则强调“代价”，因此适用于找最短路径、最低成本、最少时间等应用场景。简单来说：

• 无权图只考虑“有没有路”；
• 带权图既考虑“有没有路”，也考虑“这条路的代价是多少”。

无向图不一定不如有向图，无权图也不一定不如有权图，尽管有向有权所带来的信息更丰富和功能更全面，但功能更强大并不代表在所有问题中更好，有些时候我们就只关心是否连通，是否存在路径等问题上，这时候更多的信息叠加在错综复杂的图上，就会给我们带来额外的负担。

在图论中，添加方向或权重意味着额外复杂性，例如算法更复杂（如最短路算法因权重不同要换不同算法），需要存储更多信息，视觉上也更难读取结构，工程中维护数据也更复杂等问题。所以如果问题能用简单图解决，就不要引入复杂图。原因在于：抽象越多，模型越清晰；信息越多，问题越复杂。 无向或无权图并不是弱版本，它们是更纯粹的抽象，聚焦到更核心的问题上。用无向图、无权图非常常见，也完全没有“弱化”的含义，只有适合应用场景才是最重要的。

6.3 图的表示方法

那怎么在程序中表示图呢?我们知道一个图包含很多顶点，另外包含顶点和顶点之间的连线（边），顶点与边都是非常重要的图信息，因此都需要在程序中体现出来。其余类似于路径、度都是属于延伸概念，无需额外体现。

顶点的表示相对简单，所以我们先讨论顶点的表示。如图6-6所示的顶点，我们抽象成1 2 3 4，也可以抽象成A B C D或者表示其他含义的数据（例如村庄的名字），在之后的案例中，我们就统一使用A B C D的形式来表示。那么这些A B C D我们可以使用一个数组来存储起来（存储所有的顶点）。

那么边怎么表示呢？因为边是两个顶点之间的关系，所以"连接"的概念表示起来会稍微麻烦一些。以下我们会介绍边的两种表达形式。

6.3.1 邻接矩阵表示法

一种比较常见的表示图的方式是邻接矩阵。邻接矩阵让每个节点和一个整数项关联，该整数作为数组的下标值，我们用一个二维数组来表示顶点之间的连接，邻接矩阵如图6-7所示。如果我想表示A->C的这条边，只需要在矩阵中找到 第 A 行、第 C 列 的位置，并将该位置的值设为 1（或设为权重值，如果是带权图）。

在如图6-7的邻接矩阵中，顶点 A 对应行 A；顶点 C 对应列 C。因此表示 A->C 的方式是：matrix[A][C] = 1。

图6-7 邻接矩阵

邻接矩阵为图中的每个顶点分配一个整数编号，并以这个编号作为二维数组的下标。在这种表示中，我们构建一个大小为 n × n 的二维数组，其中 n 是顶点数量。数组的第 i 行第 j 列的元素用于表示“顶点 i 是否与顶点 j 相连”。如果两者之间存在边，我们就在这个位置记录 1（或权重值）；若不存在边，则记录 0。比如 matrix[0][2] = 1 表示编号为 0 的顶点 A 与编号为 2 的顶点 C 之间有一条边。邻接矩阵的核心优点是结构清晰、查询是否相邻的时间复杂度为 O(1)，但也因为需要 n² 的空间，在顶点很多但边较少的稀疏图中会带来额外的存储开销（矩阵中将存在大量的0，这意味着我们浪费了计算机存储空间来表示根本不存在的边）。

所以在二维数组中，0表示没有连线，1表示有连线，通过二维数组，我们可以很快的找到一个顶点和哪些顶点有连线。(比如A顶点，只需要遍历第一行即可)。另外，A-A，B-B（也就是顶点到自己的连线），通常使用0表示，所以我们可以看到图6-7对角线上的数字都是0。

6.3.2 邻接表表示法

邻接矩阵虽然结构简单、查询相邻关系也非常高效，但在边很少的稀疏图中会造成大量空间浪费，因为 n 个顶点需要 n² 的存储空间，其中大部分单元格都是 0。为了解决这种存储低效的问题，图结构更多时候会采用 邻接表。邻接表的思想是：为每个顶点单独维护一个“相邻顶点的列表”，只记录真实存在的边，从而避免无意义的空位占用。这个列表的存储方式非常灵活，可以使用数组、链表、哈希表（字典）等数据结构实现，使得在节省空间的同时，也方便我们快速访问与某个顶点直接相连的所有节点。邻接表如图6-7所示。

图6-7 邻接表

从图6-7中，可以很好的理解邻接表所表达的含义，例如我们要表示和A顶点有关联的顶点（边），那么我们可以通过A找到对应的数组/链表/字典，再取出其中的内容（B、C，D）就可以啦。这种形式看起来与哈希表的键值对格式是有那么一点相似的，键是A；值是BCD。

但邻接表也是存在一些问题的：

邻接表计算"出度"是比较简单的（出度： 指向别人的数量，入度： 指向自己的数量）。但如果邻接表需要计算有向图的"入度"，那么是一件非常麻烦的事情，它必须构造一个“逆邻接表”，才能有效的计算“入度”。但是开发中“入度”相对用的比较少。

6.4 图的实现与操作

6.4.1 图类的创建

接下来，我们要以代码的形式将图结构表现出来。依旧是使用类，先对图结构进行封装，然后定义相关的属性（例如顶点和边），最后来实现图中一些方法或者算法。

首先创建Graph（图）的构造函数（类），这个我们在封装其他数据结构的时候已经非常熟悉了，定义两个私有属性：

（1）verteces： 用于存储所有的顶点，我们说过使用一个数组来保存。

（2）adjList： adj是adjoin的缩写，邻接的意思。 adjList用于存储所有的边，我们这里采用邻接表的形式。

边有两种表达形式，即邻接矩阵和邻接表，我们采用后者。而我们表达过邻接表的形式很像哈希表的键值对形式，因此我们不使用对象来保存，而是采用JavaScript中的标准内置对象Map来保存键值对。其中键用于存放某个具体顶点，而值是一个数组，存放顶点指向其他顶点的边。并且Map对象中的键只能出现一次，这对我们实现图结构是非常有利的，图结构的顶点都是唯一的，Map对象的该特性令我们无需在去判断键是否出现过。

属性设置为私有，是因为顶点与边是图结构的基本单位，我们后续的所有操作都依赖这两个属性，一旦被外部修改，会导致整个图结构的崩溃。这些具体的实现细节不应该暴露给使用者。

▼
ts
复制代码
class Graph<T> {
  // 顶点
  private verteces: T[] = []
  // 边: 邻接表
  private adjList: Map<T, T[]> = new Map()
}

const graph = new Graph()

export {}

6.4.2 添加顶点与边的方法

添加顶点非常简单，因为顶点是可以独立存在的，我们只需要将需要添加的顶点push到verteces属性（数组）中就可以了。但在添加顶点时，需要同步创建一个顶点对应的邻接表，该邻接表的键为顶点，值则设置成一个空数组，方便后续添加该顶点指向其他顶点的边。

▼
ts
复制代码
addVertex(vertex: T) {
  // 将顶点添加数组中保存
  this.verteces.push(vertex)
  // 创建一个邻接表中的数组
  this.adjList.set(vertex, [])
}

测试代码如下：

▼
ts
复制代码
const graph = new Graph()
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")
graph.addVertex("F")
graph.addVertex("G")
graph.addVertex("H")
graph.addVertex("I")

但如果我们想快速执行AZ的输入，我们可以利用Unicode码位转换来实现连续字母的快速输入。String.fromCharCode()静态方法能将Unicode码位转为对应的内容。AZ的区间在65-90之间，a~z的区间在97-122之间。

▼
ts
复制代码
for (let c = 97; c <= 122; c++) graph.addVertex(String.fromCharCode(c));

接下来实现添加边的addEdge()方法，该方法需要接受两个参数：即构建边的两个顶点参数。

拿到顶点后可以去匹配Map对象（邻接表）中的键，匹配上之后，将另一顶点，放入相邻顶点的列表中，从而实现边的添加。由于我们目前的图是无向图，因此同样的操作要反着再来一遍，两个顶点都要操作，都要有通向另一顶点的边。

因为数组是引用类型，所以我们只要通过Map.prototype.get()实例方法获取到邻接表后，直接将顶点push到邻接表中。所有引用数组内存地址的数据都会同步更新。

▼
ts
复制代码
addEdge(v1: T, v2: T) {
  this.adjList.get(v1)?.push(v2)
  this.adjList.get(v2)?.push(v1)
}

完成以上两个核心方法：添加顶点，添加边。我们能够依靠这两方法实现一个基本的无向图。那么来测试一下方法是否能够实现图结构。

6.4.3 图结构的打印与测试

当我们通过测试代码添加对应的顶点与边之后，我们要如何拿到形成的图结构的结果？

图结构的展现是可以通过邻接表体现出来的，所以理论上我们将邻接表打印出来就能得到图结构的测试结果。打印邻接表并不困难，我们通过Map对象的size实例属性获取邻接表中一共有多少个元素，然后遍历使用Map.prototype.entries()实例方法将所有键值对打印出来就行。因此我们创建traverse()方法，用于将邻接表打印出来。

▼
ts
复制代码
  // 方法一
  traverse() {
    for (const [vertex, edges] of this.adjList.entries()) console.log(`${vertex} -> ${edges.join(" ")}`)
  }

除此之外，我们还可以遍历维护的verteces数组，该数组存放了图结构所有的顶点，再通过Map.get()找到每个vertex的邻接数组。

▼
ts
复制代码
// 方法二
traverse() {
  console.log("Graph:")
  this.verteces.forEach(vertex => {
    const edges = this.adjList.get(vertex)

    console.log(`${vertex} -> ${edges?.join(" ")}`)
  })
}

其实两种方法都是可以的，打印效果也是一致的，但我推荐大家使用方法一的adjList.entries()会更好，因为真实的图数据存在于邻接表（不是顶点数组）。图结构实际上是：

• 顶点 —— 存在 adjList.keys()。
• 边 —— 存在 adjList.values()。

vertices[]只是我们人为维护的额外结构，真正决定图结构的是Map本身。假如以后我们写了一个删除顶带你的操作，我们删除了Map对象中的key，但忘记从vertices[]里删，就会导致traverse()方法出来的图节点跟实际的图不一致，这是图结构常见的bug，很难排查。

所以，我们应该尽可能少的去维护状态，会更安全。通过Map对象本身的key去获取本身的value才是最合适的，图的定义最好只来源于一个结构。

完整测试代码如下。

▼
ts
复制代码
class Graph<T> {
  // 顶点
  private verteces: T[] = []
  // 边: 邻接表
  private adjList: Map<T, T[]> = new Map()

  /** 添加顶点和边的方法 */
  addVertex(vertex: T) {
    // 将顶点添加数组中保存
    this.verteces.push(vertex)
    // 创建一个邻接表中的数组
    this.adjList.set(vertex, [])
  }

  addEdge(v1: T, v2: T) {
    this.adjList.get(v1)?.push(v2)
    this.adjList.get(v2)?.push(v1)
  }

  // 方法一
  traverse() {
    for (const [vertex, edges] of this.adjList.entries())
      console.log(`${vertex} -> ${edges.join(" ")}`)
  }
}

const graph = new Graph()
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")
graph.addVertex("F")
graph.addVertex("G")
graph.addVertex("H")
graph.addVertex("I")

graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

graph.traverse()


export { }

测试代码打印输出效果如图6-8所示。

图6-8 图结构的实现（打印结果）

6.5 图的遍历算法

实现添加顶点与边的方法之后，基本的图结构就能实现，其次通过traverse()方法完成图结构的打印与测试。接下来我们就来学习一下图结构的遍历。

图结构的遍历很有意思，如果由我们来实现，我们需要考虑哪些问题？

遍历之前，我们知道图是由顶点和边组成的，那我们遍历图的目的是什么？是想访问所有的顶点，还是沿着边去遍历结构？

而且图结构与树不同，在6.2.2小节中，我们有说明回路的概念，也就是图是有可能有环的；在6.1.3小节的七桥问题中，甚至是存在没办法一次性走通的情况，这两点的存在让我们遍历图的时候，必须要避免死循环以及遍历不完整的情况。所以我们第一件事一旦是怎么记录已经访问过的节点？

并且我们不能保证一次性遍历就覆盖所有节点，仅从一个起点出发可能走不到所有节点，所以需要考虑是否要从每一个未访问过的节点重新启动遍历？从一个节点开始遍历之后，我们的遍历顺序要怎么控制？需要的数据结构是什么？以及需要标记访问过的顶点吗（防止重复访问）？邻接表的访问顺序是什么？遍历的结果输出成什么形式？以及是否考虑图的方向性（无向图与有向图）？遍历是否要处理权重值（无权图与有权图）？遍历的时候我们需要设置哪些边界判断？

因此图遍历需要考虑的问题较多，图遍历比树遍历更复杂，对应问题顺序表如表6-2所示。

表6-2 图结构的遍历问题

层级	需要考虑的问题
0	图是什么？结构如何保存？
1	图有环、可能不连通
2	是否确保遍历所有组件？
3	选 BFS 还是 DFS？是否需要 visited？
4	邻接节点的访问顺序如何控制？
5	遍历结果如何输出？
6	图是有向还是无向？是否影响遍历？
7	是否考虑边权重？
8	如何避免错误输入、死循环、多重边等问题？

那我们这里遍历的是一个普通基础的图结构，不考虑图的方向和权重，对边界判断不会非常细致的去做，更侧重遍历的方式。

常见的遍历图结构的方式有两种：

（1）广度优先搜索（Breadth-First Search，简称BFS）。

（2）深度优先搜索（Depth-First Search，简称DFS）。

两种遍历算法，都需要明确指定第一个被访问的顶点。

BFS与DFS的遍历过程分别是怎么样的呢？我们以一个迷宫中关灯的案例说明：现在需要我们走进迷宫，将迷宫中的灯一个个关掉，你会怎么关？迷宫关灯案例如图6-9所示。

图6-9 迷宫关灯案例

关灯不能重复，那么我们有两种BFS和DFS两种遍历算法方式，这两种方式所采用的结构各不相同：

（1）BFS：基于队列，入队列的顶点先被探索。

（2）DFS：基于栈或使用递归，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问。

如果我们使用 BFS，当走进迷宫时采取“先把附近所有灯都关掉，再走向更远的灯”这样的策略。从入口处开始，先检查离你最近的一圈房间，把这一层所有的灯依次关掉；然后再走向下一圈稍远的房间，再把这一层所有灯关掉。我们的行动像水波一样一层层往外扩散，每一层的所有灯都是成批处理的。它的特点是：靠着“先到先关”的队列，永远先处理最近的位置，因此如果我们想找到“从入口到某一盏灯的最短路径”，BFS 是最可靠的办法。

如果我们使用 DFS，当走进迷宫后，会选一条通道一路走到尽头，把沿途遇到的灯全部关掉；走到死胡同时再往回走，在分叉口换另一条没走过的路继续深入，把能关的灯都关掉。我们的行为像是不断“向下钻”，直到走不动就回溯，然后换一个分支继续探索。它依赖递归或栈来记录路径，特点是：深度优先、不关心最短路线，但特别适合“整个迷宫全部走一遍，把每一盏灯都关掉”这种彻底探索的任务。

补充概念：visited集合概念来自图（Graph），指用来记录“哪些节点已经访问过”的专用数据结构，用来避免重复访问和避免死循环。

而为了记录顶点是否被访问过，我们使用3种颜色来反应它们的状态：

（1）白色： 表示该顶点还没有被访问。

（2）灰色： 表示该顶点被访问过，但并未被探索过。

（3）黑色： 表示该顶点被访问过且被完全探索过。

或者我们也可以使用JavaScript标准内置对象中的Set对象来存储被访问过的节点。Set对象是值的合集（collection）。集合（set）中的元素只会出现一次，即集合中的元素是唯一的。每次我们想访问一个顶点时，就先去Set对象中看有没有这个顶点，如果Set对象已经有存储对应顶点，那我们就不再访问；如果Set对象中没有，那么访问的同时，将该顶点放入Set对象中。

但如果只是为了判断集合中是否存在已经访问过的顶点，好像数组也可以做到，为什么我们不用数组？首先数组是有序的列表，是可以包含重复元素的，这和visited集合概念冲突，因为visited集合不关心顺序，它本质是"状态"。当然，我们会手动判断的，不会让重复的元素（顶点）进到数组当中。从这种角度来说，虽然数组不适合做访问标记，但好像实在要做也不是不行？

当然不是这样的，还有一个最核心的理由，图是错综复杂的，判断是否存储过顶点意味着大量的查找操作（每访问一个节点都要查一次），而数组的查找性能是O(n)，即经典的线性查找，在刚开始学习数据结构与算法的时候就已经学习到，性能上的缺陷是我们摒弃数组最核心的原因，也是数组这一数组结构无法解决的问题。如果用数组，节点越多，性能越差，在大图上会明显变慢。

相对数组来说，Set对象核心理念是无重复（自动判断）、无序、查存在。这和BFS与DFS的“visited集合”概念（不允许重复、用来判断某个节点是否访问过以及不关心顺序）是一致的。最关键的在于Set对象的查找操作是哈希查找，就是我们在学习哈希表所听过的那个哈希，查找性能是常数时间O(1)，速度优势巨大。

6.5.1 广度优先搜索算法（BFS）

广度优先搜索算法的思路就是从起点开始按层级逐圈向外扩展，会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。换句话说，就是先宽后深的访问顶点，类似于树结构遍历的层序遍历，如图6-10所示。

图6-10 广度优先算法（BFS）

我们的代码示例不采用3色标记状态，而是采用Set对象访问标记，会更加方便简洁，那么这就开始实现bfs()广度优先算法方法，思路为以下3步：

（1）首先我们需要判断图结构是否存在顶点（边界判断），这一步就像判断树结构是否存在根节点一样，如果图结构的顶点不存在那就可以直接返回了。

（2）其次创建队列结构来探索顶点，创建Set对象来访问标记顶点，将图结构的第一个顶点放入到队列与Set对象中作为指定第一个被访问的顶点。

（3）满足前置条件后，就可以遍历队列中的每一个顶点。

遍历队列采用BFS，因此我们首先要将第一个顶点取出并打印，然后将顶点A指向的其他顶点放入队列中（从邻接表中直接获取），在下一轮遍历中取出第二个顶点，然后将第二个顶点指向的其余顶点继续放入队列中。每次循环从队列取出一个顶点，而队列又新增取出顶点所指向其余新顶点，当队列清空后，结束遍历。

这里需要注意的是，每次队列新增顶点时，都需要通过Set对象查询判断是否已访问过，只有未访问过的顶点才能放入队列中，而放入队列的顶点同时也要放入Set对象中，确保其状态处于已经访问。顶点加入Set对象的时机非常重要：应该在入队前，而不是出队后，因为入队之后不是马上可以出队的，每次出队只出一个顶点，其余顶点需要排队，在排队的这段时间内，顶点若未加入Set对象，可能导致多次被不同父节点重复入队。

▼
ts
复制代码
bfs() {
  // 1.判断是否有顶点
  if (this.verteces.length === 0) return

  // 2.创建队列结构访问每一个顶点
  const queue: T[] = []
  queue.push(this.verteces[0])

  // 3.创建Set结构, 记录某一个顶点是否被访问过
  const visited = new Set<T>()
  visited.add(this.verteces[0])

  // 4.遍历队列中每一个顶点
  while (queue.length) {
    // 访问队列中第一个顶点
    const vertex = queue.shift()!
    console.log(vertex)

    // 相邻的顶点
    const neighbors = this.adjList.get(vertex)
    if (!neighbors) continue
    for (const nei of neighbors) {
      if (!visited.has(nei)) {
        visited.add(nei)
        queue.push(nei)
      }
    }
  }
}

BFS与层序遍历的思路很相似，因此这对于大家来说并不难理解。

6.5.2 深度优先搜索算法（DFS）

深度优先搜索算法的思路就是从起点开始沿着一条路径不断向深处探索，直到不能再往下为止再回溯到上层换一条未走过的路径继续前进，换句话说，就是先深后宽地访问顶点，类似于树结构遍历中的先序遍历，如图6-11所示。

图6-11 深度优先算法（DFS）

深度优先搜索算法与广度优先搜索的思路不同，它不会按层级扩散，而是会优先沿一条路径一直向深处探索，直到无法继续为止，再回退到上一个可以继续探索的位置继续深入。我们同样不采用三色标记状态，而是使用Set对象进行访问标记，这让整个算法更加轻量、直观，也便于JavaScript中以集合方式判断顶点是否被访问过。

DFS有两种做法，一种是栈的做法，一种是递归的做法，我们采用栈的做法，思路为以下3步：

（1）首先，同样要进行边界判断。判断图结构是否存在顶点，如果图中没有任何顶点，那么深度优先遍历无法进行，可以直接返回。这一步与树没有根节点无法遍历的逻辑一致，是 DFS 的第一道前置条件。

（2）接着，需要创建一个**栈结构（stack）**来驱动深度优先的“深度”行为。DFS 使用栈来记录访问路径：从第一个顶点开始，将它压入栈中，并在同时将它加入 Set 对象中标记为已经访问。这里要特别说明：和 BFS 完全相同，**顶点加入 Set对象 的时机也必须是“入栈之前”**而不是“出栈之后”，否则相邻的父节点在递归回溯前都可能重复把同一个未标记的节点加入栈中，导致重复访问甚至死循环。

（3）满足前置条件后，就可以正式开始遍历栈中的顶点。DFS 的遍历方式是：每次循环从栈顶弹出一个顶点（这一步使得 DFS 总是优先沿当前路径最深处走），打印它，然后读取该顶点的所有邻接点。这里的邻接点顺序很重要：我们从邻接数组末尾向前遍历，将未访问过的邻接点压入栈中，使得数组中靠前的邻接点能够更早地被弹出、从而走成一条更自然的“深度路径”（例如图6-11所示，顶点A弹出栈之后，我们本来是要先将B C D按顺序压入栈中，但这样的话，D会先出来，为了更有顺序，我们先将D先压入栈中，接着是C和B，这样栈的弹出顺序就为BCD，之后也是从末尾往前遍历）。当子路径全部探索完毕，栈会逐渐退回，从而继续探索其它分支。最终，当栈被清空，说明所有路径都已经被走过，整个深度优先遍历结束。

▼
ts
复制代码
dfs() {
  // 1.判断有没有订单, 没有直接返回
  if (this.verteces.length === 0) return

  // 2.创建栈结构
  const stack: T[] = []
  stack.push(this.verteces[0])

  // 3.创建Set结构
  const visited = new Set<T>()
  visited.add(this.verteces[0])


  // 4.从第一个顶点开始访问
  while (stack.length) {
    const vertex = stack.pop()!
    console.log(vertex)

    const neighbors = this.adjList.get(vertex)
    if (!neighbors) continue // 类型缩小
    // 反着遍历
    for (let i = neighbors.length - 1; i >= 0; i--) {
      const nei = neighbors[i]
      if (!visited.has(nei)) {
        // 顶点加入 Set对象 的时机也必须是“入栈之前
        visited.add(nei)
        stack.push(nei)
      }
    }
  }
}

6.5.3 遍历算法的实现与比较

在图结构中，BFS 的遍历路线是“按层级展开”，从起点向外一圈圈扩散，确保离起点越近的节点越早被访问。这使 BFS 具备天然的层级结构，像一层一层剥洋葱一样访问图。相对地，DFS 的路线是“沿路径不断向深处钻”，它会沿着某条路径一直走到底部再回溯回来。因此，BFS 的访问顺序体现水平层级，而 DFS 的访问顺序体现路径深度。

在最短路径问题中：BFS 更有优势。对于无权图（每条边成本相同），BFS 是寻找起点到任意终点最短路径的最佳选择。因为 BFS 必须先访问完第 1 层的所有节点，再访问第 2 层，因此当你第一次在 BFS 中遇到目标节点时，那条路径一定就是最短路径。而 DFS 不能保证这一点：它可能会先沿着一条特别深的分支走很久，找到一个长路径后才回溯，导致你看到的并不是最短路径。因此，在图中寻找最短路径、最小步数的场景中，BFS 更适用于路线规划、迷宫最短出口、社交网络的最少关系链等问题。

在结构探索和连通性判断中：DFS 更有优势。DFS 的强项是“深入探索”，它天然适合把一个连通区域内所有节点都走完。因此，如果你的目标不是最短路径，而是判断图是否连通、寻找连通分量、检测环（cycle detection）、拓扑排序、判断是否存在某条路径等结构性问题时，DFS 的递归特性让它更容易实现，也更适合这类深度分析。例如图中是否存在环、某个节点是否可到达另一个节点、一个区域是否完全相连，这些问题 DFS 都比 BFS 更高效与更自然。

在空间复杂度上：DFS 通常更节省内存。BFS 需要维护一个可能很大的队列，这在宽度非常大的图中可能会导致内存开销剧增。例如一棵非常矮但非常“宽”的树，BFS 可能需要一次性存储成千上万的兄弟节点。而 DFS 的栈深度最多只会和图的深度一样，哪怕图很宽，只要深度不大，DFS 都可以用极少的额外空间完成遍历。因此在空间资源有限、图很大但深度不深的场景中，DFS 更具优势。

如果我们的目标是“尽快找到某个特定节点”或“找到最短路径”，那么 BFS 因为它的层级推进特性，更容易在浅层就找到目标，是典型的目标搜索算法。而如果想要的是“把整个图跑完并提取结构信息”，例如遍历所有节点、生成拓扑结构、检测连通区域等，那么 DFS 的深度探索与回溯机制更适用于这类全局性的结构问题。

两者都必须依赖 visited 集合防止重复访问，但它们在遇到环时表现不同： （1）BFS 在遇到环时，只会在访问邻居时判断 visited，那些已访问节点会被完全跳过，不会陷入死循环； （2）DFS 若没有 visited，则会一直沿环中的路径循环下去，永不回头。因此在复杂、有环的图结构中，DFS 对 visited 的依赖更强。也正因为 DFS 的深入特性，它更适合用来检测环（cycle detection），因为沿深度回溯时你能清楚看到当前路径上是否再次遇到已访问节点。

总的来说，BFS更适合“找最近的”“找最短路径”“按层级扩散”“目标搜索”。而DFS更适合“彻底探索结构”“判断连通性”“检测环”“拓扑排序”“内存较少时的遍历”。

图的完整代码如下。

▼
ts
复制代码
class Graph<T> {
  // 顶点
  private verteces: T[] = []
  // 边: 邻接表
  private adjList: Map<T, T[]> = new Map()

  /** 添加顶点和边的方法 */
  addVertex(vertex: T) {
    // 将顶点添加数组中保存
    this.verteces.push(vertex)
    // 创建一个邻接表中的数组
    this.adjList.set(vertex, [])
  }

  addEdge(v1: T, v2: T) {
    this.adjList.get(v1)?.push(v2)
    this.adjList.get(v2)?.push(v1)
  }

  traverse() {
    for (const [vertex, edges] of this.adjList.entries()) console.log(`${vertex} -> ${edges.join(" ")}`)
  }

  bfs() {
    // 1.判断是否有顶点
    if (this.verteces.length === 0) return
    
    // 2.创建队列结构访问每一个顶点
    const queue: T[] = []
    queue.push(this.verteces[0])

    // 3.创建Set结构, 记录某一个顶点是否被访问过
    const visited = new Set<T>()
    visited.add(this.verteces[0])

    // 4.遍历队列中每一个顶点
    while (queue.length) {
      // 访问队列中第一个顶点
      const vertex = queue.shift()!
      console.log(vertex)

      // 相邻的顶点
      const neighbors = this.adjList.get(vertex)
      if (!neighbors) continue
      for (const nei of neighbors) {
        if (!visited.has(nei)) {
          visited.add(nei)
          queue.push(nei)
        }
      }
    }
  }

  dfs() {
    // 1.判断有没有订单, 没有直接返回
    if (this.verteces.length === 0) return

    // 2.创建栈结构
    const stack: T[] = []
    stack.push(this.verteces[0])

    // 3.创建Set结构
    const visited = new Set<T>()
    visited.add(this.verteces[0])


    // 4.从第一个顶点开始访问
    while (stack.length) {
      const vertex = stack.pop()!
      console.log(vertex)

      const neighbors = this.adjList.get(vertex)
      if (!neighbors) continue // 类型缩小
      for (let i = neighbors.length - 1; i >= 0; i--) {
        const nei = neighbors[i]
        if (!visited.has(nei)) {
          visited.add(nei)
          stack.push(nei)
        }
      }
    }
  }
}

const graph = new Graph()
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")
graph.addVertex("F")
graph.addVertex("G")
graph.addVertex("H")
graph.addVertex("I")

graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

graph.traverse()

graph.dfs()


export {}

6.6 图结构的应用建模

图结构的应用非常多，例如可以对一些现实案例进行建模，例如交通流量与飞行航线。

6.6.1 交通流量建模

在交通流量建模中，图结构可以表示城市道路网络。我们可以将街道的十字路口作为顶点，而连接这些顶点的边则表示街道本身。为了进一步量化道路的特性，边可以赋予权重，例如道路的限速、车道数量或者街道长度。这种加权图不仅能够展示道路的基本结构，还可以为交通分析提供精确的数据支持。通过这个模型，交通管理部门或智能导航系统能够分析不同路线的通行效率，从而判定最佳行车路线，并预测可能出现交通拥堵的街道，从而优化交通调度和规划。像类似高德地图为什么总能精准预测我们到达目的地的时间，也许就是基于这些因素来计算得出的。

6.6.2 飞机航线建模

同样地，在飞机航线建模中，图结构也发挥着重要作用。航空公司可以将每个机场视为顶点，而连接两个机场的航线作为边进行建模。为了评估航线的经济性或效率，这些边可以赋予权重，例如航班成本、飞行时间或两个机场之间的实际距离。通过这种加权图模型，航空公司可以快速计算从一个城市到另一个城市的最优航线，既可以考虑成本最小化，也可以优化飞行时间或里程。同时，这种建模方式还可以帮助航空公司分析航线网络的可靠性，识别潜在的瓶颈或高负荷节点，从而提高整体运营效率。

总的来说，无论是城市交通还是航空航线，图结构都为复杂网络提供了清晰的抽象和量化方法。通过顶点表示节点、边表示连接、权重刻画特性，建模人员能够在理论层面和实践应用中有效分析路径选择、成本优化以及潜在风险。这种方法不仅提高了决策的科学性，也为智能交通系统和航空运营管理提供了坚实的基础。

到目前位置，数据结构与算法第一阶段（基础）就告一段落，接下来从第7章开始，我们会深入数据结构与算法，讲解一些更进阶一些的数据结构，例如循环链表、双向链表、堆结构、双端队列、二叉堆、最大堆、AVL树、红黑树以及动态规划和各种排序算法，最后在去刷LeetCode的一些高频题目。