数据结构与算法十一:2.3 图的存储结构–逆邻接表和十字链表-一一网

“这是我参与8月更文挑战的第25天，活动详情查看：8月更文挑战”

关注我,以下内容持续更新

数据结构与算法(一):时间复杂度和空间复杂度

前面的文章介绍了两种图的存储方式:邻接矩阵和邻接表,本篇继续介绍图的其他存储结构:逆邻接表和十字链表.

1. 逆邻接表

对于有向图而言，邻接链表的缺陷是要查询某个顶点的入度时需要遍历整个链表,所以引入了逆邻接表。
逆邻接表: 任一表头结点下的边结点的数量是图中该结点入度的弧的数量，与邻接表相反。图的邻接表，反映的是节点的出度邻接情况，图的逆邻接表反映的是节点的入度邻接情况。


a.逆邻接表

图中指向顶点V1的结点有V0和V3,所以逆邻接表中,顶点V1对应的顶点是下标0和3

2. 十字链表(适用于有向图)

对于有向图而言，邻接链表的缺陷是要查询某个顶点的入度时需要遍历整个链表，而逆邻接链表在查询某个顶点的出度时要遍历整个链表。所以引入了十字链表,十字链表是把邻接表和逆邻接表合二为一形成的表结构。其基本思想就是在邻接链表的出边表的基础上，增加一个入边表。
十字链表应用场景:当频繁的求一个顶点的入度和出度,或者求一个顶点是否是另一个顶点的邻接点或者逆邻接点，就需要用十字链表的存储方式。


b.十字链表存储有向图

注:绿色箭头表示邻接关系,红色箭头表示逆邻接关系

十字链表由顶点表结点VertexNode和边表结点EdgeNode两种结点构成。

顶点表结点VertexNode由data、firstadjin和firstadjout构成。
- data:数据域，存储有关顶点的数据信息。
- firstadjin:入边表头指针，指向该顶点的入边表的第一个结点;
- firstedgeout:出边表头指针，指向该顶点的出边表的第一个结点(firstedgeOut和邻接链表里的是一样的)。
边表结点EdgeNode由tailvex、headvex、taillink、headlink构成。
- tailvex、headvex: 分别表示弧起点和弧终点在顶点表中的下标;
- taillink:弧起点的出边表指针域,指向弧起点的出边表里的下一个结点，即指向与该边起点相同的下一条边;
- headlink:弧终点的入边表指针域,指向弧终点的入边表里的下一个结点，即指向与该边终点相同的下一条边;
- weight: 表示这条边的权值(非网图不需要)

//顶点结点
typedef struct VertexNode{
    int data;
    EdgeNode* firstadjin;
    EdgeNode* firstadjout;
};
//边表结点
typedef struct EdgeNode{
    int tailvex;
    int headvex;
    int weight;
    EdgeNode* headlink;
    EdgeNode* taillink;
};
复制代码

十字链表的图示中:

以v0为起点的弧有2个:<v0,v1>和<v0,v2>,所以v0的出边表中有2个边,即VertexNode的firstedgeOut指向第一个边表结点<v0,v1>,然后<v0,v1>的taillink指向<v0,v2>,也就是v0的出边表是这样的:<v0,v1>—><v0,v2>;(请看图中的红色箭头)
以v1为终点的弧有2个:<v0,v1>和<v3,v1>,所以v1的入边表中有2个边,即VertexNode的firstedgeIn指向第一个边表结点<v0,v1>,然后<v0,v1>的headlink指向<v0,v3>,也就是v1的入边表是这样的:<v0,v1>—><v0,v3>;(请看图中的绿色箭头)