十三、数据结构基础——图

本章主要介绍图的存储方法、图的遍历方式、无向图的连通分量分解问题、拓扑排序、最短路径问题、最小生成树。

图的相关概念

简单路径：路径上所有顶点都是互异的，但是第一个和最后一个顶点可以相同也可以不同。

有向图的环：第一个和最后一个顶点相同且长至少为1的路径。

简单环：是简单路径的环。

无环图：没有环的有向图或无向图。

有向无环图简称为DAG（Directed Acyclic Graph）。

连通图：无向图中从每一个顶点到每个其他顶点都存在一条路径，称其为连通图。

强连通图：有向图中从每一个顶点到每个其他顶点都存在一条路径，称其为强连通图。

图的存储方法

①邻接矩阵

邻接矩阵用一个二维数组G来表示图，对无权图，若边(u,v)存在，则G[u][v]=true，否则G[u][v]=false。对于有权图，若存在边(u,v)且边(v,w)上的权值为w，则G[u][v]=w，否则G[u][v]=∞（实际编码中∞可以用图中不可能出现的权值来表示）。其缺点是空间需求太大，若为稀疏图会浪费大量空间。因此只有当图中顶点数量在10³数量级及以下时，才适合使用邻接矩阵。

②邻接表

对每个顶点，使用一个表来存放该顶点所有相邻的顶点，通常用vector来实现这样的表，此时的空间复杂度就会降低到O(|E|+|V|)。

对于无权图，由于只需要存储顶点所有相邻的顶点编号，因此邻接表内的元素类型可以直接定义为int类型，则整个图可以定义为：vector<vector<int>>graph(MAX);

若需要存储边权或其他信息，可以定义一个新的edge类存放这些信息，并把邻接表内的元素类型定义为edge类型：

那么需要添加边时，如向graph中添加权值为6的边(2,3)，代码可以这样写：

一般情况下都会使用邻接表存储图。

图的遍历

分为深度优先遍历（DFS）和广度优先遍历（BFS）。

①深度优先遍历DFS

图的深度优先类似于树的深度优先遍历，但需要注意图中可能是有环的，因此需要一个访问数组记录顶点是否被访问，以免顶点重复访问。

②广度优先遍历BFS

和树的广度优先遍历一样，图的BFS也需要一个队列。同样，因为可能有环，所以也需要一个访问数组记录是否入过队列，以免顶点重复入队，即重复访问。

无向图的连通分量分解问题

若无向图是不连通的，那么这个图一定可以分解为多个连通子图，称这些连通子图为原图的连通分量。分解无向图的连通分量，通常有两种方法：深度（广度）优先遍历和并查集。 

※ 在该问题中DFS更容易实现也更常用；并查集的实现方法则更为直观、便于编写代码。

拓扑排序

拓扑排序的算法是每次找出任意一个入度为0的顶点，将该顶点加入拓扑序列中，并将它及其边一起从图中删除，重复这一操作，直至所有顶点都被加入拓扑序列中。若剩余的顶点入度均不为0，则说明此时这些顶点间形成了环。因此，拓扑排序还可以用于判断图中是否有环。

最短路径问题

最短路径问题可以分为单源最短路径问题和每对顶点间最短路径问题。

对不同的图的最短路径问题的求解算法如图13.1：

①BFS算法（针对无权图的单源最短路径算法）

无权图中没有边权，因此路径长度即为路径上边的数量，也可以认为所有边的边权为1。则出发点到达其他顶点的最短路径长度恰好是该顶点所处的层号。

②Dijkstra算法（针对正权图的单源最短路径算法）

是典型的贪心算法。该算法常用一个dis数组记录从源点到所有顶点的最短路径长度。

最小生成树

在无向连通图中找到n-1条边，使得无向图仍保持连通。若使得边的权值最小的生成树就是最小生成树。求解最小生成树的算法一般有2种：Prim算法和Kruskal算法。 此处只介绍Kruskal算法，因为其思想和代码实现都较为简单。Kruskal算法中需要使用并查集，初始状态下，Kruskal算法不考虑所有的边，每个顶点自成一个集合。

它的执行步骤是：1）先将所有的边权从小到大排序；2）遍历所有的边，假设当前访问的两个端点为u和v，如果u和v没有在一个集合中，就将该边作为最小生成树的一条边，并将u和v所在的集合合并成一个集合；如果u和v本身就在同一个集合，则忽略这条边。若执行算法时，发现最小生成树的边少于n-1条，说明原图不连通。