下载掌阅APP，畅读海量书库
立即打开
图（Graph）是一种非线性的数据结构，图在实际生活中有很多例子，比如交通运输网、地铁网络，朋友关系等都可以抽象成图结构。图G是由V（G）和E（G）两个集合组成的，记为G=（V,E），其中V（G）是顶点（vertexes）的非空有限集，E（G）是边（edges）的有限集合。
顶点： 图中的每个节点就是顶点。
边： 图中两个顶点之间的线就叫作边。
路径： 路径就是从某个顶点到另一个顶点所要经过的顶点序列。
路径长度： 一条路径上经过的边的数量。
回路： 一条路径的起点和终点为同一个顶点。
度： 在无向图中，点的度是指与该点相连的边的数量。在有向图中，分为 出度 和 入度 ，指向该点的边数称为入度；反之，则称为出度。有向图某点度的大小等于该点出度和入度之和。
图的种类比较多，比如无向图、有向图、完全图、加权图等，下面我们来看一下。
如果一个图结构中，所有的边都没有方向，那么这种图称为无向图，无向图类似于情侣关系，比如在情侣中A喜欢B，那么B也喜欢A。由于无向图中的边没有方向，所以在表示边的时候对两个顶点的顺序没有要求，用小括号（?,?）表示边。如图1-62所示，顶点V2和顶点V4之间的边，可以表示为（V2，V4），也可以表示为（V4，V2）。
•图1-62
对应的顶点集合与边集合如下：
如果一个图结构中，所有的边都有方向，那么这种图称为有向图。有向图类似于“单相思”，比如A喜欢B，但B不一定喜欢A。在有向图中，与一个顶点相关联的边有出边和入边之分。由于有向图的边是有方向的，所以在表示边的时候，对两个顶点的顺序就有要求。用尖括号＜?,?＞表示边，如图1-63所示，＜V1，V3＞表示从顶点V1到顶点V3，而＜V3，V1＞表示从顶点V3到顶点V1。
•图1-63
对应的顶点集合与边集合如下：
在完全图中任意一对顶点之间都有边相连。根据边是否有方向，完全图又可以分为无向完全图与有向完全图，在无向图中如果任意两个顶点之间都存在边，则称该图为无向完全图，同理在有向图中如果任意两个顶点之间都存在方向相反的两条边，则称该图为有向完全图，如图1-64所示。有向完全图有n*(n-1)条边，无向完全图有n*(n-1)/2条边。
•图1-64
在一个图中，边既包括有方向，也包括无方向的图称为混合图。
边很少的图称为稀疏图。
边相对比较多的图称为稠密图。
对于两个图G=(V,E)和G′=(V′,E′)，如果V′是V的子集并且E′也是E的子集，我们称G′是G的子图，如图1-65所示。
•图1-65
在图中如果任意两顶点之间最多只有一条边（在有向图中为两顶点之间每个方向最多只有一条边），边集中不存在环，这样的图称为简单图。如图1-66所示，都不属于简单图。
•图1-66
对图G的每一条边e来说，都对应于一个值v，我们把这个v称为e的权，把这样的图G称为加权图，这个v可以表示两点之间的距离、花费时间等。如果每条边没有对应的值，我们称它为非加权图，对于非加权图两点之间如果有边用1表示，如果没边可以用0表示，如图1-67所示。
•图1-67
如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图，如图1-68所示。
•图1-68
在无向图中，对于每一对顶点V1和V2有路径相连，则称此图是连通图，如图1-69所示。
•图1-69
在有向图中，对于任意一对顶点V1和V2都存在从V1到V2和V2到V1的路径，则称此图是强连通图。
把有向图的所有有向边替换成无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则原图就是弱连通图。可以看到无论是强连通图，还是弱连通图，都是对于有向图来说的。
图的表示方式常见的有三种，分别是邻接矩阵、邻接表和边集数组。邻接矩阵是表示图最直观的一种方式，可以看到各顶点之间的关系，而邻接表可以看到一个顶点指向其他顶点的数量，而边集数组就是记录每条边的起点、终点和权值的数组。
邻接矩阵就是使用一个n*n（n是图的顶点个数）的矩阵A。对于无向图来说，如果顶点i和顶点j之间相连，则把A[i][j]和A[j][i]标记为相同的值。如果是非加权图，标记为1即可，如果是加权图，标记为这条边的权值。对于有向图来说，如果是顶点i指向顶点j，只需要记录A[i][j]的值即可，如图1-70所示。
•图1-70
我们看到对于简单无向图来说，它的邻接矩阵是关于从左上角到右下角这条线对称的，因为在无向图中A[i][j]和A[j][i]的值是一样的。对于有向图来说，A[i][?]不为0的个数就是点i的出度个数，A[?][j]不为0的个数是点j的入度个数。
对于稠密图（边相对比较多）来说，使用邻接矩阵表示会更合适一些，如果是稀疏图（边相对比较少），使用邻接矩阵就会造成矩阵中很多元素是0，从而导致存储空间的浪费，这个时候可以考虑使用邻接表。邻接表是一种链式存储结构，对于图中的每一个顶点v都可以建一个单向链表，将顶点v相关的信息存储在表头，链表的其余节点用来存放和顶点v相连的顶点。如果是加权图，需要在链表的节点中添加权值，否则可以不加，如图1-71所示。
•图1-71
邻接表的特点：
•通过邻接表方便找任一顶点的所有邻接点。
•节约稀疏图的存储空间。
•方便计算无向图的度，方便计算有向图的出度。
对于有向图的入度，使用邻接表的方式就不太好算了，这时候还可以使用十字链表来表示图，图的十字链表和邻接表类似，都是使用链表的方式，不过十字链表的头节点会有两个指针，分别指向两个链表，一个是指向出度的链表，另一个是指向入度的链表，十字链表更方便查找一个顶点的出度和入度。
边集数组是使用一维数组来存储边，一维数组中每个元素由3个成员组成，分别是边的起点、终点、权值，当然也可以写成二维数组edges[m][3]，其中m是边的数量，如图1-72所示。
•图1-72
图的遍历方法主要有深度优先搜索（DFS）和广度（宽度）优先搜索（BFS），关于DFS和BFS我们在第9章也会介绍。
DFS的思想类似于树的前序遍历。其遍历过程可以描述为：从图中某个顶点v出发，沿着一个方向一直访问下去，当访问到这个方向上最后一个顶点（这个顶点之后没有下一个顶点了，或者和这个顶点相连的都被访问完了）的时候，往回退一步，查看和上一个顶点相连的有没有可访问的，如果有就继续重复上面的方式沿着另一个方向继续访问，如果没有可访问的，就再回到上一个顶点，重复同样的步骤，如图1-73所示。如果一个顶点被访问之后，就不能再被访问了，所以需要使用一个数组visited来记录哪些顶点被访问过。
•图1-73
可以看一下代码的大致结构，这里的图使用的是邻接表，假设从顶点u开始访问。
这里只是从图的一个顶点开始访问，如果要遍历整个图，需要从图的所有顶点开始，否则在有向图中有些顶点是访问不到的。我们来看一下图的访问过程，如图1-74所示，这里选择的是非加权有向图。
•图1-74
测试代码如下：
打印结果：0,1,3,4,2,
DFS是从一个点沿着一个方向一直走下去，而BFS是从一个点开始，先访问和它相连的，然后访问和它相连顶点的邻接点，一圈一圈往外访问，如图1-75所示。
•图1-75
访问图的时候需要标记哪些点被访问过，防止出现重复访问的情况，来看一下图的BFS访问过程，如图1-76所示。
•图1-76
结合上面的图，我们来看一下它的大致模板。
迪杰斯特拉（Dijkstra）算法也叫作狄克斯特拉算法，它使用类似广度优先搜索的方法解决 从一个顶点到其他所有顶点的最短路径算法 ，它解决的是加权图（不能有负权）的最短路径问题，采用的是贪心算法的思想。解题思路是，每次选择一个没被标记且距离起始点最近的顶点，把它标记一下，然后更新和它邻接的顶点，重复上面的步骤，直到标记完所有的顶点为止。比如一个人现在在上海，老家在信阳，假设他回老家不想直接到家，只能通过南京、杭州、武汉、合肥这四个城市中的几个中转。如图1-77所示，下面是中转所需要的时间，有的坐飞机，有的开车，还有的可能会骑单车，所以边表示的是时间而不是距离，问应该怎样走，时间才会更短？
•图1-77
我们从起始点开始，使用一个数组dis，数组中dis[j]的值表示从顶点j到起始点的时间，刚开始的时候，起始点到自己为0，到其他顶点为无穷大，如图1-78所示。
•图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所示。
•图1-79
我们来看一下打印结果：0,1,2,4,3,7，也就是说从起始点到其他顶点的最短时间分别是1,2,4,3,7，和图中分析的完全一样。时间复杂度：O(n^2),n是顶点的个数。
我们看到代码中外面的循环是遍历顶点，里面的循环主要是查找最近的顶点，然后更新和它邻接的顶点。如果这张是稀疏图，且边特别少，再一个个查找效率明显不高，在这种情况下，可以使用最小堆来优化一下，注意使用堆优化的时候，图要使用 邻接表 的表示方式。每次与顶点v邻接的计算完成后，直接把它加入到堆中，下次循环的时候直接弹出堆顶元素即可，它就是离起始点最近的，时间复杂度可以降为O((n+e)logn)，其中n是顶点的个数，e是边的数量，因为出堆和入堆都会涉及堆的调整，堆调整的时间复杂度是O(logn)，大家可以尝试写一下代码。
为什么通过上述的操作可以保证得到的dis值最小？因为这里的图是没有负权边的，值只能越加越大，所以这里的最小值不可能再被更新了。我们不断选择最小值进行标记，然后更新和它邻接的点，即贪心的思路，最终保证起始点到每个顶点的值都是最小的。如果有负权边，再使用Dijkstra算法就行不通了，如图1-80所示。
•图1-80
最后的结果是起始点到顶点3的值是8，但实际上如果选择0->1->2->3这条路径的值是7，会更小，所以有负权边并不适合Dijkstra算法。如果图是有环的，可不可以使用Dijkstra算法呢？实际上只要没有负权边，无论有环还是无环，都是可以使用Dijkstra的。
上一节我们讲到Dijkstra算法，它是求单源点的最短路径，但是不能有负权边，如果有负权边该怎么办呢？可以使用Bellman-Ford算法。Bellman-Ford算法可以解决有负权边的问题，但不能有负权回路，它也可以检测是否有负权回路问题。解题思路就是假设有一条边{begin,end,value}，如果dis[begin]+value<dis[end]，可以更新dis[end]的值为dis[begin]+value，如图1-81所示。
•图1-81
所以只需要枚举所有的边即可，代码如下。
如果只枚举一遍，有可能只会更新和起始点邻接的点（也就是起始点直接指向的点），与起始点没有邻接的点可能没更新。也就是说如果枚举一遍，可以更新从起始点通过一条边到达的点，如果枚举两次，可以更新从起始点通过两条边到达的点。而在一个含有n个点的图中，一个点最多只有n-1条边和起始点相连。所以只需要枚举n-1次，即可计算起始点到其他所有点的距离。Bellman-Ford算法虽然可以计算带有负权边的图，但不能计算有负权回路的图，因为在负权回路中，如果一直转圈，值就会一直变小，如图1-82所示。
•图1-82
如果没有负权回路，最多枚举n-1次就可计算出起始点到其他所有点的最短路径，最后枚举一遍，所有的值不会再更新。如果有负权回路，最后枚举一遍，有些值还是会更新。所以在计算完之后，还需要再枚举一遍，判断有没有负权回路，代码如下。
我们只需要看bellMan函数即可，上面的测试数据如图1-83所示，打印结果是：0,9,2,7。也就是说如果有负权边，但没有负权回路，BellMan-Ford算法也是可以计算的。
•图1-83
BellMan-Ford算法虽然可以计算含有负权边的图，但时间复杂度还是比较高的O(ne)，n是顶点的个数，e是边的个数。其实还可以优化一下，如果在某一次枚举的时候没有顶点被更新，再枚举下去也不会更新了，可以直接终止。
SPFA（Shortest Path Faster Algorithm）即最短路径快速算法，实际上它是对Bellman-Ford算法使用队列的一种优化，也是求单源点最短路径的，可以有负权边，但不能有负权回路。我们再来回顾一下Bellman-Ford算法的原理，它是每次遍历所有的边，然后判断是否能松弛。如图1-84所示，假设第一步先计算<1,2>这条边，因为顶点1的值还没有更新，它到起始点的距离是无穷大，我们用它更新顶点2的值明显是更新不了的，同理如果顶点2的值没有更新，那么<2,3>这条边计算顶点3的值也是更新不了的。也就是说使用Bellman-Ford算法会出现大量的无效计算。
•图1-84
通过Bellman-Ford算法发现一个问题，就是在遍历<x,y>这条边的时候，如果顶点x的值没有改变，那么通过这条边计算y的值也不会改变。所以有一种解决方式就是如果某个顶点的值改变了，它不在队列中，就把它添加到队列中，因为它改变了，和它邻接的顶点才有可能改变，所以这里只需要遍历队列中的顶点即可，如图1-85所示。
我们先来看一下边的类，只有两个属性，一个是指向另一个的顶点，一个是边的权值，使用list集合存储邻接表，所以就不需要next指针了。
•图1-85
这里要注意有负权回路的也是不能解决的，所以最后还需要判断图是否有负权回路。判断方式比较简单，因为如果有负权回路，为了获取最小值，它会在负权回路上绕圈，在一个有n个顶点的图中，一个点到起始点最多只能有n-1条边，如果一个点入队的次数超过n-1，就说明出现了负权回路，来看一下代码。
我们仔细看一下上面的代码和Dijkstra算法的堆优化有什么区别？Dijkstra堆优化使用的是堆，每次从堆中取出一个最小值，然后更新和它邻接的点，一个点如果从堆中出来之后，它的值就已经被确定了，不可能再改变了，也不可能再入堆了，所以它只能处理没有负权的图。而SPFA算法使用的是队列，每次顶点出队之后，只要它的值被改变，还可以再次入队的。
细心的读者可能发现，使用队列每次遍历一个点相邻的顶点，这不是和图的BFS遍历一样吗。提到BFS，大家可能也会想到DFS，也就是一个点被更新之后，和它邻接的点可能会被更新，可以参考DFS的写法，当一个点被更新之后，可以沿着这个点朝一个方向一直走下去，来更新这条路径上的所有点，这里就不再过多介绍，有兴趣的读者可以试着写一下。
前面介绍的几个都是求单源点路径的，其中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的最短距离。
•图1-86
•如果不经过第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算法使用的是动态规划思想，更适合稠密图，也可以处理负权边，但不能处理有负权回路的图。它更容易理解，三层循环，代码比较简洁，可以计算任意两点之间的最短距离。缺点是时间复杂度比较高，不适合计算顶点比较多的图。
Prim算法和下一小节要讲的Kruskal算法都是实现最小生成树的一种算法，Prim是通过点来实现的，而Kruskal是通过边来实现的，这一小节先讲Prim算法。对于一个有n个顶点的无向图，如果只需要使用n-1条边，即可把图中的所有点连接起来，那么这n个顶点和这n-1条边构成的图就是生成树，如图1-87所示。
•图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-88
Kruskal算法也是求最小生成树的，它是通过选择边来实现的，它的实现原理是，首先需要对图中的边根据大小排序，然后每次选择一个最小的边，但要保证选的时候不能构成环路，一直选择下去，直到不能选择为止。判断能不能构成环路可以使用并查集，就是判断边的两个点是否在一个连通分量，如果在一个连通分量，这条边就不能选，否则可以选，如图1-89所示。
•图1-89
实现步骤如图1-90所示。
来看一下代码，代码会涉及并查集的知识，如果不熟悉也没有关系，只需要知道find这个方法可以判断是否是同一连通分量即可，关于并查集的知识，我们在第12章并查集中会进行介绍。
•图1-90
看一下运行结果：
和上面的图中分析得差不多，因为权值相同的时候先选择哪个都是一样的。
Boruvka算法是最小生成树最古老的一种算法，最早可以追溯到1926年，当时用于构建高效电力网络。它的实现原理就是刚开始的时候把每一个顶点看作是一个连通分量，接着计算与每个连通分量距离最短的连通分量，然后把它们连接起来。如果还有没连通的连通分量，继续计算离它们最近的连通分量，继续连接，直到都连通为止，如图1-91所示。
•图1-91
如图1-92所示，离顶点1最近的顶点除了顶点0还有顶点2，连通的时候不能重复连接，比如连接了（0,1），就不能再连接（1,0）。连接之后只剩下两个连通分量，我们找到它们之间最短的边连接起来即可。
•图1-92
来看一下打印结果：
打印顺序和图中分析的完全一样。
总结： 无论是求单源点路径还是多源点路径，图中都不能有负权回路，因为负权回路每绕一圈，距离就会变小，如果有负权回路，永远没有最小值，我们来对上面几种算法做一个简单的总结。
Dijkstra：求单源点路径，不能有负权值。
Bellman-Ford：求单源点路径，可以有负权值，但不能有负权回路。
SPFA：是使用队列对Bellman-Ford算法的一种优化，可以有负权值，但不能有负权回路。
Floyd：求多源点路径，可以有负权值，但不能有负权回路。
Prim：通过查找最近的点，计算最小生成树。
Kruskal：通过查找最小的边，计算最小生成树。
Boruvka：通过不停合并连通分量，计算最小生成树。
拓扑排序就是在一个有向无环图中，对图的顶点进行排序，排序的条件是对于任意一条有向边<v1,v2>，排序的结果中顶点v1一定在顶点v2的前面。如图1-93所示，对于<起床，刷牙>这条边排序的结果中，起床一定在刷牙之前。
•图1-93
拓扑排序的思路就是首先从图中选择入度为0的顶点，把它加入到队列中，然后逐步输出队列中的元素v，其中v指向的顶点入度要减1，如果减1之后入度为0，也要加入到队列中。重复这个步骤直到没有入度为0的顶点为止。其实也很好理解，入度为0，说明在它前面没有顶点了，我们直接输出就行，如果入度不为0，说明在它前面还有顶点，需要先输出它前面的顶点才能输出它，如图1-94所示。
•图1-94
