1.8 图

图（Graph）是一种非线性的数据结构，图在实际生活中有很多例子，比如交通运输网、地铁网络，朋友关系等都可以抽象成图结构。图G是由V（G）和E（G）两个集合组成的，记为G=（V,E），其中V（G）是顶点（vertexes）的非空有限集，E（G）是边（edges）的有限集合。

图的基本术语

顶点：图中的每个节点就是顶点。

边：图中两个顶点之间的线就叫作边。

路径：路径就是从某个顶点到另一个顶点所要经过的顶点序列。

路径长度：一条路径上经过的边的数量。

回路：一条路径的起点和终点为同一个顶点。

度：在无向图中，点的度是指与该点相连的边的数量。在有向图中，分为出度和入度，指向该点的边数称为入度；反之，则称为出度。有向图某点度的大小等于该点出度和入度之和。

1.8.1 图的分类

图的种类比较多，比如无向图、有向图、完全图、加权图等，下面我们来看一下。

1. 无向图

如果一个图结构中，所有的边都没有方向，那么这种图称为无向图，无向图类似于情侣关系，比如在情侣中A喜欢B，那么B也喜欢A。由于无向图中的边没有方向，所以在表示边的时候对两个顶点的顺序没有要求，用小括号（?,?）表示边。如图1-62所示，顶点V2和顶点V4之间的边，可以表示为（V2，V4），也可以表示为（V4，V2）。

对应的顶点集合与边集合如下：

2. 有向图

如果一个图结构中，所有的边都有方向，那么这种图称为有向图。有向图类似于“单相思”，比如A喜欢B，但B不一定喜欢A。在有向图中，与一个顶点相关联的边有出边和入边之分。由于有向图的边是有方向的，所以在表示边的时候，对两个顶点的顺序就有要求。用尖括号＜?,?＞表示边，如图1-63所示，＜V1，V3＞表示从顶点V1到顶点V3，而＜V3，V1＞表示从顶点V3到顶点V1。

对应的顶点集合与边集合如下：

3. 完全图

在完全图中任意一对顶点之间都有边相连。根据边是否有方向，完全图又可以分为无向完全图与有向完全图，在无向图中如果任意两个顶点之间都存在边，则称该图为无向完全图，同理在有向图中如果任意两个顶点之间都存在方向相反的两条边，则称该图为有向完全图，如图1-64所示。有向完全图有n∗(n-1)条边，无向完全图有n∗(n-1)/2条边。

4. 混合图

在一个图中，边既包括有方向，也包括无方向的图称为混合图。

5. 稀疏图

边很少的图称为稀疏图。

6. 稠密图

边相对比较多的图称为稠密图。

7. 子图

对于两个图G=(V,E)和G′=(V′,E′)，如果V′是V的子集并且E′也是E的子集，我们称G′是G的子图，如图1-65所示。

8. 简单图

在图中如果任意两顶点之间最多只有一条边（在有向图中为两顶点之间每个方向最多只有一条边），边集中不存在环，这样的图称为简单图。如图1-66所示，都不属于简单图。

9. 加权图

对图G的每一条边e来说，都对应于一个值v，我们把这个v称为e的权，把这样的图G称为加权图，这个v可以表示两点之间的距离、花费时间等。如果每条边没有对应的值，我们称它为非加权图，对于非加权图两点之间如果有边用1表示，如果没边可以用0表示，如图1-67所示。

10. 有向无环图

如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图，如图1-68所示。

11. 连通图

在无向图中，对于每一对顶点V1和V2有路径相连，则称此图是连通图，如图1-69所示。

12. 强连通图

在有向图中，对于任意一对顶点V1和V2都存在从V1到V2和V2到V1的路径，则称此图是强连通图。

13. 弱连通图

把有向图的所有有向边替换成无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则原图就是弱连通图。可以看到无论是强连通图，还是弱连通图，都是对于有向图来说的。

1.8.2 图的表示方式

图的表示方式常见的有三种，分别是邻接矩阵、邻接表和边集数组。邻接矩阵是表示图最直观的一种方式，可以看到各顶点之间的关系，而邻接表可以看到一个顶点指向其他顶点的数量，而边集数组就是记录每条边的起点、终点和权值的数组。

1. 邻接矩阵

邻接矩阵就是使用一个n∗n（n是图的顶点个数）的矩阵A。对于无向图来说，如果顶点i和顶点j之间相连，则把A[i][j]和A[j][i]标记为相同的值。如果是非加权图，标记为1即可，如果是加权图，标记为这条边的权值。对于有向图来说，如果是顶点i指向顶点j，只需要记录A[i][j]的值即可，如图1-70所示。

