十字链表

Miracle 2017年9月10日20:57:16IT相关评论1,29011720字阅读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
欧盟隐私法即将生效,谷歌努力缓解担忧 IT相关

欧盟隐私法即将生效,谷歌努力缓解担忧

谷歌周四举行会议,希望缓解在线内容发布商对即将生效的欧洲数据隐私新规的担忧。 本周五生效的欧盟《通用数据保护条例》(GDPR)是欧洲20多年来对数据隐私法规最大的一次调整。根据这项新规,相关组织必须对...
科学家暗示外星生命隐藏在平行宇宙中 IT相关

科学家暗示外星生命隐藏在平行宇宙中

据国外媒体报道,假如在我们所处的宇宙中找不到外星生命,不妨将目光投向其它宇宙。由英国皇家天文学会开展的新研究指出,平行宇宙中很可能存在拥有外星生命的星球,尽管暗能量足以使这些宇宙分崩离析。 平行宇宙理...
关于微信与抖音摩擦的一点看法 IT相关

关于微信与抖音摩擦的一点看法

头条的崛起也是一路薅着微博、朋友圈的羊毛,当它们发现并想封杀时,轻舟己过万重山。抖音的极速爆发微信起着至关重要传播裂变的作用,现在想封杀已经来不及了,抖音的装弱碰瓷更像是一场挑衅,有人依稀记得3Q大战...
Google-ch:一场谷歌搜索“重返中国”的乌龙 IT相关

Google-ch:一场谷歌搜索“重返中国”的乌龙

一个名为Google-CH的网站在微博上引起了关注。这个域名为www.google-ch.com的网站不仅可以很方便的打开,而且搜索结果也与Google搜索一致。一时间,甚至有人认为这是Google在...

发表评论