23 图：如何用图表达错综复杂的数据？

你好，我是王健伟。

经过了长期努力，我们一起学习了树相关的知识。树是整个课程中占据篇幅最大的话题，也是面试和使用中的热门话题。而这一次，我们来说一说图。

图这种数据结构比树更加复杂。我们回想一下，树形结构中的节点或者说数据之间有明显的层次关系，一个父节点可以有多个子节点，当然，一个子节点只能有唯一的父节点。但在图形结构中，节点之间可以有任意的关系，即任意两个数据都可能相关。

关于图，有哪些必备的基本概念和术语？

图涉及的概念和术语比较多，请你投入一定的耐心学习。不过，这些概念和术语不用强记，只需要有印象，后面使用到这些术语的时候再到这节课看看就可以，反复几次，这些概念和术语自然也就记住了。

顶点、边、阶

先看一些基本概念。在图中，数据元素被称为顶点，和在树中将数据元素称为节点是有区别的，用v（Vertex）表示。不同的顶点之间的连线称为边，用e（Edge）表示。

图（Graph）是由顶点的有穷非空集合和顶点之间的连线（边）的集合组成。通常表示为G=(V,E)，其中G表示一个图，V(G)代表图G中的顶点集合，E(G)代表图G中的边集合。

用|V|表示图G中顶点个数，也称为图G的阶。

用|E|表示图G中边的条数。

图1所示就是一个图，其中A、B、C、D、E、F是顶点。

注意了，图不可以为空，换句话说，顶点集合V不可以为空集。而边集合E可以为空，所以，图2也是一个图。

无向图、有向图、简单图、多重图、完全图

如果你刚才观察得仔细，一定会发现上面介绍的图中的边是没有方向的，这种边就叫做无向边（简称边）。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图，比如图1就是无向图。

当然，从一个顶点到另外一个顶点的边也可以是有方向的，这种边称为有向边，也称为弧。如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。图3就是一个有向图：

对于无向图，只要两个顶点之间有一条边，则这两个顶点之间可以互相到达。图1中，连接顶点A与B之间的边因为不存在方向问题，因此可以表示为无序对(A,B)或者(B,A)，注意这里用的是圆括号表示无向边。

有向图不同。在图3中，顶点A到B之间存在一条有向边（从A指向B的箭头），这表示从顶点A可以到达顶点B，但因为顶点B到顶点A之间并不存在有向边，所以从顶点B不可以到达顶点A。

这里你可以设想一下微博用户之间的关系。你关注喜欢的账号之后，可以看到对方发的消息，但这并不等于人家也关注了你，如果对方没有关注你，那也看不到你发的消息。

顶点A到顶点B的有向边（箭头）就是弧。箭头开始的顶点A叫弧尾，箭头指向的顶点B叫弧头。这条弧可以用<A,B>表示，注意这里用的是尖括号表示有向边。另外还需要注意方向，不可以写成<B,A>。

图中若不存在顶点到其自身的边，并且同一条边不会重复出现，这种图称为简单图。简单图分为简单无向图（如图1）和简单有向图（如图3）。

图中某两个顶点之间的边数多于一条，或者顶点通过一条边和自己关联，这种图称为多重图。多重图分为多重无向图和多重有向图，如图4所示：

数据结构中所讨论的图都是简单图，多重图不在讨论之中。基本上，绝大部分问题通过简单图都可以得到解决，比如微信中不需要自己加自己为好友，也不需要加同一个人多次好友。

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。如图5所示：

仔细观察后会发现，含有n个顶点的无向完全图有$\frac{n(n-1)}{2}$条边。比如图5，一共有5个顶点，每个顶点有4条边，所以一共有20条边，但因为边是两两重复的，比如顶点A与顶点B的边也是顶点B与顶点A的边，所以边数要除以2也就是20/2=10条边。

在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。如图6所示：

从图6中不难看到，含有5个顶点的有向完全图含有20条边，因此，含有n个顶点的有向完全图有n(n-1)条边。

有很少条边或者弧的图称为稀疏图，反之称为稠密图。这里稀疏和稠密都是相对而言的，并不是一个精确的数值。

顶点的度、入度、出度

针对边的讨论结束之后，我们看看和顶点相关的一些概念。

在无向图中，顶点v的度（Degree）是和v相关联的边的数目，记为TD(v)。

比如图1中，顶点A的度为3。深入思考一下，无向图中，因为一条边可以给与这条边相连接的两个顶点分别提供1度，所以，无向图中所有顶点的度之和就应该是边数*2，即2|E|。

在有向图中，以顶点v为终点（箭头指向v）的有向边的数目称为顶点v的入度（InDegree），记为ID(v)。以顶点v为起点的有向边的数目称为顶点v的出度（OutDegree），记为OD(v)。所以，有向图中顶点v的度等于其入度和出度之和，既TD(v)=ID(v)+OD(v)。

比如图3中，顶点A的入度为1，出度为3，所以顶点A的度为4。有向图中，因为一条边可以给与这条边相连接的两个顶点分别提供1出度和1入度，所以有向图所有顶点的入度之和与出度之和相等并且等于弧的数量。

顶点之间的关系、路径、边