我们看到对于简单无向图来说，它的邻接矩阵是关于从左上角到右下角这条线对称的，因为在无向图中A[i][j]和A[j][i]的值是一样的。对于有向图来说，A[i][?]不为0的个数就是点i的出度个数，A[?][j]不为0的个数是点j的入度个数。

2. 邻接表

对于稠密图（边相对比较多）来说，使用邻接矩阵表示会更合适一些，如果是稀疏图（边相对比较少），使用邻接矩阵就会造成矩阵中很多元素是0，从而导致存储空间的浪费，这个时候可以考虑使用邻接表。邻接表是一种链式存储结构，对于图中的每一个顶点v都可以建一个单向链表，将顶点v相关的信息存储在表头，链表的其余节点用来存放和顶点v相连的顶点。如果是加权图，需要在链表的节点中添加权值，否则可以不加，如图1-71所示。

邻接表的特点：

•通过邻接表方便找任一顶点的所有邻接点。

•节约稀疏图的存储空间。

•方便计算无向图的度，方便计算有向图的出度。

对于有向图的入度，使用邻接表的方式就不太好算了，这时候还可以使用十字链表来表示图，图的十字链表和邻接表类似，都是使用链表的方式，不过十字链表的头节点会有两个指针，分别指向两个链表，一个是指向出度的链表，另一个是指向入度的链表，十字链表更方便查找一个顶点的出度和入度。

3. 边集数组

边集数组是使用一维数组来存储边，一维数组中每个元素由3个成员组成，分别是边的起点、终点、权值，当然也可以写成二维数组edges[m][3]，其中m是边的数量，如图1-72所示。

1.8.3 图的遍历

图的遍历方法主要有深度优先搜索（DFS）和广度（宽度）优先搜索（BFS），关于DFS和BFS我们在第9章也会介绍。

1. 深度优先搜索（DFS）

DFS的思想类似于树的前序遍历。其遍历过程可以描述为：从图中某个顶点v出发，沿着一个方向一直访问下去，当访问到这个方向上最后一个顶点（这个顶点之后没有下一个顶点了，或者和这个顶点相连的都被访问完了）的时候，往回退一步，查看和上一个顶点相连的有没有可访问的，如果有就继续重复上面的方式沿着另一个方向继续访问，如果没有可访问的，就再回到上一个顶点，重复同样的步骤，如图1-73所示。如果一个顶点被访问之后，就不能再被访问了，所以需要使用一个数组visited来记录哪些顶点被访问过。

可以看一下代码的大致结构，这里的图使用的是邻接表，假设从顶点u开始访问。

这里只是从图的一个顶点开始访问，如果要遍历整个图，需要从图的所有顶点开始，否则在有向图中有些顶点是访问不到的。我们来看一下图的访问过程，如图1-74所示，这里选择的是非加权有向图。

测试代码如下：

打印结果：0,1,3,4,2,

2. 广度优先搜索（BFS）

DFS是从一个点沿着一个方向一直走下去，而BFS是从一个点开始，先访问和它相连的，然后访问和它相连顶点的邻接点，一圈一圈往外访问，如图1-75所示。

访问图的时候需要标记哪些点被访问过，防止出现重复访问的情况，来看一下图的BFS访问过程，如图1-76所示。

结合上面的图，我们来看一下它的大致模板。

1.8.4 迪杰斯特拉（Dijkstra）算法

迪杰斯特拉（Dijkstra）算法也叫作狄克斯特拉算法，它使用类似广度优先搜索的方法解决从一个顶点到其他所有顶点的最短路径算法，它解决的是加权图（不能有负权）的最短路径问题，采用的是贪心算法的思想。解题思路是，每次选择一个没被标记且距离起始点最近的顶点，把它标记一下，然后更新和它邻接的顶点，重复上面的步骤，直到标记完所有的顶点为止。比如一个人现在在上海，老家在信阳，假设他回老家不想直接到家，只能通过南京、杭州、武汉、合肥这四个城市中的几个中转。如图1-77所示，下面是中转所需要的时间，有的坐飞机，有的开车，还有的可能会骑单车，所以边表示的是时间而不是距离，问应该怎样走，时间才会更短？

我们从起始点开始，使用一个数组dis，数组中dis[j]的值表示从顶点j到起始点的时间，刚开始的时候，起始点到自己为0，到其他顶点为无穷大，如图1-78所示。

