十字链表

Miracle 2017年9月10日20:57:16IT相关十字链表已关闭评论1,39511720字阅读5分44秒阅读模式

转自网页文章源自联网快讯-https://x1995.cn/1312.html

对于有向图来说,邻接表是有缺陷的,关心了出度问题,想了解入度就必须要遍历整个图才能知道,反之,逆邻接表解决了入度的情况。文章源自联网快讯-https://x1995.cn/1312.html

把邻接表与逆邻接表结合起来,即有向图的一种存储方法十字链表(Orthogonal   List)。文章源自联网快讯-https://x1995.cn/1312.html

我们重新定义顶点表结构文章源自联网快讯-https://x1995.cn/1312.html

十字链表文章源自联网快讯-https://x1995.cn/1312.html

firstin表示入边表头指针,指向该顶点的入边表中第一个结点;文章源自联网快讯-https://x1995.cn/1312.html

firstout表示出边表头指针,指向该顶点的出边表中第一个结点;文章源自联网快讯-https://x1995.cn/1312.html

重新定义了边表结点结构文章源自联网快讯-https://x1995.cn/1312.html

十字链表文章源自联网快讯-https://x1995.cn/1312.html

其中文章源自联网快讯-https://x1995.cn/1312.html

tailvex是指弧起点在顶点的下标,文章源自联网快讯-https://x1995.cn/1312.html

headvex是指弧终点在顶点表中的下标,文章源自联网快讯-https://x1995.cn/1312.html

headlink是指入边表指针域,指向终点相同的一下条边文章源自联网快讯-https://x1995.cn/1312.html

taillink是指出边表指针域,指向起点相同的下一条边。文章源自联网快讯-https://x1995.cn/1312.html

如果是网,还可以再增加一个weight域来存储权值。文章源自联网快讯-https://x1995.cn/1312.html

 文章源自联网快讯-https://x1995.cn/1312.html

如图文章源自联网快讯-https://x1995.cn/1312.html

十字链表文章源自联网快讯-https://x1995.cn/1312.html

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

我们重点需要来解释虚线箭头的含义,它其实就是此图的逆邻接表的表示。对于v0来说,它有两个顶点v1和v2的入边。因此v0的firstin指向顶点v1的边表结点中headvex为0的结点①。接着由入边结点的headlink指向下一个入边顶点v2,如图②文章源自联网快讯-https://x1995.cn/1312.html

对于顶点v1,它有一个入边顶点v2,所以它的firstin指向顶点v2的边表结点中headvex为1的结点,如图中的③。文章源自联网快讯-https://x1995.cn/1312.html

firstin 指向headvex相同的,用的是headlink文章源自联网快讯-https://x1995.cn/1312.html

firstout指向tailvex相同的,用的是taillink文章源自联网快讯-https://x1995.cn/1312.html

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

邻接多重表

对于无向图的边操作,如下图要删除(v0,v2)这条边要做文章源自联网快讯-https://x1995.cn/1312.html

十字链表文章源自联网快讯-https://x1995.cn/1312.html

需要对邻接表结构中右边表的阴影两个结点进行删除操作,显然比较烦琐文章源自联网快讯-https://x1995.cn/1312.html

因此,我们也仿照十字链表的方式对边表结构进行一些改造,也许就可避免刚才的问题。文章源自联网快讯-https://x1995.cn/1312.html

重新定义边表结构:文章源自联网快讯-https://x1995.cn/1312.html

十字链表文章源自联网快讯-https://x1995.cn/1312.html

其中ivex和jvex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下条边,jlink指向依附顶点的下一条边。这就是邻接多重表结构文章源自联网快讯-https://x1995.cn/1312.html

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

十字链表文章源自联网快讯-https://x1995.cn/1312.html

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

十字链表文章源自联网快讯-https://x1995.cn/1312.html

连线⑦就是指(v1,v0)这条边,它是相当于顶点v1指向(v1,v2)边后的下一条。v2有三条边依附,所以在v3之后就有⑧⑨。连线⑩的就是顶点v3在连线④之后的下条边。文章源自联网快讯-https://x1995.cn/1312.html

邻接多重表与邻接表的差别,仅仅是在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。这样对边的操作就方便多了,若要删除左图的(v0,v2)这条边,只要右图的⑥⑨的链接指向改为^即可。文章源自联网快讯-https://x1995.cn/1312.html

边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边信息,这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成。文章源自联网快讯-https://x1995.cn/1312.html

在边集数组中要查找一个顶点的度需要扫描整个数组,效率并不高。因此它更适合对边依次时行处理的操作,而不适合对顶点相关的操作。回会学习一种克鲁斯卡尔算法。文章源自联网快讯-https://x1995.cn/1312.html

十字链表文章源自联网快讯-https://x1995.cn/1312.html

 文章源自联网快讯-https://x1995.cn/1312.html

数据结构如下文章源自联网快讯-https://x1995.cn/1312.html

十字链表文章源自联网快讯-https://x1995.cn/1312.html

继续阅读
Miracle
  • 本文由 发表于 2017年9月10日20:57:16