图论——基础概念

学习引言

图论，是 C++ 里面很重要的一种算法，今天，就让我们一起来了解一下图论吧！

如果对您有帮助，就点个赞吧！

什么是图

其实很简单，把点用边连起来就可以算是图。

从严格意义上来讲，图是一种数据结构，定义为：graph=(V,E)。其中，V 是一个非空有限集合，代表顶点（结点），E 代表边的集合。

图的一些定义和概念

• 有向图：图的边有方向，只能严格遵循箭头方向从一个点到达另一个点。例如下方就是一个有向图：
• 无向图：图的边有方向，可以双向行走。例如下方就是一个无向图：
• 结点的度：仅存在在无向图中。无向图中与一个结点相连的边的个数叫做这个结点的度。
• 结点的入度：仅存在在有向图中。有向图中以一个结点为终点的边的个数叫做这个结点的入度。
• 结点的出度：仅存在在有向图中。有向图中以一个结点起点的边的个数叫做这个结点的出度。
• 权值：边的“费用”，可以理解为边的长度。
• 连通：如果图中存在一条从结点 $U$ 到结点 $V$ 的道路，则称 $U$ 和 $V$ 是连通的。
• 回路：起点和终点为同一结点的路径叫做回路，或称为“环”。
• 完全图：一个有 $n$ 个结点的有向图有 $n\times (n-1)$ 条边或一个有 $n$ 个结点的无向图有 $\frac{n\times (n-1)}{2}$ 条边。
• 稠密图：一个边数接近完全图的图。
• 稠密图：一个边数远远少于完全图的图。
• 强连通分量：有向图中任意两点都连通的最大子图。下图中的 $1$，$2$，$5$ 结点就构成一个强连通分量。特殊的，单个点也算一个强连通分量。所以下图中有 $3$ 个强连通分量：$1-2-5$，$3$，$4$。

图的存储方式

这里只讲解最常见的邻接表和邻接矩阵。

二维数组邻接矩阵存储

定义 int 类型数组：G[100][100]（注：数组大小随结点的个数变化）。

$G_{i,j}$ 的值表示从点 $i$ 到点 $j$ 的权值，定义如下：
$$G_{i,j}=\{\begin{array}{ll}1\text{或权值}& v_i\text{与}{v}_j\text{之间有边或弧}\\ 0\text{或}\infty & v_i\text{与}{v}_j\text{之间无边且无弧}\end{array}$$
上面的 $3$ 个图对应的邻接矩阵分别如下：
$$G(A)=\left[\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 0& 0\\ 1& 1& 0& 0\end{array}\right]G(B)=\left[\begin{array}{ccc}0& 1& 1\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]G(C)=\left[\begin{array}{ccccc}\infty & 5& 8& \infty & 3\\ 5& \infty & 2& \infty & 6\\ 8& 2& \infty & 10& 4\\ \infty & \infty & 10& \infty & 11\\ 3& 6& 4& 11& \infty \end{array}\right]$$

优缺点

优点：实现简单，使用方便，且容易获取每个结点的度（有向图是入度和出度），特别是有向图的出度，有手就会。
缺点：对于节点多，边数少的图来说，邻接矩阵存储很浪费空间。

以空间换时间。

数组模拟邻接表存储

图的邻接表存储法，又叫链式存储法。本来是采用链表实现的，但大多情况下只要用数组模拟即可。

优缺点

优点：随机数据下空间相对较小。
缺点：极限数据浪费空间大。

空间消耗不稳定。

边集数组优缺点

优点：更加的节约空间。
缺点：搜索时需要把所有的边枚举一遍，太浪费时间。

以时间换空间。

排序前向星优缺点

优点：更加的节约空间。
缺点：排序时间大。

以时间换空间。

链式前向星优缺点

优点：空间消耗少，速度也快。
缺点：暂无。