图论——基础概念

学习引言

图论，是 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 ) = [ 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 0 ] G ( B ) = [ 0 1 1 0 0 1 0 1 0 ] G ( C ) = [ ∞ 5 8 ∞ 3 5 ∞ 2 ∞ 6 8 2 ∞ 10 4 ∞ ∞ 10 ∞ 11 3 6 4 11 ∞ ] G(A)=\begin{bmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&0\\ 1&1&0&0 \end{bmatrix}\qquad G(B)=\begin{bmatrix} 0&1&1\\ 0&0&1\\ 0&1&0 \end{bmatrix}\qquad G(C)=\begin{bmatrix} \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{bmatrix} G(A)= ​0111​1011​1100​1100​ ​G(B)= ​000​101​110​ ​G(C)= ​∞58∞3​5∞2∞6​82∞104​∞∞10∞11​36411∞​ ​

优缺点

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

以空间换时间。

数组模拟邻接表存储

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

优缺点

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

空间消耗不稳定。

边集数组优缺点

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

以时间换空间。

排序前向星优缺点

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

以时间换空间。

链式前向星优缺点

优点：空间消耗少，速度也快。
缺点：暂无。文章来源地址https://www.toymoban.com/news/detail-857580.html

到了这里，关于图论——基础概念的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！