图论——基础概念

---

学习引言

图论，是 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 = { 1  或权值 v i  与  v j  之间有边或弧 0  或  ∞ v i  与  v j  之间无边且无弧 G_{i,j}=

Gi,j​={1 或权值0 或 ∞​vi​ 与 vj​ 之间有边或弧vi​ 与 vj​ 之间无边且无弧​
上面的 $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)=

[0111101111001100]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢0111101111001100⎤⎦⎥⎥⎥$$\left[\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 0& 0\\ 1& 1& 0& 0\end{array}\right]$$

\qquad G(B)=

[011001010]" role="presentation" style="position: relative;">⎡⎣⎢000101110⎤⎦⎥$$\left[\begin{array}{ccc}0& 1& 1\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]$$

\qquad G(C)=

[∞58∞35∞2∞682∞104∞∞10∞1136411∞]" role="presentation" style="position: relative;">⎡⎣⎢⎢⎢⎢⎢⎢∞58∞35∞2∞682∞104∞∞10∞1136411∞⎤⎦⎥⎥⎥⎥⎥⎥$$\left[\begin{array}{ccccc}\mathrm{\infty }& 5& 8& \mathrm{\infty }& 3\\ 5& \mathrm{\infty }& 2& \mathrm{\infty }& 6\\ 8& 2& \mathrm{\infty }& 10& 4\\ \mathrm{\infty }& \mathrm{\infty }& 10& \mathrm{\infty }& 11\\ 3& 6& 4& 11& \mathrm{\infty }\end{array}\right]$$

G(A)= ​0111​1011​1100​1100​ ​G(B)= ​000​101​110​ ​G(C)= ​∞58∞3​5∞2∞6​82∞104​∞∞10∞11​36411∞​ ​

优缺点

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

以空间换时间。

数组模拟邻接表存储

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

优缺点

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

空间消耗不稳定。

边集数组优缺点

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

以时间换空间。

排序前向星优缺点

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

以时间换空间。

链式前向星优缺点

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