如果想要减少从起始点到j的时间，唯一的方式就是需要寻找一个中转站k。从起始点到k的时间为dis[k]，从k到j的时间为g[k][j]，然后判断中转的总时间dis[k]+g[k][j]是否小于dis[j]，如果中转时间小于dis[j]，就更新dis[j]。如图1-77所示，从起始点到南京的时间是3小时，如果通过杭州中转，时间就会变成2小时。核心代码是下面这行。

计算过程如图1-79所示。

我们来看一下打印结果：0,1,2,4,3,7，也就是说从起始点到其他顶点的最短时间分别是1,2,4,3,7，和图中分析的完全一样。时间复杂度：O(n^2),n是顶点的个数。

1. 堆优化

我们看到代码中外面的循环是遍历顶点，里面的循环主要是查找最近的顶点，然后更新和它邻接的顶点。如果这张是稀疏图，且边特别少，再一个个查找效率明显不高，在这种情况下，可以使用最小堆来优化一下，注意使用堆优化的时候，图要使用邻接表的表示方式。每次与顶点v邻接的计算完成后，直接把它加入到堆中，下次循环的时候直接弹出堆顶元素即可，它就是离起始点最近的，时间复杂度可以降为O((n+e)logn)，其中n是顶点的个数，e是边的数量，因为出堆和入堆都会涉及堆的调整，堆调整的时间复杂度是O(logn)，大家可以尝试写一下代码。

2. 不能处理带有负权边的图

为什么通过上述的操作可以保证得到的dis值最小？因为这里的图是没有负权边的，值只能越加越大，所以这里的最小值不可能再被更新了。我们不断选择最小值进行标记，然后更新和它邻接的点，即贪心的思路，最终保证起始点到每个顶点的值都是最小的。如果有负权边，再使用Dijkstra算法就行不通了，如图1-80所示。

最后的结果是起始点到顶点3的值是8，但实际上如果选择0->1->2->3这条路径的值是7，会更小，所以有负权边并不适合Dijkstra算法。如果图是有环的，可不可以使用Dijkstra算法呢？实际上只要没有负权边，无论有环还是无环，都是可以使用Dijkstra的。

1.8.5 贝尔曼-福特（Bellman-Ford）算法

上一节我们讲到Dijkstra算法，它是求单源点的最短路径，但是不能有负权边，如果有负权边该怎么办呢？可以使用Bellman-Ford算法。Bellman-Ford算法可以解决有负权边的问题，但不能有负权回路，它也可以检测是否有负权回路问题。解题思路就是假设有一条边{begin,end,value}，如果dis[begin]+value<dis[end]，可以更新dis[end]的值为dis[begin]+value，如图1-81所示。

所以只需要枚举所有的边即可，代码如下。

如果只枚举一遍，有可能只会更新和起始点邻接的点（也就是起始点直接指向的点），与起始点没有邻接的点可能没更新。也就是说如果枚举一遍，可以更新从起始点通过一条边到达的点，如果枚举两次，可以更新从起始点通过两条边到达的点。而在一个含有n个点的图中，一个点最多只有n-1条边和起始点相连。所以只需要枚举n-1次，即可计算起始点到其他所有点的距离。Bellman-Ford算法虽然可以计算带有负权边的图，但不能计算有负权回路的图，因为在负权回路中，如果一直转圈，值就会一直变小，如图1-82所示。

如果没有负权回路，最多枚举n-1次就可计算出起始点到其他所有点的最短路径，最后枚举一遍，所有的值不会再更新。如果有负权回路，最后枚举一遍，有些值还是会更新。所以在计算完之后，还需要再枚举一遍，判断有没有负权回路，代码如下。

我们只需要看bellMan函数即可，上面的测试数据如图1-83所示，打印结果是：0,9,2,7。也就是说如果有负权边，但没有负权回路，BellMan-Ford算法也是可以计算的。

BellMan-Ford算法虽然可以计算含有负权边的图，但时间复杂度还是比较高的O(ne)，n是顶点的个数，e是边的个数。其实还可以优化一下，如果在某一次枚举的时候没有顶点被更新，再枚举下去也不会更新了，可以直接终止。

1.8.6 SPFA算法