现在，我们可以把顶点和边联系起来了。

顶点$v_{m}$和顶点$v_{n}$的路径是一个顶点序列$v_{m}$,$v_{1}$,$v_{2}$,$v_{3}$,……$v_{n}$，该序列中的顶点属于图中的顶点集合。两个顶点的路径并不唯一，图7展示了无向图中从顶点B到D四种不同的路径，如粗线条所示（当然还有更多）。

这里注意，对于有向图，路径也是有向的，图8展示了有向图中从顶点A到顶点D的两种不同路径。而对于B到A之间就不存在路径。

我们把第一个顶点和最后一个顶点相同的路径称为回路或环。如图9所示：

这么多的路径，其实也是涉及了一些专有名词的，我把它列在这里，你可以参考。

简单路径：在路径序列中顶点不重复出现的路径称为简单路径。图7中，从顶点A到顶点D可以有多种不同路径，比如A、B、A、D这个路径，因为顶点A重复出现了，所以这就不是一个简单路径。

简单回路/简单环：除第一个顶点和最后一个顶点，其余顶点不重复出现的回路叫简单回路或简单环。

路径长度：路径上的边或弧的数目。图7中的四幅图路径长度分别为1、2、2、3，图8中的两幅图路径长度分别为3、1。

点到点的距离：从顶点$v_{m}$到$v_{n}$的最短路径如果存在，则此路径的长度称为从顶点$v_{m}$到$v_{n}$的距离，如果$v_{m}$到$v_{n}$之间不存在路径，则称他们之间的距离为无穷（∞）。

无向图中，若从顶点$v_{m}$到$v_{n}$之间有路径存在，则称$v_{m}$和$v_{n}$是连通的。图10中，顶点F与其他顶点之间不连通，而除F外的其他顶点是彼此连通的。

有向图中，若从顶点$v_{m}$到$v_{n}$之间和从顶点$v_{n}$到$v_{m}$之间都有路径，则称这两个顶点是强连通的。图3中，顶点A和D之间就是强连通的，而顶点A和B之间就不是强连通的，因为从B到A不存在路径。

有些图的边或弧有与其相关的数字，这种与图的边或者弧相关的数字叫权（Weight）或者权值。这些权值可以表示从一个顶点到另一个顶点的距离、时间、票价等数据。这种带权的图通常称为带权图或网。如图11所示：

连通图、子图

局部的顶点、边了解完之后，我们再将视角放大，着眼于整张图。

如果无向图中任意两个顶点都是连通的，则称图为连通图，否则称为非连通图。比如前面的图1就是一个连通图。不难想象得出这么几个结论。

对于具有n个顶点的无向图，如果是连通图，则最少要有n-1条边。简单绘制一个有3个顶点的无向图，你就能得到结论。
对于具有n个顶点的无向图，如果是非连通图，则最多只能有$\frac{(n-1)(n-2)}{2}$条边。

如何推出这个结论呢？试想，含有n个顶点的无向完全图有$\frac{n(n-1)}{2}$条边，比如含有5个顶点的无向完全图有10条边，那么如果再增加进来一个顶点变成6个顶点，现在只要将这个新增加的顶点和任意其他顶点连线，就构成了连通图，所以6个顶点的非连通图最多只能有10条边。

而如果有向图中任意一对顶点都是强连通的呢？那我们称此图为强连通图，如图12所示：

不难想象，对于有n个顶点的有向图，若是强连通图，则最少要有n条边以构成回路，如图13所示：

我们假设有图一和图二两个图，如果图二的顶点是图一的顶点的子集，并且图二的边是图一边的子集，则称图二是图一的子图。如果子图包含原图的所有顶点，则称该子图为原图的一个生成子图，图14从第2个图开始的图都是第1个图的子图，而最后一个子图是原图的生成子图。

连通分量：无向图中的极大连通子图称为连通分量。换句话说，极大连通子图必须连通并且包含尽可能多的顶点和边，如图15所示：

举个例子，全国各个城市的地铁网，比如上海地铁网是全国地铁网的连通分量，深圳地铁网是全国地铁网的连通分量，诸如此类。

强连通分量：有向图中的极大强连通子图称为强连通分量。这里的强连通意味着两两可达。如图16所示：

生成树、生成森林

一个无向的连通图的生成树是包含图中全部顶点的一个极小的连通子图。这里的极小指边尽可能要少，如图17所示：

从图17可以看到，无向连通图的生成树可以有多个，生成树中如果有n个顶点，则必须有n-1条边。因为我们前面讲解过，n个顶点的无向图，如果是连通图，则最少要有n-1条边。话说回来，如果一个无向图有n个顶点和小于n-1条边，则肯定是非连通图。如果它多于n-1条边，则一定有回路（环）。但有n-1条边的图不一定是生成树，因为生成树要求连通。

你可以想象一下通往各个城市的道路铺设场景，其中就可以用到生成树。生成树既可以保证各个城市之间彼此都可以到达，又可以保证铺设的道路尽可能少，而后可以在多个生成树中挑选最优的生成树方案。比如如果想最节省成本，就可以把修每段路（边）的价格作为权值来计算总成本并最终挑选出总成本最少的修路方案如图18所示：