十字链表

对于有向图来收，邻接表是有缺陷的，关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却解决不了出度的情况。十字链表的出现就是为了解决这个问题，把邻接表和逆邻接表结合起来
十字链表是有向图邻接表的优化存储结构

定义

结构定义如下：

tailvex是指弧起点在顶点表的下标
headvex是指弧重点在顶点表中的下标
headlink是指入边表指针域
taillink是指出边表指针域

图示

十字链表如图所示：

每个顶点表后面接的都是它们各自的出边表
我们重点解释虚线箭头的含义，它其实就是此图的逆邻接表的表示。对于V₀来说，它有两个顶点V₁和V₂的入边。因此V₀的入边表指针firstin指向顶点V₁的边表节点中弧终点下标headvex为0的结点，接着由入边结点的入边表指针headlink指向下一个入边顶点V₂。其余的就不解释了，可以按照刚才我所说的一一推导。
十字链表的好处就是因为把邻接表和逆邻接表整合在一起，相信掌握了邻接表和逆邻接表，就一定能够掌握好十字链表。

进阶多重表

进阶多重表是无向图邻接表的优化存储结构

定义

边表结点定义如下：

ivex和jvex是与某条边依附的两个顶点在顶点表中的下标
ilink指向依附顶点ivex的下一条边
jlink指向依附顶点jvex的下一条边

图示

邻接多重表：

左图告诉我们它有4个顶点和5条边，显然我们先将4个顶点和5条边的边表结点画出来，为了绘图方便，都将ivex值设置得与一旁得顶点下标相同。
然后我们开始连线，首先连线的①②③④就是将顶点的firstedge指向一条边，顶点下标与ivex的值相同。接着，由于顶点V₀的（V₀，V₁）边的临边有（V₀，V₃）和（V₀，V₂），因此⑤⑥的连线就是满足指向下一条依附于顶点V₀的边的目标。
在整个连线过程中，遵循一个重要原则：ilink指向的结点jvex一定要和它本身的ivex的值相同，因为是依附于同一个结点的不同边。

左图一共有5条边，所以右图中有10条连线。
到这里，邻接多重表和邻接表的取别，仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只用一个结点，这样操作就方便很多。
比如删除左图的（V₀，V₂）这条边，只需要将右图的⑥⑨的指针改为空指针即可。

边集数组

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

显然边集数组更关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点的相关操作。
这里就不多讲解边集数组，之后会由详细介绍。