7.2.3 有向图(网)的十字链表存储表示

　　十字链表是有向图的另一种存储结构，目的是将在有向图的邻接表和逆邻接表中两次出现的同一条弧用一个结点表示，由于在邻接表和逆邻接表中的顶点数据是相同的，则在十字链表中只需要出现一次，但需保留分别指向第一条"出弧"和第一条"入弧"的指针。例如有向图G1的十字链表如下所示（忽略与弧相关的信息指针）。动画

　

算法 有向图的十字链表存储表示
　　const MAX_VERTEX_NUM = 20;

　　typedef struct ArcBox { 　　　// 弧结点结构定义
　　　int tailvex, headvex; 　　　　// 该弧的尾和头顶点的位置
　　　struct ArcBox *hlink, *tlink; // 分别为弧头相同和弧尾相同的弧的链域
　　　VRType weight;　　　　　　　　// 与弧相关的权值，无权则为0
　　　InfoType *info; 　　　　　　　// 该弧相关信息的指针
　　} ArcBox;
　　typedef struct VexNode {　　　// 顶点结点结构定义
　　　VertexType data;
　　　ArcBox *firstin, *firstout;　 // 分别指向该顶点第一条入弧和出弧
　　} VexNode;
　　typedef struct { 　　　　　　// 十字链表结构定义
　　　VexNode xlist[MAX_VERTEX_NUM]; // 表头向量
　　　int vexnum, arcnum;　　　　　// 有向图的当前顶点数和弧数
　　　GraphKind kind;　　　　　　　// 图的种类标志
　　} OLGraph;

  

　　虽然在有向图的邻接表和逆邻接表中分别可以找到从顶点出发的弧和指向顶点的弧，但对于同一个有向图需要用两个结构来表示它毕竟不方便，因此当应用问题中同时需要对这两种弧进行处理时就需要采用十字链表来表示有向图。

　　从例图可见，有向图的十字链表类似于第5章5.2.2节中讨论的稀疏矩阵的十字链表。图中每个弧结点恰好对应有向图G2的邻接矩阵中的非零元素，可将邻接矩阵看成是一个稀疏矩阵，同一行的非零元构成一个链表，同一列的非零元构成一个链表，行链表和列链表的头指针都合在顶点的结点中。

　　由此在十字链表中不仅容易找到从任意一个顶点出发的弧，也容易找到指向任意一个顶点的弧。