图论中一些与之相关最基本重要的定义 _小知识

文章插图

图如何解决探索迷宫问题之前，我们必须解决迷宫的一般性表示方法。回忆我们曾经描述迷宫的方式，它们由房间和房间之间的廊道组成。我们暗示过，当认识到迷宫与其他结构相似时，问题就变得更有趣了。实际上，迷宫与任何由对象和对象间的连接组成的东西是相似的。
这是一种基础数据结构，可能是所有数据结构中最基础的，因为现实世界中很多事物都可以表示为对象和对象间的连接。这种结构被称为「图」（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），即从某个顶点是否能到达其他某个顶点。