数据结构名词

线性表

线性表(linear list)是数据结构一种,一个线性表是n个具有想嘶特性的数据元素的有限序列.数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同

线性表中元素是一对一的关系,除了第一个和最后一个数据元素外,其他元素都是首位相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

链表和数组都是线性表

图

术语

图(graph)是由定点的有穷非空集合顶定点之间的边的集合组成,通常表示为G(V,E),其中G表示一个图,V是图中G中顶点的集合,e是图G中边的集合

在线性表中,数据元素之间是呗串起来的,仅有线性的关系,每个数据元素只有一个直接前驱和一个直接后继.在树形结构中,数据元素之间有着明显的层次关系.

在图中:节点之间的关系是可以任意的,图中任意俩个数据元素都可能相关

对于图的定义,我们有几个需要注意的地方

• 线性表中我们把数据元素叫元素,树中叫节点,在图中数据元素,我们称之为顶点
• 线性表中可以没有数据元素,称为空表,树中没有节点可以叫做空树,在图中不允许没有顶点
• 线性表中响铃元素之间有线性关系,树结构中,相邻的俩层节点具有层次关系,而图中,任意俩个顶点之间都可能有关系,顶点之间逻辑关系用边来表示,边集可以是空的

无向边

无向边:若顶点vi到vj之间的边没有方向,则称之为这条边为无向边(edge)用无序偶对Vi,Vj来表示.如果图中任意俩个顶点之间的边都是无向的,啧称该图为无向图(Undirected graphs)

有向边

有向边:弱从顶点Vi到Vj的边有方向,则 称这条边为有向边,也称为弧(Arc)

用有序偶<Vi,Vj>来表示,Vi称之为弧尾(Tail),Vj称之为弧头.如果图中任意俩个顶点之间的边都是有向边,则称该图为有向图(Directed graphs)

左边就是无向图,右边是有向图

连接顶点A到D的有向边就是弧,A是弧尾,D是弧头,<A,D>表示弧主义不能写成<D,A>

看清楚了,无向边用小括号()表示,而有向边是用<>尖括号表示

在途中,弱不存在顶点到自身的边,且同一条边不吃重复出现,这样的图为简单图,文中讨论的都是简单图

下图就不再讨论的范围中

在无向图中,如果任意俩个顶点之间都存在边,则称该图为完全无向图.

因为每个顶点都要与除它以外的顶点连线,顶点A与BCD三个顶点连线,n个顶点的完全无向图有 (n*(x-1))/2条边

在有向图中,如果任意俩个顶点之间都存在方向互为相反的俩条弧,则称该图为完全有向图

含有n个顶点的完全有向图有n(n-1)条边

有很少跳边的或弧的图称为洗漱图,反之称为稠密图.这里的稀疏和稠密都是模糊概念,都是相对的.

有些图的边或弧具有它相关的数字,这种图的边或者弧相关的数字叫做权(Weight).这些权可以表示从一个顶点到另一个顶点的距离或耗费.这种带权的图,通常称为网(network)

子图,subgraph,带底纹的图均为左侧无向图与有向图的子图

假如A和W之间存在一条边则称A和W互为邻接点

一个顶点到最后一个顶点相同的路径称为回路或环(cycle).序列中顶点不重复出现的路径称为简单路径.除了第一个节点和最后一个顶点之外,其顶点不重复出现的回路,称为简单回路或简单环

图7-2-11的粗线都构成环,左侧的环因第一个顶点和最后一个顶点都是B,切CDA没有重复出现,因此是一个简单环,而右侧的环由于顶点C的重复,它就不是简单环了

连通图

在无向图G中,如果从顶V到顶点V'有路径,则称V和V'是连通的.如果对于图中任意俩个顶点都是连通的,则称G为连通图(Connected Graph)

比如图1,顶点A到顶点BCD都是连通的,因此不能算是连通图,而图2顶点ABCD都是连通的,所以它本身是联通图

无向图的极大连通子图称为连通分量.注意连通分量的概念

• 要是子图
• 子图要是连通的
• 连通子图含有极大顶点数
• 具有极大顶点数的联通子图包含依附于这些顶点的所有边

图1是一个无向非连通图,但是他有俩个连通分量,即图2和图3,而图4尽管是图1的子图,但是它却不满足连通子图的极大顶点数(图2满足).因此它不是图1的无向图的连通分量

