邻接多重

邻接多重表(Adjacency Multilist)主要用于存储无向图。因为，如果用邻接表存储无向图，每条边的两个边结点分别在以该边所依附的两个顶点为头结点的链表中，这给图的某些操作带来不便。例如，对已访问过的边做标记，或者要删除图中某一条边等，都需要找到表示同一条边的两个结点。因此，在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。

邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如图所示。

其中，顶点表由两个域组成，vertex 域存储和该顶点相关的信息firstedge 域指示第一条依附于该顶点的边；边表结点由六个域组成，mark 为标记域，可用以标记该条边是否被搜索过；ivex 和jvex 为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点ivex的边;jlink 指向下一条依附于顶点jvex 的边，info 为指向和边相关的各种信息的指针域。

例如，上图所示为无向图的邻接多重表。在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。可见，对无向图而言，其邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。因此，除了在边结点中增加一个标志域外，邻接多重表所需的存储量和邻接表相同。在邻接多重表上，各种基本操作的实现亦和邻接表相似。

十字链表

对于有向图来说，邻接表是有缺陷的，关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度的情况。

把邻接表与逆邻接表结合起来，即有向图的一种存储方法十字链表(Orthogonal   List)。

我们重新定义顶点表结构

firstin表示入边表头指针，指向该顶点的入边表中第一个结点；

firstout表示出边表头指针，指向该顶点的出边表中第一个结点；

重新定义了边表结点结构

其中

tailvex是指弧起点在顶点的下标，

headvex是指弧终点在顶点表中的下标，

headlink是指入边表指针域，指向终点相同的一下条边

taillink是指出边表指针域，指向起点相同的下一条边。

如果是网，还可以再增加一个weight域来存储权值。

如图对于这样的一个有向图，构建如下的十字链表

对于十字链表的一些认识：

1.表头结点即顶点结点，与邻接表一样是顺序存储。

2.对于每个顶点结点之后是与之相关联的弧结点（该弧结点中存有弧头、弧尾），而邻接表则是一些与顶点结点相连接的点。

3.从每个顶点结点开始有两条链表，一条是以该顶点结点为弧头的链表，一条是以该顶点结点为弧尾的链表。

4.对于其中的每一条链表必然是从顶点结点开始，直到与之相关的弧结点链域headlink和taillink为空是结束，构成一条完整的链表。

十字链表存储结构：

typedef struct ArcBox   // 弧的结构表示
{
    int tailvex, headvex;
    InfoType  *info;
    struct ArcBo...

掌握本节内容