SPFA（Shortest Path Faster Algorithm）即最短路径快速算法，实际上它是对Bellman-Ford算法使用队列的一种优化，也是求单源点最短路径的，可以有负权边，但不能有负权回路。我们再来回顾一下Bellman-Ford算法的原理，它是每次遍历所有的边，然后判断是否能松弛。如图1-84所示，假设第一步先计算<1,2>这条边，因为顶点1的值还没有更新，它到起始点的距离是无穷大，我们用它更新顶点2的值明显是更新不了的，同理如果顶点2的值没有更新，那么<2,3>这条边计算顶点3的值也是更新不了的。也就是说使用Bellman-Ford算法会出现大量的无效计算。

通过Bellman-Ford算法发现一个问题，就是在遍历<x,y>这条边的时候，如果顶点x的值没有改变，那么通过这条边计算y的值也不会改变。所以有一种解决方式就是如果某个顶点的值改变了，它不在队列中，就把它添加到队列中，因为它改变了，和它邻接的顶点才有可能改变，所以这里只需要遍历队列中的顶点即可，如图1-85所示。

我们先来看一下边的类，只有两个属性，一个是指向另一个的顶点，一个是边的权值，使用list集合存储邻接表，所以就不需要next指针了。

这里要注意有负权回路的也是不能解决的，所以最后还需要判断图是否有负权回路。判断方式比较简单，因为如果有负权回路，为了获取最小值，它会在负权回路上绕圈，在一个有n个顶点的图中，一个点到起始点最多只能有n-1条边，如果一个点入队的次数超过n-1，就说明出现了负权回路，来看一下代码。

我们仔细看一下上面的代码和Dijkstra算法的堆优化有什么区别？Dijkstra堆优化使用的是堆，每次从堆中取出一个最小值，然后更新和它邻接的点，一个点如果从堆中出来之后，它的值就已经被确定了，不可能再改变了，也不可能再入堆了，所以它只能处理没有负权的图。而SPFA算法使用的是队列，每次顶点出队之后，只要它的值被改变，还可以再次入队的。

细心的读者可能发现，使用队列每次遍历一个点相邻的顶点，这不是和图的BFS遍历一样吗。提到BFS，大家可能也会想到DFS，也就是一个点被更新之后，和它邻接的点可能会被更新，可以参考DFS的写法，当一个点被更新之后，可以沿着这个点朝一个方向一直走下去，来更新这条路径上的所有点，这里就不再过多介绍，有兴趣的读者可以试着写一下。

1.8.7 弗洛伊德（Floyd）算法

前面介绍的几个都是求单源点路径的，其中Dijkstra算法是不能解决有负权值的图。而Bellman-Ford算法和SPFA算法是可以解决有负权值，但不能有负权回路的图。这节要介绍的Floyd算法是解决多源点路径的，它可以解决图中任何两点之间的距离，图中也是可以有负权值的，但不能有负权回路。大家可能会说前面刚讲过求单源点路径的算法，如果把每个点都当作起始点计算一次，不就可以计算出任意两点之间的距离了吗，这种方式也是可以的，但我们这里要讲的是另一种解决方式——Floyd算法。

Floyd算法相比前面讲的几个求单源点的算法更简单，也更容易理解。我们来思考这样一个问题，如果知道A到B的距离是x，这个x可能是一个确定的值，也可能是无穷大，怎样才能使x的值变小呢？唯一的解决方式就是找一个中转站C，判断A到C的距离加上C到B的距离是否小于A到B的距离，如果小于，就更新A到B的值，如果不小于，A到B的值就不变，如图1-86所示。

我们只需要把所有的点作为中转站枚举一遍即可，很明显这是一道动态规划的问题，关于动态规划在第11章会进行介绍。我们定义dp[k][i][j]表示经过前k个顶点从i到j的最短距离。

•如果不经过第k个顶点中转，那么dp[k][i][j]=dp[k-1][i][j]。

•如果经过第k个顶点中转，那么dp[k][i][j]=dp[k-1][i][k]+dp[k-1][k][j]。

只需要取它们的最小值即可，也就是：

这里要注意初始条件，以及最后距离的合并，来看一下代码。

这里只需要看下面几行代码，它才是这道题的核心代码。

我们看到dp是一个三维数组，计算的时候dp[k][?][?]只和dp[k-1][?][?]有关，所以可以把它压缩成二维数组，这样代码就会更加简洁。

时间复杂度是：O(n^3)，空间复杂度是O(1)，只需要一个变量n即可，因为我们是直接在矩阵数组中计算的，如果题中要求不能在矩阵数组中修改，还需要申请一个二维数组，空间复杂度就是O(n^2)。注意这三层for循环的嵌套顺序，遍历k的时候不能放到最里面一层，因为这是通过三维数组状态压缩出来的。Floyd算法使用的是动态规划思想，更适合稠密图，也可以处理负权边，但不能处理有负权回路的图。它更容易理解，三层循环，代码比较简洁，可以计算任意两点之间的最短距离。缺点是时间复杂度比较高，不适合计算顶点比较多的图。

