十字链表

2017年9月10日20:57:16十字链表已关闭评论 463

转自网页

对于有向图来说,邻接表是有缺陷的,关心了出度问题,想了解入度就必须要遍历整个图才能知道,反之,逆邻接表解决了入度的情况。

把邻接表与逆邻接表结合起来,即有向图的一种存储方法十字链表(Orthogonal   List)。

我们重新定义顶点表结构

十字链表

firstin表示入边表头指针,指向该顶点的入边表中第一个结点;

firstout表示出边表头指针,指向该顶点的出边表中第一个结点;

重新定义了边表结点结构

十字链表

其中

tailvex是指弧起点在顶点的下标,

headvex是指弧终点在顶点表中的下标,

headlink是指入边表指针域,指向终点相同的一下条边

taillink是指出边表指针域,指向起点相同的下一条边。

如果是网,还可以再增加一个weight域来存储权值。

 

如图

十字链表

顶点依然是存入一个一维数组{v0,v1,v2,v3},实线箭头指针的图标完全与前面提到的邻接表相同。就以顶点v0来说,firstout指向的是出边表中的第一个结点v3。所以v0边表结点的headvex=3,而tailvex其实就是当前顶点v0的下标0,由于v0只有一个出边顶点,所以headlink和taillink都是空的。

我们重点需要来解释虚线箭头的含义,它其实就是此图的逆邻接表的表示。对于v0来说,它有两个顶点v1和v2的入边。因此v0的firstin指向顶点v1的边表结点中headvex为0的结点①。接着由入边结点的headlink指向下一个入边顶点v2,如图②

对于顶点v1,它有一个入边顶点v2,所以它的firstin指向顶点v2的边表结点中headvex为1的结点,如图中的③。

firstin 指向headvex相同的,用的是headlink

firstout指向tailvex相同的,用的是taillink

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

邻接多重表

对于无向图的边操作,如下图要删除(v0,v2)这条边要做

十字链表

需要对邻接表结构中右边表的阴影两个结点进行删除操作,显然比较烦琐

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

重新定义边表结构:

十字链表

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

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

十字链表

首先连线①②③④就是将顶点的firstedge指向一条边,顶点下标要与ivex的值相同,这很好理解,接着,由于顶点v0的(v0,v1)的邻边有(v0,v3)和(v0,v2)。因此⑤⑥的连线就是满足指向下一条依附于顶点v0的边的目标,注意ilink指向的结点的jvex一定要和它本身的ivex值相同。同样道理

十字链表

连线⑦就是指(v1,v0)这条边,它是相当于顶点v1指向(v1,v2)边后的下一条。v2有三条边依附,所以在v3之后就有⑧⑨。连线⑩的就是顶点v3在连线④之后的下条边。

邻接多重表与邻接表的差别,仅仅是在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。这样对边的操作就方便多了,若要删除左图的(v0,v2)这条边,只要右图的⑥⑨的链接指向改为^即可。

边集数组

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

在边集数组中要查找一个顶点的度需要扫描整个数组,效率并不高。因此它更适合对边依次时行处理的操作,而不适合对顶点相关的操作。回会学习一种克鲁斯卡尔算法。

十字链表

 

数据结构如下

十字链表