图是什么?(数据结构中的图)

图,一个简单而又复杂的模型,在计算机科学中起到很大的作用。图往往可以作为生活中复杂联系的简化结构,一种抽象的数学对象,从而使计算机能够高效地处理分析图中蕴藏的有效信息。

应用图往往能解决“最近”“最远”“能否到达”“不能到达”“能到达哪”等问题。图的很多算法是解决许多重要的实际问题的基础。

图论作为数学领域中的一个重要分支已经有数百年的历史了。人们发现了图的许多重要而实用的性质,发明了许多重要的算法,许多困难问题的研究仍然十分活跃。

图的几种分类

1) 无向图

无向图是图的一个分支,在无向图的模型中,图中的边仅仅是两个顶点之间的连接,而并没有方向的属性。为了和其他图模型相区别,我们将它称为无向图。

作为最简单的图模型,无向图的定义是:

由一组顶点和一组能够将两个顶点相连而没有方向的边组成的图。

与数学上图的定义有稍许差别,因为这里定义的图不一定是闭合的,所以所有图上的点都可以被视为顶点。

就定义而言,顶点叫什么名字并不重要,但我们需要一个方法来指代这些顶点。一般使用 1 至 V 来表示一张含有 V 个顶点的图中的各个顶点。这样约定是因为无论对于数组还是列表索引而言,能都更高效地访问各个顶点中的信息,如图 1 和图 2 所示。
数学中的图和顶点
图 1:数学中的图和顶点

基本无向图和顶点
图 2:基本无向图和顶点

在绘制一幅图时,往往用圆圈表示顶点,用线段表示连接两个顶点的边,这样就能直观地看出图的结构。

但值得注意的是,因为图的定义不会影响绘制出来的图像,所以同一幅图,绘制出的图像可能会有不同。因此,分析图的结构时,不能只看绘制出来的图像,而要观察顶点和边的联系。图 3 和图 4 就是一个例子。
相同图结构的第1种形状
图 3:相同图结构的第 1 种形状

相同图结构的第2种形状
图 4:相同图结构的第 2 种形状

图 3 和图 4 的形状很不同,却其实是一幅图。其实,只要我们合理地把一幅图存储后,我就不再关注其绘制出来的形状了,而是用算法直接分析图的各类性质。、

2) 二分图

如果一个图能将所有顶点分为两个分离的顶点集合,其中图的每条边所连接的两个顶点都分别属于不同的集合中,则其是一个二分图。二分图的两个顶点集合中的每一个顶点都和相同集合中的顶点不相连接。如图 5 和图 6 所示。
二分图
图 5:二分图

二分图结构示意图
图 6:二分图结构示意图

图 5 所示为一个二分图,图 6 则是图 5 二分后的形式(其中每一个集合中均没有边相互连接)。二分图往往会讨论其最大匹配问题,之后会涉及。

3) 无环图

无环图是指一种不包含环的图。

和图有关的术语

除顶点和边外,仍有很多与无向图有关的术语。

1) 邻接点

当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,也可以说这两个顶点互为邻接点,并称这条边依附于这两个顶点,与这两个顶点相关联。

2) 度

对于无向图而言,顶点 V 的度是指与 V 相关联的边的个数。换句话说,度数等于依附于它的边的总数。在有向图中,度有入度和出度之分,入度是指方向指向某顶点 V 的所有与顶点 V 相关联的边的数量,出度是指从顶点 V 出发的所有与顶点 V 相关联的边的数量。以之前的无向图为例,每一个顶点的度数如图 7 所示。
无向图的度数
图 7:无向图的度数

3) 子图

子图是指在一幅图中所有边的一个子集以及它们所依附的所有顶点组成的图,如图 8 所示。
无向图的子图
图 8:无向图的子图

4) 路径和环

路径是由边顺序连接的一系列顶点的集合,简单路径则是一条没有重复顶点的路径。环是一条至少含有一条边且起点和终点相同的路径。简单环是一个没有重复顶点和边的环(除起点和终点重复外)。路径或者环的长度都等于其所包含的边的长度。

通常情况下,问题所涉及的都是简单环和简单路径,所以往往我们会省略掉简单二字,只提到“环”和“路径”。当两个顶点之间存在一条连接双方的路径时,我们称一个顶点和另一个顶点是连通的。

5) 权和网

在实际应用中,图上的边往往是有权值的,这些权重具有一定的意义,例如代表边的长度、距离、花费等信息。而我们将每条边都带有权值的图称为“网”。

6) 图的密度

图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例。在稀疏图中,已连接的顶点对很少;而在稠密图中,基本所有顶点之间都有边相连接。一般来说,如果一幅图中不同的边的数量在顶点总数为 V 的一个小的常数倍以内,那么我们就认为这幅图是稀疏的,否则是稠密的。

有时我们也会以 V lgV 为分界线来区分稀疏图和稠密图,但实际应用中稀疏图和稠密图之间的区别是十分明显的。当前阶段我们分析的几乎都是稀疏图。