图-十字链表，邻接多重表，边集数组

邻接表固然优秀，但也有不足，例如对有向图的处理中，有时候需要再建立一个逆邻接表。我们思考

有没有可能把邻接表和 逆邻接表结合起来呢？  答案是肯定的，这就是我们现在要谈的十字链表。为此我们 重新定义 了顶点表的结构;

重新定义边表的结点结构：

 

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

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

 

邻接多重表

 

有向图的优化存储结构，对于无向图的邻接表，有没有问题呢？

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

如果要删除（V0，V2）这条边，就需要对邻接表结构中的边表的两个结点进行删除操作。

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

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

的下一条边。

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

 

边集数组

边集数组是由两个一维数组构成，一个是存储顶点的信息，另一个 是存储边的信息

，这个边数组每个数据元素由一条边的起点下标，终点下标和权组 成。