如果从V1,到Vj和从Vj到V都存在路径,则称G是强连通图有向图的极大强连通子图称作有向图的强连通分量

上图1并不是强连通图,因为顶点A到顶点D存在路径,而D到A就不存在,图2就是强连通图,且图2是图一的极大连通子图,即是它的强连通分量

存储结构

图的存储结构相较线性表与树来说就更加复杂了,首先我们口头上说的顶点的位置,或邻接点的位置,只是一个相对概念.从图的逻辑结构定义来看,图上任何一个顶点都可以被看成是一个顶点,任一顶点的邻接点之间也不存在次序关系.如图,仔细观察发现,它们其实是同一个图,只不过顶点的位置不同,就造成了表象上不太一样的感觉

也正是由于图的结构比较复杂,任意俩个顶点之间都可能存在联系,因此无法以数据元素在内存中物理位置标示元素之间的关系,也就是说,图不可能用简单的顺序存储结构标示.而多重链表的方式,即以一个数据域和多个指针域组成的节点标示图中的一个顶点,尽管可以实现图结构,但其实在树中,问我们也已经讨论过,这是有问题的.如果各个顶点的度数相差很大,按最大顶点设计节点结构会造成很多存储单元的浪费,而若按每个顶点自己的度数设计不同的顶点结构,又会带来操作上的不便.因此,对于图来说,如何对它实现物理存储是个难题,不过我们的前辈已经解决了,现在我们来看前辈提供的五种不同的存储结构

邻接矩阵

考虑到图是由顶点和边或者弧俩部分组成.合在一起比较困难,那就很自然的考虑到分俩个结构来分别存储.顶点不分大小主次,所以用一个一维数组来存储是很不错的选择.而边或弧由于是顶点与顶点之间的关系,一维搞不定,那就考虑用一个二维数组来存储.于是我们的邻接矩阵的方案就诞生了

图的邻接矩阵(Adjacency Matrix)存储方式是用俩个数组来表示图,一个一维数组存储图中顶点信息

顶点数组为vertex[4]={V0,V1,V2,V3}边数组arc4为右图中这样一个矩阵

简单解释一下,对于矩阵的主对角线的值,即arc[0][0],arc[1][1],arc[2][2],arc[3][3]权威0是因为不存在顶点到自身的边,比如V0到V0.

arc[0][1]=1是因为V0到V1的边存在,而arc[1][3]=0是因为V1到V3的边不存在.并且由于是无向图,V1到V3的边不存在意味着V3到V1的边也不存在.所以无向图的边数组是一个对称矩阵.(对称矩阵即:从左上角到右下角的主线为轴右上角的元与左下角对应的元都是相等的)

有了这个矩阵,我们就可以很容易知道图中的信息

1. 我们要判断任意俩顶点是否有边就非常容易了
2. 我们要知道某个顶点的度,其实就是这个顶点Vi在邻接矩阵中的第i行(或第i列)的元素之和,比如顶点V1的度就是1+0+1+0=2
3. 求顶点V1的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点

这是一个有向图

• 入度:有向图的某个顶点作为重点的次数和
• 出度:有向图的某个顶点作为起点的次数和

顶点数组为vertex[4]={v0,v1,v2,v3}弧数组arc[4][4]为图右边这样的一个矩阵.但因为是有向图,所以此矩阵并不对称,比如由V1到V0有弧,得到arc[1][0]=1

而V0到V1没有弧,因此arc[0][1]=0

有向图讲究入度与出度,顶点V1的入度为1,正好是滴V1列个数之和.顶点V1的出度为2,即第V1行的个数之和

判断俩点之间是否存在弧,只需要查找矩阵中arc[i][j]是否为1即可.要求V1的所有邻接点就是将矩阵低i行元素扫描一遍,朝招arc[i][j]为1的顶点

邻接表

邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构存在对存储空间的极大浪费,比如说,如果我们要处理图中这样的稀疏有向图,邻接矩阵除了arc[1][0]有权值外,没有其他弧,其实这些存储空间都被浪费掉了

因此我们考虑另外一种存储结构方式.回忆我们在线性表时谈到,顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题,于是引出了链式存储的结构.同样的,我们也可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题

孩子表示法:将节点存入数组,并对节点孩子进行链式存储,不管有多少孩子,也不会存在空间浪费问题.这个思路同样适用于图的存储,我们把这周数组与链表相结合的存储方法称为邻接表(Adjacency List)

