注：十字链表是有向图的链式存储结构

有向图用邻接表法存储的时候，计算出度容易，计算入度难；用逆邻接表存则相反。

如何存储能使得有向图计算出度和入度都容易呢？

最容易想到的就是把邻接表和逆邻接表都存一份，此外有什么方式能将两个表合并在一起呢？ 十字链表。

如图：

---

存储类型表示

上图可看出，图有顶点表结点和边表结点组成

顶点表结点数据成员：data（顶点信息）+ first_RAdjhead（逆邻接表表头指针） + first_Adjhead（邻接表表头指针）

边表结点： tailvex（弧尾顶点下标）+ headvex（弧头顶点下标）+ RAdjPointer（逆邻接表指针）+ AdjPointer（邻接表指针）

// 边表结点
typedef struct ArcNode
{
    /*data*/
    // 弧尾顶点下标
    int tailvex;

    // 弧头顶点下标
    int headvex;

    // 逆邻接表指针
    struct ArcNode *RAdjPointer;

    // 邻接表指针
    struct ArcNode *AdjPointer;

    // 若为网，则添加权值
    // double ArcVal;
}ArcNode;


typedef char VextexType;

// 顶点表结点
typedef struct
{
    /*data*/
    // 顶点信息
    VextexType Info;

    // 逆邻接表表头指针
    ArcNode *First_RAdjhead;

    // 邻接表表头指针
    ArcNode *First_Adjhead;

}VexNode;


#define MaxVexNode 100

// 图的十字链表存储
typedef struct
{
    /* data */
    //顶点表数组
    VexNode Vex[MaxVexNode];

    // 顶点和弧的个数
    int Vexnum, ArcNum;

}MGraph;

---

建图过程

阿Q自行完成的十字链表建图过程：

其实本质即为同时维护邻接表和逆邻接表。以下为建立有向图的十字链表（邻接表和逆邻接表的维护均为头插法）

阿Q：看着很难，其实实现起来特别快。

int FindVex(OrthLinkGraph G, VextexType v){
    for(int i = 0; i < G.Vexnum; i++)
        if(G.Vex[i].Info == v) return i;
    return -1;
}

// 判断<u, v> 存在弧 
bool Exist(OrthLinkGraph G, int u, int v){
    // 找邻接表（出度）
    ArcNode *ptr = G.Vex[u].First_Adjhead;

    for(; ptr != nullptr; ptr = ptr->AdjPointer)
        if(ptr->headvex == v) return true; // <tailvex, headvex>
    
    return false;
}

// 建图过程
#include<iostream>
// 十字链表是有向图（网）的存储结构，此处以建立有向图为例
// 手动输入顶点信息和边信息
void CreateGraph(OrthLinkGraph &G){
    std::cout << "Input VexNum: ";
    std::cin >> G.Vexnum;

    std::cout << "Input ArcNum: ";
    std::cin >> G.ArcNum;

    // 初始化十字链表 并 输入顶点信息
    std::cout << "Input VexInfo(char): ";
    for(int i = 0; i < G.Vexnum; i++){
        std::cin >> G.Vex[i].Info;
        G.Vex[i].First_Adjhead = nullptr;
        G.Vex[i].First_RAdjhead = nullptr;
    }

    // 输入边信息，建立所需图的十字链表
    int i = 0;
    while(i < G.ArcNum){
        // <vex1,vex2> 弧边
        VextexType vex1, vex2;
        std::cout << "Input <vex1,vex2>(char): ";
        std::cin >> vex1 >> vex2;

        int index1 = FindVex(G, vex1);
        int index2 = FindVex(G, vex2);

        // 有这俩顶点 且 该边没有存值 才能存入该边的值
        if(index1 == index2 || index1 == -1 || index2 == -1 || Exist(G, index1, index2)){
            std::cout << "Input same Vex / No such Vex / This edge already have value" << std::endl;
            continue;
        }else{
            i++;
            // 维护邻接表和逆邻接表（重点！）
            
            // 新建边表结点
            ArcNode *newArc = new ArcNode;

            // <index1, index2>
            newArc->tailvex = index1;
            newArc->headvex = index2;

            newArc->AdjPointer = nullptr;
            newArc->RAdjPointer = nullptr;

            // 维护vex1的邻接表
            // 头插法（后半部分指针 - 邻接表）
            newArc->AdjPointer = G.Vex[index1].First_Adjhead;
            G.Vex[index1].First_Adjhead = newArc;

            // 维护vex2的逆邻接表
            // 头插法（前半部分指针 - 逆邻接表）
            newArc->RAdjPointer = G.Vex[index2].First_RAdjhead;
            G.Vex[index2].First_RAdjhead = newArc;
        }
    }

}

测试代码

int main(){
    OrthLinkGraph G;
    CreateGraph(G);

    // 依次计算 各顶点的度
    for(int i = 0; i < G.Vexnum; i++){
        // 入度，出度，度
        int InCount, OutCount, Count;
        InCount = OutCount = Count = 0;

        // 出度
        for(ArcNode *ptr = G.Vex[i].First_Adjhead; ptr != nullptr; ptr = ptr->AdjPointer)
            OutCount++;
        
        // 出度
        for(ArcNode *ptr = G.Vex[i].First_RAdjhead; ptr != nullptr; ptr = ptr->RAdjPointer)
            InCount++;

        Count = InCount + OutCount;

        std::cout << "vextex: " << G.Vex[i].Info << "   --- Indegree: " << InCount << "\tOutdegree:" << OutCount << "\tdegree:" << Count << std::endl;
    }

    return 0;
}
/*
输入:
Input VexNum: 4
Input ArcNum: 7
Input VexInfo(char): ABCD
Input <vex1,vex2>(char): AB
Input <vex1,vex2>(char): AC
Input <vex1,vex2>(char): CA
Input <vex1,vex2>(char): CD
Input <vex1,vex2>(char): DA
Input <vex1,vex2>(char): DB
Input <vex1,vex2>(char): DC
*/
/*
输出:
vextex: A   --- Indegree: 2     Outdegree:2     degree:4
vextex: B   --- Indegree: 2     Outdegree:0     degree:2
vextex: C   --- Indegree: 2     Outdegree:2     degree:4
vextex: D   --- Indegree: 1     Outdegree:3     degree:4
*/

建立如下图：

---

适用及优劣性

适用：有向图（网）

优点

• 出度和入度都容易计算
• 适合存储稀疏的有向图

阿Q：有向图的十字链表存储本质就是将邻接表和逆邻接表整合在一起；因此在建立边<u,v>时既要维护顶点u的邻接表，也要维护顶点v的逆邻接表