图的存储结构——十字链表的理解
7.2.4十字链表 Orthogonal List
同无向图类似,有向图也有另外一种链式存储结构称为十字链表。
根据应用的需要,对于有向图有时既需要用邻接表,又需要用逆邻接表,这时可以把两个表合二为一,用有向图的邻接多重表(通常称为十字链表)表示。
十字链表的存储结构
十字链表的顶点结点结构
对有向图中的每一个顶点也用一个顶点结点表示,它由三个域组成,其中:
data域存储有关顶点的信息:firstinarc域是链接指针,指向第一条以该顶点为终点的弧;
firstoutarc域也是链接指针,指向第一条以该顶点为始点的弧。
所有的顶点结点组成一个顺序表。
十字链表的弧结点结构
在有向图的十字链表中,图中的每一条弧用一个弧结点表示。
弧结点的结构与无向图邻接多重表中的边结点结构类似,也有六个域。
其中:
tag是标记域,标记该弧是否被处理或被搜索过;
weight为弧的信息域,用于存储弧的权值等信息;
tailvex和headvex是分别表示弧尾顶点序号和弧头顶点序号的顶点域;
tailnextarc域是链接指针,指向下一条以顶点tailvex为始点(弧尾)的弧;
headnextarc也是链接指针,指向下一条以顶点headvex为终点(弧头)的弧。
十字链表的存储结构
在有向图的十字链表中,从顶点结点中的firstoutarc域出发,由弧结点中的tailnextarc域链接起来的链表,正好是原来的邻接表结构。统计该链表中弧结点的个数,可求得该顶点的出度。若从顶点结点的 firstoutarc域出发,由弧结点中的headnextarc域链接起来的链表,正好是原来的逆邻接表结构。统计该链表中弧结点的个数,可求得该顶点的入度。
其 实现 可以参考:
https://blog.****.net/majiakun1/article/details/88692940