处理办法

1. 用一个一维数组存储顶点,当然顶点也可以用单链表来存储,不过数组可以比较容易的读取顶点信息,更加方便.另外,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息
2. 图中每个顶点Vi的所有邻接点构成一个线性表,由于邻接点个数的不稳定,所以用单链表存储,无向图称为顶点V1的边表,有向图则称为顶点V1作为弧尾的出边表

从图中可知,顶点表的各个几点由data和firstedge俩个域表示,data是数据域存储顶点的信息firstedge是指针域,指向边表的第一个节点,即此顶点的第一个邻接点.边表节点由adjvex和next俩个组成.adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个节点的指针.比如V1顶点与V0,V2互为邻接点,则在V1的边表中,adjvex分别为V0的0和V2的2

这样的结构,对于我们要获得图的相关信息也是很方便的,比如我们想要知道某个顶点的度,就去查找这个顶点的边表中的节点个数.若要判断Vi到Vj是否存在边,只需要测试顶点Vi的边表中adjvex是否存在结点Vj的下标j就行了.若顶点的所有邻接点,其实就是对此顶点的边表进行遍历.,得到的adjvex域对应的顶点就是邻接点

若是有向图,邻接表的结构是类似的,比如图7-4-7中第一幅图的邻接表就是第二幅图.但要注意的是有向图由于有方向,我们是以顶点为弧尾来存储边表的,这样很容易就可以得到每个顶点的出度.但也有时为了便于确定顶点的入度或以顶点为弧头的弧,我们可以建立一个有向图的逆邻接表,即对每个顶点Vi都建立一个链接为Vi为弧头的表

此时我们可以很容易就可以算出某个顶点的入度或出度是多少,判断俩顶点是否存在弧也很容易实现

对于带权值的图,可以在边表节点定义中加一个weight的数据域,存储权值信息即可

在创建邻接表的边表时,可以使用头插法,减少了一次对于出边表的遍历

十字链表

那么对于有向图来说,邻接表是有缺陷的.关心了出度问题,想了解入度,就必须要遍历整个图才能知道,反之,逆邻接表解决了入度却解决不了出度的情况.有没有可能把邻接表与逆邻接表结合起来呢?答案是肯定的,就是把它们整合在一起.就是我们现在要将的有向图的一种存储方法:十字链表(Orthogonal List)

我们重新定义表结构

其中firstin表示入边表头指针,指向该节点的入边表中第一个节点,firstout表示出边表头指针,指向该顶点的出边表中的第一个节点

重新定义的边表节点的结构

其中tailvex是指弧七点在顶点表的下标,headvex是只弧终点在顶点表中的下标,headlink是入编表指针域,指向终点相同的下一条边,taillink是指边表指针域,指向七点相同的下一条边.如果是网,还可以增加一个weight来存储权值

比如图7-4-10顶点依然是粗如一个一位数组{v0,v1,v2,v3}实现箭头指针的标识与图7-4-7的邻接表相同.就以v0来说,firstout指向的出边表中的第一个节点v3.所以v0遍表节点的headvex=3,而tailvex其实就是当前v0的下标0,由于v0只有一个节点,所以headlink和taillink都是空

我们重点需要来解释虚线箭头的含义,它其实就是此图的逆邻接表的标识,对于v0来说,它又俩个顶点v1和v2的入编.因此v0的firstin指向点v1边表节点中headvex为0的节点,如图7-4-10右图中的①.接着由入编节点的headlink指向下一个入编节点v2,如图中的②对于顶点v1,他有一个入编顶点v2,所以它的firstin指向顶点v2的边表节点中headvex为1的节点如图中的③顶点v2和v3也同样有一个入边顶点,如图④和⑤

十字连表的好处就是因为把邻接表和逆邻接表整合在了一起,这样既容易找到一v1位结尾的弧,也容易找到一v1位头的弧,因而容易求得顶点的出度和入度.而且它除了结构复杂一点外,其实创建算法的时间复杂度和邻接表是相同的,因此,在有向图的应用中,十字链表是非常好的数据结构模型

邻接多重表

