作者：解学武

存储有向图（网），可以使用邻接表或者逆邻接表结构，也可以使用本节讲解的十字链表结构。

用邻接表存储有向图（网），可以快速计算出某个顶点的出度，但计算入度的效率不高。反之，用逆邻接表存储有向图（网），可以快速计算出某个顶点的入度，但计算出度的效率不高。

那么有没有一种存储结构，可以快速计算出有向图（网）中某个顶点的入度和出度呢？答案是肯定的，十字链表就是这样的一种存储结构。

十字链表（Orthogonal List）是一种专门存储有向图（网）的结构，它的核心思想是：将图中的所有顶点存储到顺序表（也可以是链表）中，同时为每个顶点配备两个链表，一个链表记录以当前顶点为弧头的弧，另一个链表记录以当前顶点为弧尾的弧。

举个简单的例子，用十字链表结构存储图 1a) 中的有向图，图的存储状态如图 1b) 所示：


观察图 1b)，顺序表中的各个存储空间分为 3 部分，各个链表中的结点空间分为 4 部分。

顺序表中的空间用来存储图中的顶点，结构如下图所示：


各部分的含义分别是：

• data 数据域：用来存储顶点的信息；
• firstin 指针域：指向一个链表，链表中记录的都是以当前顶点为弧头的弧的信息；
• firstout 指针域：指向另一个链表，链表中记录的是以当前顶点为弧尾的弧的信息。

链表的结点用来存储图中的弧，结构如下图所示：

各部分的含义分别是：

• tailvex数据域：存储弧尾一端顶点在顺序表中的位置下标；
• headvex 数据域：存储弧头一端顶点在顺序表中的位置下标；
• hlink 指针域：指向下一个以当前顶点作为弧头的弧；
• tlink 指针域：指向下一个以当前顶点作为弧尾的弧；
• info 指针：存储弧的其它信息，例如有向网中弧的权值。如果不需要存储其它信息，可以省略。

在十字链表结构中，如果想计算某个顶点的出度，就统计 firstout 所指链表中的结点数量，每找到一个结点，再根据它的 tlink 指针域寻找下一个结点，直到最后一个结点。同样的道理，如果想计算某个顶点的入度，就统计 firstin 所指链表中的结点数量，每找到一个结点，再根据它的 hlink 指针域寻找下一个结点，直到最后一个结点。

以图 1b) 中的 V1 顶点为例，计算出度的过程是：

• 根据 V1 顶点的 firstout 指针，找到存储 <V1, V2> 弧的结点；
• 根据 <V1, V2> 弧结点中的 tlink 指针，找到存储 <V1, V3> 弧的结点；
• 由于 <V1, V3> 弧结点的 tlink 指针为 NULL，因此只找到了 2 个弧，V1 顶点的出度就为 2。

计算 V1 顶点入度的过程是：

• 根据 V1 顶点的 firstin 指针，找到存储 <V4, V1> 弧的结点；
• 由于 <V4, V1> 弧结点的 hlink 指针为 NULL，因此只找到了 1 个弧，V1 顶点的入度就为 1。

如果你已经学会了邻接表和逆邻接表，可以将十字链表想象成邻接表和逆邻接表的结合体。

构建图的十字链表结构，对应的 C 语言代码如下：

#define  MAX_VERTEX_NUM 20 //图中顶点的最大数量
#define  InfoType int*     //表示弧额外信息的数据类型
#define  VertexType char    //图中顶点的数据类型
//表示链表中存储弧的结点
typedef struct ArcBox {
    int tailvex, headvex;          //弧尾、弧头对应顶点在顺序表中的位置下标
    struct ArcBox* hlik, * tlink;  //hlik指向下一个以当前顶点为弧头的弧结点；
                                   //tlink 指向下一个以当前顶点为弧尾的弧结点；
    //InfoType info;               //存储弧相关信息的指针
}ArcBox;

//表示顺序表中的各个顶点
typedef struct VexNode {
    VertexType data;              //顶点的数据域
    ArcBox* firstin, * firstout;  //指向以该顶点为弧头和弧尾的链表首个结点
}VexNode;

//表示十字链表存储结构
typedef struct {
    VexNode xlist[MAX_VERTEX_NUM];  //存储顶点的顺序表
    int vexnum, arcnum;             //记录图的顶点数和弧数
}OLGraph;

十字链表结构的具体实现

以图 1a) 为例，十字链表结构存储此图的完整 C 语言程序如下所示：

