从今儿起,我就正儿八经地开始更新学习算法的一些心得惹,图论主要参考的是张新华老师的《算法竞赛宝典》。到时候离散数学学到这里以后,我再进行补充吧。现在只能拿着张老师的书照本宣科。

以下绝对是新手友好系列。因为我自己就是一个菜鸡QAQ,走到哪里都是全队最菜。我检讨。

入门内容包括图的基本概念、图的存储结构(邻接数组、邻接表)、深度优先法、广度优先法。

图论入门

图的基本概念

图是一种非线性结构,由顶点的有穷非空集合和顶点之间边的集合组成。数据元素之间是多对多的关系,即网状结构关系。

图可以分为有向图和无向图两类。

无向图:任意两个顶点之间的边都是无向边(简而言之就是没有方向的边);

有向图:任意两个顶点之间的边都是有向边(简而言之就是有方向的边)。

需要注意的是,无论是有向图还是无向图,都需要遵循两点限制:

  1. 图形不允许自身循环(每个顶点不能构成自环)
  2. 任意两顶点之间的边数不能超过1,即边不能重复

以下是图论中一些基本名词概念解释:

  • 完全图:无向图的任意两顶点之间都存在边(有向图为任意两顶点之间都存在双向边)
  • 路径:在图中由一顶点A到另一顶点B经过的所有边。路径长度为经过的边数。
  • 简单路径:路径上的各顶点(除起点、终点)均不互相重复。
  • 回路:路径上的第一个顶点与最后一个顶点重合的简单路径。下图回路有(A,B,C,D,E,A)等等。

  • 连通顶点:无向图中两个存在一条路径的顶点。

  • 连通图:无向图中任意两个顶点皆连通。
  • 强连通顶点:有向图中两个存在双向边的顶点。
  • 强连通图形:有向图中任意两个顶点皆存在双向边。
  • 度:有向图中,内分支度是指其他顶点前往此顶点的边数,外分支度是指此顶点前往其他顶点的边数。
  • 权:有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权。

图的存储结构

邻接数组

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

  • 无向图

    我们可以设置两个数组,顶点数组为vertex[4]={v0,v1,v2,v3},边数组arc[4][4]为上图右边这样的一个矩阵。对于矩阵的主对角线的值,即arc[0][0]、arc[1][1]、arc[2][2]、arc[3][3],全为0是因为不存在顶点的边。
  • 有向图
    我们再来看一个有向图样例,如下图所示的左边。顶点数组为vertex[4]={v0,v1,v2,v3},弧数组arc[4][4]为下图右边这样的一个矩阵。主对角线上数值依然为0。但因为是有向图,所以此矩阵并不对称,比如由v1到v0有弧,得到arc[1][0]=1,而v到v没有弧,因此arc[0][1]=0。

    邻接表

    由于存在n个顶点的图需要n*n个数组元素进行存储,当图为稀疏图时,使用邻接矩阵存储方法将会出现大量0元素,这会造成极大的空间浪费。这时,可以考虑使用邻接表表示法来存储图中的数据。

邻接表由表头节点和表节点两部分组成,图中每个顶点均对应一个存储在数组中的表头节点。如果这个表头节点所对应的顶点存在邻接节点,则把邻接节点依次存放于表头节点所指向的单向链表中。

  • 无向图


从上图中我们知道,顶点表的各个结点由data和firstedge两个域表示,data是数据域,存储顶点的信息,firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个结点的指针。例如:v1顶点与v0、v2互为邻接点,则在v1的边表中,adjvex分别为v0的0和v2的2。

对于无向图来说,使用邻接表进行存储也会出现数据冗余的现象。例如上图中,顶点V0所指向的链表中存在一个指向顶点V3的同事,顶点V3所指向的链表中也会存在一个指向V0的顶点。

  • 有向图

若是有向图,邻接表结构是类似的,但要注意的是有向图由于有方向的。因此,有向图的邻接表分为出边表和入边表(又称逆邻接表),出边表的表节点存放的是从表头节点出发的有向边所指的尾节点;入边表的表节点存放的则是指向表头节点的某个顶点,如下图所示。

  • 带权图

对于带权值的网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可,如下图所示。

深度优先法

广度优先法

留坑,待填……

最后更新: 2019年03月30日 18:55

原始链接: http://yisin.top/2019/03/29/图论入门/

× 请我吃糖~
打赏二维码