图的基本知识

图的定义和术语

图是一种比线性表和树形结构更为复杂的数据结构。在线性表中,数据元素之间存在着一对一的关系,也就是除了第一个元素之外,每个元素都只有一个前驱;除了最后一个元素之外,每个元素都只有一个后继。在树形结构中,数据元素之间存在这一对多的关系,也就是除了根节点外,每个节点都只有一个父节点,除了叶子节点外,每个节点都有若干个孩子节点。在图状结构中,数据元素之间存在着多对多的关系
图中的数据元素称为顶点。设V是顶点的有限集,VR两个顶点之间的关系的有限集。
对于VR中的任意一个有序偶对<v, w>,它表示从顶点v到顶点w的一条弧。v称为弧尾或起点,w称为弧头或终点。此时的图称为有向图。若对于任意<v, w>属于VR,必有<w, v>属于VR,也就是VR是对称的,则以无序偶对(v, w)代替有序偶对<v, w> 和 <w, v>,它表示v和w之间的一条边,此时的图称为无向图。
综上所述,图是由两部分构成的:顶点的集合、边或弧的集合。
用n表示图中顶点的数量,e表示图中边或弧的数量,则:

  • 对于无向图而言,e的取值范围是0到n×(n-1)/2,其中拥有n×(n-1)/2条边的无向图称为完全图
  • 对于有向图而言,e的取值范围是0到n×(n-1),其中拥有n×(n-1)条边的有向图称为有向完全图

有很少条边或弧的图称为稀疏图,否则称为稠密图。
边和弧也可以有一个权值,该值表示从一个顶点到另外一个顶点的距离或耗费。这种带权的图,也称为网。

对于无向图G = (V, {E}),若边(v, w) ∈ E,则称顶点v和顶点w互为邻接点,即v和w相邻接。边(v, w)依附于顶点v、顶点w,即边(v, w)和顶点v、顶点w相关联。顶点v的度是和v相关联的边的数量。
对于有向图G = (V, {A}),若弧<v, w> ∈ A,则称顶点v关联到顶点w、顶点w关联自顶点v、弧<v, w>与顶点v、顶点w相关联。以顶点v为弧尾的弧的数量就是v的出度;以顶点v为弧头的弧的数量就是v的入度;顶点v的度等于v的出度 加上 v的入度。所以在有向图中,弧的数量e = 所有顶点的入度之和 = 所有顶点的出度之和。

从一个顶点到另外一个顶点之间的路径是一个顶点序列,如果图是有向图,那么路径也是有向的。路径的长度就是路径上边或弧的数量。如果路径的第一个顶点 和 最后一个顶点 相同,那么称该路径为 回路 或 环。如果路径上所有的顶点都不相同,那么称该路径为 简单路径。如果路径上,第一个顶点和最后一个顶点相同,其余所有的顶点都不相同,那么称该路径为 简单回路 或 简单环。

对于一个无向图,如果任意两个顶点之间都有路径,则称该图为连通图。对于非连通图而言,它的一个极大连通子图,称为一个连通分量。
一个连通图的生成树是一个极小连通子图,它包含所有的顶点,但是只包含足以构成一棵树的n - 1条边。

对于一个有向图,如果任意两个顶点之间都有路径,则称该图为强连通图。有向图的极大强连通子图称为强连通分量。
如果一个有向图,只有一个顶点的入度为0,其他所有顶点的入度都为1,则称该图为有向树。一个强连通图的生成森林是由若干棵互不相交的有向树组成的,这些有向树包含图中所有的顶点,但只有足以构成这些有向树的弧。


图的存储结构

1,数组矩阵表示法
用一个数组保存顶点的集合、用一个矩阵保存边或弧及其信息(比如权重)。
2,邻接表表示法
邻接表表示法是图的一种链式存储结构。它用一个数组保存所有顶点。每个顶点是一个链表,链表的头节点包含两个域:数据域、指向第一个表节点的指针;链表的表节点包含三个域:邻接点在数组中的索引、指向下一个表节点的指针、边或弧的信息(比如权重等)。
图的表示
可以看出,对于稀疏图而言,数组矩阵表示法会浪费存储空间。

Python的有向网的实现,可以参考tim-chow的github

感谢浏览tim chow的作品!

如果您喜欢,可以分享到: 更多

如果您有任何疑问或想要与tim chow进行交流

可点此给tim chow发信

如有问题,也可在下面留言: