图的存储结构——十字链表的理解

7.2.4十字链表 Orthogonal List

同无向图类似，有向图也有另外一种链式存储结构称为十字链表。
根据应用的需要，对于有向图有时既需要用邻接表，又需要用逆邻接表，这时可以把两个表合二为一，用有向图的邻接多重表（通常称为十字链表）表示。

十字链表的存储结构

十字链表的顶点结点结构

对有向图中的每一个顶点也用一个顶点结点表示，它由三个域组成，其中：
data域存储有关顶点的信息：firstinarc域是链接指针，指向第一条以该顶点为终点的弧；
firstoutarc域也是链接指针，指向第一条以该顶点为始点的弧。
所有的顶点结点组成一个顺序表。

十字链表的弧结点结构

在有向图的十字链表中，图中的每一条弧用一个弧结点表示。
弧结点的结构与无向图邻接多重表中的边结点结构类似，也有六个域。
其中：
tag是标记域，标记该弧是否被处理或被搜索过；
weight为弧的信息域，用于存储弧的权值等信息；
tailvex和headvex是分别表示弧尾顶点序号和弧头顶点序号的顶点域；
tailnextarc域是链接指针，指向下一条以顶点tailvex为始点（弧尾）的弧；
headnextarc也是链接指针，指向下一条以顶点headvex为终点（弧头）的弧。

十字链表的存储结构

在有向图的十字链表中，从顶点结点中的firstoutarc域出发，由弧结点中的tailnextarc域链接起来的链表，正好是原来的邻接表结构。统计该链表中弧结点的个数，可求得该顶点的出度。若从顶点结点的 firstoutarc域出发，由弧结点中的headnextarc域链接起来的链表，正好是原来的逆邻接表结构。统计该链表中弧结点的个数，可求得该顶点的入度。

其 实现 可以参考：
https://blog.csdn.net/majiakun1/article/details/88692940