图的十字链表存储构架
发布时间：2022-07-08 13:49:13 所属栏目：语言 来源：互联网
导读：前面介绍了图的邻接表存储法，本节继续讲解图的另一种链式存储结构十字链表法。 与邻接表不同，十字链表法仅适用于存储有向图和有向网。不仅如此，十字链表法还改善了邻接表计算图中顶点入度的问题。 十字链表存储有向图（网）的方式与邻接表有一些相同，都
|
前面介绍了图的邻接表存储法，本节继续讲解图的另一种链式存储结构——十字链表法。 与邻接表不同，十字链表法仅适用于存储有向图和有向网。不仅如此，十字链表法还改善了邻接表计算图中顶点入度的问题。 十字链表存储有向图（网）的方式与邻接表有一些相同，都以图（网）中各顶点为首元节点建立多条链表，同时为了便于管理，还将所有链表的首元节点存储到同一数组（或链表）中。 firstin 指针用于连接以当前顶点为弧头的其他顶点构成的链表； firstout 指针用于连接以当前顶点为弧尾的其他顶点构成的链表； data 用于存储该顶点中的数据； 由此可以看出，十字链表实质上就是为每个顶点建立两个链表，分别存储以该顶点为弧头的所有顶点和以该顶点为弧尾的所有顶点。 注意，存储图的十字链表中，各链表中首元节点与其他节点的结构并不相同，图 1 所示仅是十字链表中首元节点的结构， 十字链表中普通节点的存储分为 5 部分内容，它们各自的作用是： tailvex 用于存储以首元节点为弧尾的顶点位于数组中的位置下标； headvex 用于存储以首元节点为弧头的顶点位于数组中的位置下标； hlink 指针：用于链接下一个存储以首元节点为弧头的顶点的节点； tlink 指针：用于链接下一个存储以首元节点为弧尾的顶点的节点； info 指针：用于存储与该顶点相关的信息，例如量顶点之间的权值； 拿图 3 中的顶点 V1 来说，通过构建好的十字链表得知，以该顶点为弧头的顶点只有存储在数组中第 3 位置的 V4（因此该顶点的入度为 1），而以该顶点为弧尾的顶点有两个，分别为存储数组第 1 位置的 V2 和第 2 位置的 V3（因此该顶点的出度为 2）。 对于图 3 各个链表中节点来说，由于表示的都是该顶点的出度或者入度，因此没有先后次序之分。 （编辑：百客网 - 百科网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