数据结构--5.1图的存储结构（十字链表、邻接多重表、边集数组）-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构--5.1图的存储结构（十字链表、邻接多重表、边集数组）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、十字链表（Orthogonal List）

二、邻接多重表

三、边集数组

四、深度优先遍历

一、十字链表（Orthogonal List）

重新定义顶点表结点结构：

data

firstIn

firstOut

重新定义边表结构结点：

tailVex

headVex

headLink

tailLink

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到Vi为尾的弧，也容易找到以Vi为头的弧，因而容易求得顶点的出度和入度。

十字链表除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中，十字链表也是非常好的数据结构模型。

我们可以仿照十字链表的方式，对边表结构进行改装，重新定义的边表结构如下：

iVex

iLink

jVex

jLink

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

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

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

深度优先遍历（DepthFirstSearch），也有称为深度优先搜索，简称为DFS。文章来源地址https://www.toymoban.com/news/detail-687090.html

到了这里，关于数据结构--5.1图的存储结构（十字链表、邻接多重表、边集数组）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！