数据结构之图的定义及基本术语

深藏阁楼爱情的钟 2022-05-31 13:43 532阅读 0赞

**图的定义**

图是由顶点集合(Vertex)及顶点间的关系集合组成的一种数据结构：Graph＝( V, E )  
V = \{x | x ∈某个数据对象 \} 是顶点的有穷非空集合；  
E =\{ (x, y) | x, y ∈V \} 是顶点之间关系的有穷集合，也叫做边(Edge)集合。

注：∈为数学符号，表示属于的意思 。例：x∈y：表示x属于y的意思。

在图中的数据元素通常称为**顶点 V 。**

下图的都是图的表示

![70][]

可能有人会提出异议，G2和G3怎么会是图，明明就是二叉树和线性表嘛。不错，你们说的是对的，但是根据图的定义我们不难发现，二叉树和线性表也符合图的特征。大家来看，二叉树的所有结点是不是相当于顶点的集合，结点间都存在一定的关系；线性表也是一样，也就是说二叉树和线性表是特殊的图。只不过图比线性表和树更加复杂罢了。

在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中的一个元素相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

**相关术语**

**无向边：**若顶点 x 和 y 之间的边没有方向，则称该边为无向边(x, y)，(x, y) 与 (y,x) 意义相同，表示 x 和 y 之间有连接。

**无向图：**若图中任意两个顶点之间的边均是无向边，则称该图为无向图（如上图G1，G2）。

**有向边：**若顶点 x 和 y 之间的边有方向，则称该边为有向边<x, y>，<x, y> 与 <y, x> 意义不同，表示从 x 连接到 y，x 称为尾，y 称为头。

**有向图：**若图中任意两个顶点之间的边均是有向边，则称该图为有向图（如上图G3，G4）。

在图中的两个重要关系是**邻接**和**关联。**

**邻接：**是两个顶点之间的一种关系。如果图包含（u,v），则称顶点v与顶点u邻接。在无向图中，这也暗示了顶点u也与顶点v邻接。换句话说，在无向图中邻接关系是对称的。

**关联：**是指顶点和边之间的关系。在有向图中，边（u,v）从顶点u开始关联到v，或者相反，从顶点v开始关联到u。在无向图中，边(u,v)与顶点u和v相关联。

**完全图：**每个顶点都与其他顶点相邻接的图。

**度(Degree)的定义**：顶点 v 的度是和 v 相关联的边的数目，记为TD(v)。  
**入度：**以 v 为头的边的数目，记为ID(v)  
**出度：**以 v 为尾的边的数目，记为OD(v)  
很显然：TD(v) = ID(v) + OD(v)  
E = \[TD(v1) + TD(v2) + … + TD(vn)\] / 2  
E = ID(**v1**) + ID(v**2**) + … + ID(v**n**)

E = OD(v**1**) + OD(v**2**) + … + OD(v**n**)

**权(Weight)的定义**：与图的边相关的数字叫做权，权常用来表示图中顶点间的距离或者耗费。带权的图通常称为网。

![70 1][]

**路径：**依次遍历顶点序列之间的边所形成的轨迹。没有重复顶点的路径称为**简单路径**。路径的长度是路径上的边或弧的数目。

**环**是指路径包含相同的顶点两次或两次以上。也就是说，在有向图的一条路径中，如果从某顶点出发，最后能够返回该顶点，则该路径是**环**。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为**简单环**或**简单回路**。

**连通性**是图中另一个重要的概念。对于无向图而言，如果它的每个顶点都能通过某条路径到达其他顶点，那么我们称它为**联通的**。如果该条件在有向图中同样成立，则称该图是**强连通**。尽管无向图可能不是连通的，但它扔然可能包含连通的部分，这部分分支为**连通分支**。如果有向图中只有部分是强连通的，则该部分称为**强连通分支**。

某些特定的顶点对于保护图或连通分支的连通性有特殊的重要意义。如果移除某个顶点将使得图或某分支失去连通性，则称该顶点为**关结点**。

前面讲了这么多图的相关术语，都是为了后面如何实现图和操作图做准备的。当然，本节不讲图的实现与操作，不过会将有关图的相关操作列举出来，下节实现所有的操作功能。

**图的一些常用操作**:

1. 创建图;

2. 销毁图;

3. 清空图;

4. 加入边;

5. 删除边;

6. 获取权;

7. 获取结点的度;

8. 获取图的结点数;

9. 获取图的边数。

图的操作在程序中的表现为一组函数 ，如下所示：

![70 2][]

小结：图是一种扩展的树结构，每个结点可以指向任意的其它结点。链表是特殊的树结构，树是特殊的图结构。图这种数据结构常用于网络规划和路径路径规划等领域。GPS相关产品中大量应用了图结构和图算法。

**路径：**依次遍历顶点序列之间的边所形成的轨迹。没有重复顶点的路径称为**简单路径**。路径的长度是路径上的边或弧的数目。

[70]: /images/20220531/27e6040025484b11a7a514db61319f26.png
[70 1]: /images/20220531/ad72addb3d88421993894b17b059e889.png
[70 2]: /images/20220531/6bfef7f0de0649619535e021cabc78da.png