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

图的定义

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

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

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

下图的都是图的表示

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

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

相关术语

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

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

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

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

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

邻接：是两个顶点之间的一种关系。如果图包含（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(v2) + … + ID(vn)

E = OD(v1) + OD(v2) + … + OD(vn)

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

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

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

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

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

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

图的一些常用操作:

1.    创建图;

2.    销毁图;

3.    清空图;

4.    加入边;

5.    删除边;

6.    获取权;

7.    获取结点的度;

8.    获取图的结点数;

9.    获取图的边数。

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

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

最后

以上就是冷酷舞蹈为你收集整理的数据结构之图的定义及基本术语的全部内容，希望文章能够帮你解决数据结构之图的定义及基本术语所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。