#include<stdio.h>
#define  MAX_VERTEX_NUM 20 //图中顶点的最大数量
#define  InfoType int*     //表示弧额外信息的数据类型
#define  VertexType char    //图中顶点的数据类型
//表示链表中存储弧的结点
typedef struct ArcBox {
    int tailvex, headvex;          //弧尾、弧头对应顶点在顺序表中的位置下标
    struct ArcBox* hlik, * tlink;  //hlik指向下一个以当前顶点为弧头的弧结点；
                                   //tlink 指向下一个以当前顶点为弧尾的弧结点；
    //InfoType info;               //存储弧相关信息的指针
}ArcBox;

//表示顺序表中的各个顶点
typedef struct VexNode {
    VertexType data;              //顶点的数据域
    ArcBox* firstin, * firstout;  //指向以该顶点为弧头和弧尾的链表首个结点
}VexNode;

//表示十字链表存储结构
typedef struct {
    VexNode xlist[MAX_VERTEX_NUM];  //存储顶点的顺序表
    int vexnum, arcnum;             //记录图的顶点数和弧数
}OLGraph;

int LocateVex(OLGraph* G, VertexType v) {
    int i;
    //遍历一维数组，找到变量v
    for (i = 0; i < G->vexnum; i++) {
        if (G->xlist[i].data == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回 -1
    if (i > G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}

//构建十字链表存储结构
void CreateDG(OLGraph* G) {
    int i, j, k;
    VertexType v1, v2;
    ArcBox* p = NULL;
    //输入有向图的顶点数和弧数
    scanf("%d %d", &(G->vexnum), &(G->arcnum));
    getchar();
    //使用一维数组存储顶点数据，初始化指针域为NULL
    for (i = 0; i < G->vexnum; i++) {
        scanf("%c", &(G->xlist[i].data));
        getchar();
        G->xlist[i].firstin = NULL;
        G->xlist[i].firstout = NULL;
    }
    //存储图中的所有弧
    for (k = 0; k < G->arcnum; k++) {
        scanf("%c %c", &v1, &v2);
        getchar();
        //确定v1、v2在数组中的位置下标
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        //建立弧的结点
        p = (ArcBox*)malloc(sizeof(ArcBox));
        p->tailvex = i;
        p->headvex = j;
        //采用头插法插入新的p结点
        p->hlik = G->xlist[j].firstin;
        p->tlink = G->xlist[i].firstout;
        G->xlist[j].firstin = G->xlist[i].firstout = p;
    }
}

//计算某顶点的入度
int indegree(OLGraph* G, VertexType x) {
    int i;
    int num = 0;
    //遍历整个顺序表
    for (i = 0; i < G->vexnum; i++) {
        //找到目标顶点
        if (x == G->xlist[i].data) {
            //从该顶点的 firstin 指针所指的结点开始遍历
            ArcBox* p = G->xlist[i].firstin;
            while (p)
            {
                num++;
                //遍历 hlink 指针指向的下一个结点
                p = p->hlik;
            }
            break;
        }
    }
    if (i == G->vexnum) {
        printf("图中没有指定顶点\n");
        return -1;
    }
    return num;
}

//计算某顶点的出度
int outdegree(OLGraph* G, VertexType x) {
    int i;
    int num = 0;
    //遍历整个顺序表
    for (i = 0; i < G->vexnum; i++) {
        //找到目标顶点
        if (x == G->xlist[i].data) {
            //从该顶点的 firstout 指针所指的结点开始遍历
            ArcBox* p = G->xlist[i].firstout;
            while (p)
            {
                num++;
                //遍历 tlink 指针指向的下一个结点
                p = p->tlink;
            }
            break;
        }
    }
    if (i == G->vexnum) {
        printf("图中没有指定顶点\n");
        return -1;
    }
    return num;
}

//删除十字链表结构
//每个顶点配备两个链表，选定一个链表（比如 firstout 所指链表），删除每个顶点中 firstout 所指链表上的结点
void DeleteDG(OLGraph* G) {
    int i;
    ArcBox* p = NULL, * del = NULL;
    for (i = 0; i < G->vexnum; i++) {
        p = G->xlist[i].firstout;
        while (p) {
            del = p;
            p = p->tlink;
            free(del);
        }
        //将第 i 个位置的两个指针全部置为 NULL，能有效避免出现野指针
        G->xlist[i].firstout = NULL;
        G->xlist[i].firstin = NULL;
    }
}
int main() {
    OLGraph G;
    CreateDG(&G);
    printf("A 顶点的入度为 %d\n", indegree(&G, 'A'));
    printf("A 顶点的出度为 %d\n", outdegree(&G, 'A'));
    DeleteDG(&G);
    return 0;
}

分别用 A、B、C、D 表示 V1、V2、V3 和 V4，程序的运行结果为：

4 5
A B C D
A B
A C
C D
D A
D B
A 顶点的入度为 1
A 顶点的出度为 2