现在的位置: 首页 > 综合 > 正文

图的存储结构-邻接多重表、边集数组

2018年03月21日 ⁄ 综合 ⁄ 共 532字 ⁄ 字号 评论关闭

图的存储结构:

 

如果我们在无向图的应用中,关注的重点是顶点的话,那么邻接表是不错的选择,但是我们关注的是边的操作,比如对已经访问过的边做标记,或者删除某一条边等操作,邻接表就显得不那么方便了。

 

图解:

若要删除(v0,v2)这条边,就需要对邻接表结构中边表的两个节点进行删除操作。

相对操作比较麻烦!

 

因此,也仿照十字链表的方式,对边表结构进行改装,重新定义的边表结构如下:

iVex

iLink

jVex

jLink

 

其中iVex和jVex是与某条边依附的两个顶点的顶点下标。iLink指向依附顶点iVex的下一条边,jLink指向依附顶点jVex的下一条边。

也就是说在邻接多重表里边,这表存放的是一条边,而不是一个顶点。

 

 

上图遵循:iVex和jVex是与某条边依附的两个顶点的顶点下标。iLink指向依附顶点iVex的下一条边,jLink指向依附顶点jVex的下一条边,而形成。

 

 

边集数组:

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

 

图解:

顶点数组

V0

 V1

V2

V3

 

边数组

Begin

End

Weight

0

0

3

5

1

1

0

4

2

1

2

3

3

2

0

8

 

抱歉!评论已关闭.