图

如何解决探索迷宫问题之前，我们必须解决迷宫的一般性表示方法。回忆我们曾经描述迷宫的方式，它们由房间和房间之间的廊道组成。我们暗示过，当认识到迷宫与其他结构相似时，问题就变得更有趣了。实际上，迷宫与任何由对象和对象间的连接组成的东西是相似的。

这是一种基础数据结构，可能是所有数据结构中最基础的，因为现实世界中很多事物都可以表示为对象和对象间的连接。这种结构被称为「图」（graph）。

一个简洁的定义是：图就是一个节点（node）与其之间的连接（link）组成的一个集合。你可以使用术语「顶点」（vertex，复数形式为 vertices）和「边」（edge）。一条边连接恰好有两个顶点。一个边的序列中，如果每两条相邻边都有公共顶点，则我们称之为「路径」（path）。因此，在图 2-2 中有一条从顶点 0 到 2 经由顶点 1 的路径。一条路径中边的条数称为其长度（length）。一条边就是一条长度为 1 的路径。如果两个顶点间存在一条路径，则我们说两个顶点是「连接的」（connected）。在特定的图中，我们可能希望边是有方向的，这种图称为「有向图」（directed graph，或简写为 digraph）。否则，就是「无向图」（undirected graph）。图 2-5 左边是一个无向图，右边是一个有向图。如你所见，可能有多条边从同一个顶点发出或指向同一个顶点。一个顶点邻接边的数目称为它的度（degree）。在有向图中，度分为「入度」（in-degree），即入射边的数目，以及「出度」（out-degree），即出射边的数目。在图 2-5a 中，所有顶点的度都恰为 3。在图 2-5b 中，最右边的顶点的入度为 2，出度为 1。

图的应用可以撑起一整套丛书：令人惊讶的是有这么多事物可用图表示，这么多问题可用图的术语描绘，又有这么多用来求解图相关问题的算法。其原因是，如我们刚刚发现的，很多事物都是由对象及对象间的连接组成的。这值得进一步关注。

如我们已经暗示过的，可能图最明显的应用就是表示网络。网络中的节点就是图中的顶点，链路就是顶点间的边。世界上有很多不同种类的网络。计算机网络（computer network）当然是其中一种，计算机相互连接在一起。但也有运输网络（transport network），城市通过公路、飞机航线和铁路连接在一起。在所有计算机网络中，互联网（Internet）是最大的，万维网（web）也是一种网络，网页是顶点，它们通过超链接连接起来。维基百科（wikipedia）是一个特别大的网络，它是万维网的一个子集。在电子领域，电路板（circuit board）由晶体管等电子器件组成，这些器件通过电路连接起来。在生物学中我们会遇到代谢网络（metabolic network），它由很多部分组成，其中最主要的是代谢途径：化学物质通过化学反应连接起来。社交网络（social network）用图来建模，人为顶点，人之间的关系为边。人或机器的工作和任务的调度（scheduling）也可用图来建模，任务为顶点，任务间的依赖关系（如哪个任务应该在其他哪些任务之前完成）用边来表示。

对上述所有应用，以及其他应用，有不同类型的图适合于表示不同情况。如果图中任意顶点到任何其他顶点都存在路径，则称图是连通的（connected），否则称为不连通的（disconnected）。图 2-6 显示了一个连通图和一个不连通图，两个图都是无向图。注意，对一个有向图，我们在确定其是否连通时必须考虑边的方向。在一个有向图中，如果任意两个顶点间都有一条有向路径（directed path），则称它是强连通的（strongly connected）。如果我们出于某种原因忘记方向，只对任意两个顶点间是否存在无向路径（undirected path）感兴趣，则图称为弱连通的（weakly connected）。如果一个有向图既不是强连通的，也不是弱连通的，则简单称它是不连通的。图 2-7 展示了这三种情况。对于用图来建模的事物，当我们希望确定它是由一个完整实体表示还是由分离的子实体组成时，就会产生图的连通性问题。无向图中连接的子实体和有向图中强连接的子实体称为连通分量（connected component）。因此，如果一个图只由单一连通分量组成，则它是一个连通图（强连通有向图）。一个相关的问题是可达性（reachability），即从某个顶点是否能到达其他某个顶点。

在一个有向图中，可能出现这种情况：从一个顶点开始，沿着边前进，最终回到起始顶点。如果发生了这种情况，表明我们走了一个圈，我们走过的路径形成了一个环（cycle）。在一个无向图中，如果允许向后退，我们总能回到起点，因此我们说走了一个圈指的是在不沿着边后退的情况下回到起点。存在环的图被称为有环的（cyclic），不包含环的图被称为无环的（acyclic）。图 2-8 显示了两个包含多个环的有向图。注意，右边图中的一些边的起、止都是同一个顶点。这些边形成了长度为 1 的环，我们称之为自环（loop）。自环在无向图中也是可能的，但并不常见。有向无环图出现在非常多的应用中，以至于人们特意为其起了一个名字，简称 dag。为了使这部分图形完整，图 2-9 显示了两个无环图，一个是无向的，另一个是 dag。

将一个图的顶点分为两个集合，使得所有边都是连接一个集合中的顶点和另一个集合中的顶点，这是可能的，这样我们就得到了一个二部图（bipartite graph）。二部图的一个经典应用是匹配（matching）问题，其中我们希望将一个集合中的实体与另一个集合中的实体进行匹配（例如，可能一个集合中是人，另一个集合中是分配给人的任务）。实体表示为顶点，指出实体兼容的连接用边表示。为避免陷入困境之中，实体间一对一精确匹配是很重要的。如图 2-10 所示，一个图是否为二部图，检查结论并不总是那么清晰，除非我们重新安排顶点位置。

有大量边的图和没有大量边的图有着重要区别。一个图如果有大量的边，我们称它是稠密的（dense），否则我们称它是一个稀疏图（sparse graph）。一种极端情况是，在一个图中可能任意两个顶点间都有边相连，这种图被称为完全图（complete graph），你可以在图 2-11 中看到一个例子。显然，它有很多条边。对 n 个顶点的图，由于每个顶点连接到所有其他 n-1 个顶点，我们有 n(n-1)/2 条边。一般而言，如果一个 n 个顶点的图有接近 n² 条边，我们就可以说它是稠密的，如果它的边数接近 n，就称它是稀疏的。这在 n 和 n² 间留下了一个模糊区域，但我们通常从上下文就可以知道我们处理的是稀疏图还是稠密图。实际上大多数应用使用的是稀疏图。例如，设想我们有一个图表示人之间的朋友关系。我们以一个包含 70 亿(n=7×10^9)个顶点的图为例，即假定这个星球上几乎所有人都在这个图中。我们还假定每个人连接到 1000 个朋友，这在实际中几乎是不可能的。则边的数量为 7×10^12，即 7 万亿。而对于 n=7×10^9，n(n-1)/2 的值约为 2.5×10^19，即约 2000 亿亿，这远大于 7 万亿。这个例子说明，一个图可能有非常多的边，但它仍是稀疏的。

本文摘编自机械工业出版社华章公司出版的《真实世界的算法：初学者指南》，[遇见] 已获授权。

推荐阅读： 算法的第一本入门书籍，带领你踏上算法学习之路。本书通过真实世界中需要解决的实际问题来介绍算法，这些算法用伪代码表示，可以很容易地用计算机语言实现。算法尽量简单，避免读者有挫败感，仅需基本数学基础和计算机常识知识。通过真实世界需要解决的实际问题来介绍算法思想。为各领域高效运用算法提供重要指南。