图的存储结构（十字链表、邻接多重表、边集数组）- 数据结构和算法58
图的存储结构（十字链表、邻接多重表、边集数组）
让编程改变世界
Change the world by program
十字链表
邻接表固然优秀，但也有不足，例如对有向图的处理上，有时候需要再建立一个逆邻接表~
那我们思考了：有没有可能把邻接表和逆邻接表结合起来呢？
答案是肯定的，这就是我们现在要谈的十字链表(Orthogonal List)
为此我们重新定义顶点表结点结构：
十字链表
接着重新定义边表结点结构：
十字链表
十字链表
十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以Vi为尾的弧，也容易找到以Vi为头的弧，因而容易求得顶点的出度和入度。
十字链表除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中，十字链表也是非常好的数据结构模型。
邻接多重表
讲了有向图的优化存储结构，对于无向图的邻接表，有没有问题呢？
如果我们在无向图的应用中，关注的重点是顶点的话，那么邻接表是不错的选择，但如果我们更关注的是边的操作，比如对已经访问过的边做标记，或者删除某一条边等操作，邻接表就显得不那么方便了。
到底有多烦？小甲鱼用图片告诉你：
若要删除(V0,V2)这条边，就需要对邻接表结构中边表的两个结点进行删除操作。
邻接多重表
因此，我们也仿照十字链表的方式，对边表结构进行改装，重新定义的边表结构如下：
其中iVex和jVex是与某条边依附的两个顶点在顶点表中的下标。iLink指向依附顶点iVex的下一条边，jLink指向依附顶点jVex的下一条边。
也就是说在邻接多重表里边，边表存放的是一条边，而不是一个顶点。
不急，马上进入No pic you say a J8!环节~
邻接多重表
边集数组
边集数组是由两个一维数组构成，一个是存储顶点的信息，另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成。
边集数组
弗洛伊德的冰山理论
冰山理论
视频下载
技术, IT技术, 数据结构和算法, 邻接表
风险提示及免责条款
市场有风险，投资需谨慎。本文不构成个人投资建议，也未考虑到个别用户特殊的投资目标、财务状况或需要。用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！
