加入收藏 | 设为首页 | 会员中心 | 我要投稿 网站开发网_安阳站长网 (https://www.0372zz.com/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 编程 > 正文

图的十字链表存储构架

发布时间:2022-07-08 03:18:06 所属栏目:编程 来源:互联网
导读:前面介绍了图的邻接表存储法,本节继续讲解图的另一种链式存储结构十字链表法。 与邻接表不同,十字链表法仅适用于存储有向图和有向网。不仅如此,十字链表法还改善了邻接表计算图中顶点入度的问题。 十字链表存储有向图(网)的方式与邻接表有一些相同,
  前面介绍了图的邻接表存储法,本节继续讲解图的另一种链式存储结构——十字链表法。
 
  与邻接表不同,十字链表法仅适用于存储有向图和有向网。不仅如此,十字链表法还改善了邻接表计算图中顶点入度的问题。
 
  十字链表存储有向图(网)的方式与邻接表有一些相同,都以图(网)中各顶点为首元节点建立多条链表,同时为了便于管理,还将所有链表的首元节点存储到同一数组(或链表)中。
 
  firstin 指针用于连接以当前顶点为弧头的其他顶点构成的链表;
  firstout 指针用于连接以当前顶点为弧尾的其他顶点构成的链表;
  data 用于存储该顶点中的数据;
  由此可以看出,十字链表实质上就是为每个顶点建立两个链表,分别存储以该顶点为弧头的所有顶点和以该顶点为弧尾的所有顶点。
 
 
  注意,存储图的十字链表中,各链表中首元节点与其他节点的结构并不相同,图 1 所示仅是十字链表中首元节点的结构, 
 
   十字链表中普通节点的存储分为 5 部分内容,它们各自的作用是:
  tailvex 用于存储以首元节点为弧尾的顶点位于数组中的位置下标;
  headvex 用于存储以首元节点为弧头的顶点位于数组中的位置下标;
  hlink 指针:用于链接下一个存储以首元节点为弧头的顶点的节点;
  tlink 指针:用于链接下一个存储以首元节点为弧尾的顶点的节点;
  info 指针:用于存储与该顶点相关的信息,例如量顶点之间的权值;
 
  拿图 3 中的顶点 V1 来说,通过构建好的十字链表得知,以该顶点为弧头的顶点只有存储在数组中第 3 位置的 V4(因此该顶点的入度为 1),而以该顶点为弧尾的顶点有两个,分别为存储数组第 1 位置的 V2 和第 2 位置的 V3(因此该顶点的出度为 2)。
 
  对于图 3 各个链表中节点来说,由于表示的都是该顶点的出度或者入度,因此没有先后次序之分。

(编辑:网站开发网_安阳站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!