1.8.8 普里姆（Prim）算法

Prim算法和下一小节要讲的Kruskal算法都是实现最小生成树的一种算法，Prim是通过点来实现的，而Kruskal是通过边来实现的，这一小节先讲Prim算法。对于一个有n个顶点的无向图，如果只需要使用n-1条边，即可把图中的所有点连接起来，那么这n个顶点和这n-1条边构成的图就是生成树，如图1-87所示。

一张图的所有生成树中权值总和最少的就是最小生成树。Prim算法就是求最小生成树的，它使用的是贪心算法。解题思路是需要把图中的点分成两部分，一部分是已经选择的，我们用集合S记录，一部分是还没选择的，我们用集合T记录。刚开始的时候集合S为空，集合T中包含图中的所有顶点，如图1-88所示，步骤如下。

（1）第一步从集合T中任选一个顶点v，把顶点v放到集合S中。

（2）更新集合T中和v相邻的顶点值。

（3）继续从集合T中选择离集合S最近的顶点v，把它加入到集合S中，更新集合T中和v相邻的顶点值。

（4）一直重复下去，直到集合T为空。

1.8.9 克鲁斯卡尔（Kruskal）算法

Kruskal算法也是求最小生成树的，它是通过选择边来实现的，它的实现原理是，首先需要对图中的边根据大小排序，然后每次选择一个最小的边，但要保证选的时候不能构成环路，一直选择下去，直到不能选择为止。判断能不能构成环路可以使用并查集，就是判断边的两个点是否在一个连通分量，如果在一个连通分量，这条边就不能选，否则可以选，如图1-89所示。

实现步骤如图1-90所示。

来看一下代码，代码会涉及并查集的知识，如果不熟悉也没有关系，只需要知道find这个方法可以判断是否是同一连通分量即可，关于并查集的知识，我们在第12章并查集中会进行介绍。

看一下运行结果：

和上面的图中分析得差不多，因为权值相同的时候先选择哪个都是一样的。

1.8.10 博鲁夫卡（Boruvka）算法

Boruvka算法是最小生成树最古老的一种算法，最早可以追溯到1926年，当时用于构建高效电力网络。它的实现原理就是刚开始的时候把每一个顶点看作是一个连通分量，接着计算与每个连通分量距离最短的连通分量，然后把它们连接起来。如果还有没连通的连通分量，继续计算离它们最近的连通分量，继续连接，直到都连通为止，如图1-91所示。

如图1-92所示，离顶点1最近的顶点除了顶点0还有顶点2，连通的时候不能重复连接，比如连接了（0,1），就不能再连接（1,0）。连接之后只剩下两个连通分量，我们找到它们之间最短的边连接起来即可。

来看一下打印结果：

打印顺序和图中分析的完全一样。

总结：无论是求单源点路径还是多源点路径，图中都不能有负权回路，因为负权回路每绕一圈，距离就会变小，如果有负权回路，永远没有最小值，我们来对上面几种算法做一个简单的总结。

Dijkstra：求单源点路径，不能有负权值。

Bellman-Ford：求单源点路径，可以有负权值，但不能有负权回路。

SPFA：是使用队列对Bellman-Ford算法的一种优化，可以有负权值，但不能有负权回路。

Floyd：求多源点路径，可以有负权值，但不能有负权回路。

Prim：通过查找最近的点，计算最小生成树。

Kruskal：通过查找最小的边，计算最小生成树。

Boruvka：通过不停合并连通分量，计算最小生成树。

1.8.11 拓扑排序

拓扑排序就是在一个有向无环图中，对图的顶点进行排序，排序的条件是对于任意一条有向边<v1,v2>，排序的结果中顶点v1一定在顶点v2的前面。如图1-93所示，对于<起床，刷牙>这条边排序的结果中，起床一定在刷牙之前。

拓扑排序的思路就是首先从图中选择入度为0的顶点，把它加入到队列中，然后逐步输出队列中的元素v，其中v指向的顶点入度要减1，如果减1之后入度为0，也要加入到队列中。重复这个步骤直到没有入度为0的顶点为止。其实也很好理解，入度为0，说明在它前面没有顶点了，我们直接输出就行，如果入度不为0，说明在它前面还有顶点，需要先输出它前面的顶点才能输出它，如图1-94所示。