讲了有向图的存储结构,对于无向图的邻接表,有没有问题呢,有没有问题呢?如果我们在无向图中的应用中,关注的重点是顶点,那么邻接表是不错的选择,但如果我们关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着,需要找到这条边的俩个边节点进行操作,比如对访问过的边做标记,删除某一条边等操作,纳吉尼意味着,需要找到这条边的俩个边表节点进行操作,这其实还是比较麻烦的.比如图7-4-11弱要删除左图的(v0,v2)这条边,需要对邻接表结构中右边表的阴影俩个节点进行删除操作,显然这是比繁琐的

因此我们也仿照十字链表的方式,对边表的结构进行一些改造,也许就可以避免刚才提到的问题

其中ivex和jvex是与某条边依附的俩个顶点在顶点表中的下标,ilink指向依附顶点ivex的下一条边,jlink指向依附顶点jvex的下一条边.这就是邻接多重表结构

我们来看结构示意图绘制过程,理解了它是如何连线的,也就理解邻接多重表的构造原理了

简单理解为一个数组记录所有顶点,一个数组记录所有边

我们来看结构的绘制过程,了解它是如何理线的,也就理解邻接多重表构造原理了.如果如图所示,左图告诉我们它有4个顶点和五条边,显然,我们就应该先将四个顶点和5条边表节点画出来.由于是无向图,所以ivex是0,jvex是1还是反过来都是无所谓的,不过为了绘图方便,都将ivex值设置得与一旁的顶点下标相同

我们开始连线如图7-4-13.首先连接线的①②③④就是将顶点的firstedge指向一条边,顶点下标要与ivex值相同,这很好理解.接着由于顶点的(v0,v1)边的邻边有(v0,v3)和(v0,v2).因此⑤⑥的连线就是满足指向下一条依附于顶点v0的边的目标,注意ilink指向的节点jvex一定要和它本身的ivex值相同.同样的道理连线⑦就是指(v1,v0)这条边,它相当于是顶点v1指向(v1,v2)边后的修啊一条

v2有三条边依附,所以在③之后就有了⑧⑨.连线⑩的就是顶点v3在连线④之后的下一条边.左图一共有5条边,所以右图有10条连线完全符合预期

到这里大家应该可以明白,邻接多重表与邻接表的差别,仅仅是在于一条边在邻接表中用俩个节点表示,而在邻接多重表只有一个节点.这样对边的操作就方便多了,弱要删除(v0,v2)这条边,只需要将右图的⑥⑨的链接指向改为^即可.由于各种操作的实现方式是和邻接表是相似的,这里我们就不讲解代码了

边集数组

边集数组是由俩个一维数组构成.一个是存储顶点的信息;另一个是存储边的信息,这个边数组每个元素由一条边的起点下标(begin),终点下标(end)和权(weight)组成,

如图7-4-14所示.显然边集数组关注的是边的集合,在边集数组中要查找一个顶点的度需要扫描整个边数组,效率不高.因此它更适合对边依次进行处理的操作,而不适合对顶点相关操作.这里不在详述

定义的边数组结构如表7-4-4所示

其中begin是存储起点下标,end是存储终点下标,weight是存储权值

AOV 网拓扑排序

所谓拓扑排序,其实就是对一个有向图构造拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出,然后删去此顶点,并删除以此顶点为尾的弧,继续重复此步骤,知道输出全部顶点或者AOV网中不存在入度为0的顶点为止

首先我们需要确定一下这个图需要使用的数据结构.前面求最小生成树和最短路径时,我们使用的都是邻接矩阵,但由于拓扑排序的过程中需要删除顶点,显然用邻接表会更加方便.因此我们需要为AOV网建立一个邻接表.考虑到算法过程中始终要查找入度为0的顶点,我们在原来顶点表结构中,增加一个入度域in,结构如下

因此对于图7-8-2的第一幅图AOV网,我们可以得到如第二幅图的邻接表数据结构

在算法中还需要辅助的数据结构栈,用来处理过程中入度为0的点

AOV和AOE

aov

是一个有向无回路的图

顶点-表示活动

用弧-表示活动间的优先级关系的有向图称为-顶点表示活动的网

如果a->b 那么a是b的先决条件

求拓扑序列就是AOV

图中顶点表示活动之间的先后顺序.边没有权重,只是表示先后关系,而AOE有权重

这样的有向图叫做AOV,顶点活动网

拓步排序的输出叫做拓扑序列

aoe

是一个带权的有向无环图

• 边:表示活动
• 顶点:表示事件(event)弧表示活动
• 权表示活动的持续事件

关键路径就是OAE