【图论】图论及数据结构图储存结构的C语言代码实现_图的储存结构极其应用代码

数据结构的图存储结构，常用于存储逻辑关系为 “多对多” 的数据。图存储结构，是重点，也是难点。

小白要想玩转数据结构的图，就必须稳扎稳打，死抠图结构的每一个知识点，每一行代码，只有这样，才有彻底学会图存储结构的可能。

除了图存储结构的理论知识，还会穿插一些与图存储结构相关的常用算法，例如克鲁斯卡尔算法，迪杰斯特拉算法、弗洛伊德算法等。

数据结构的图存储结构

我们知道，数据之间的关系有 3 种，分别是 “一对一”、“一对多” 和 “多对多”，前两种关系的数据可分别用线性表和树结构存储，具有"多对多"逻辑关系数据的结构——图存储结构。

图 1 所示为存储 V1、V2、V3、V4 的图结构，从图中可以清楚的看出数据之间具有的"多对多"关系。例如，V1 与 V4 和 V2 建立着联系，V4 与 V1 和 V3 建立着联系，以此类推。

与链表不同，图中存储的各个数据元素被称为顶点（而不是节点）。拿图 1 来说，该图中含有 4 个顶点，分别为顶点 V1、V2、V3 和 V4。

图存储结构中，习惯上用 Vi 表示图中的顶点，且所有顶点构成的集合通常用 V 表示，如图 1 中顶点的集合为 V={V1,V2,V3,V4}。

注意，图 1 中的图仅是图存储结构的其中一种，数据之间 “多对多” 的关系还可能用如图 2 所示的图结构表示：

可以看到，各个顶点之间的关系并不是"双向"的。比如，V4 只与 V1 存在联系（从 V4 可直接找到 V1），而与 V3 没有直接联系；同样，V3 只与 V4 存在联系（从 V3 可直接找到 V4），而与 V1 没有直接联系，以此类推。

因此，图存储结构可细分两种表现类型，分别为无向图（图 1）和有向图（图 2）。

图存储结构基本常识

弧头和弧尾

有向图中，无箭头一端的顶点通常被称为"初始点"或"弧尾"，箭头直线的顶点被称为"终端点"或"弧头"。

入度和出度

对于有向图中的一个顶点 V 来说，箭头指向 V 的弧的数量为 V 的入度（InDegree，记为 ID(V)）；箭头远离 V 的弧的数量为 V 的出度（OutDegree，记为OD(V)）。拿图 2 中的顶点 V1来说，该顶点的入度为 1，出度为 2（该顶点的度为 3）。

(V1,V2) 和 <V1,V2> 的区别

无向图中描述两顶点（V1 和 V2）之间的关系可以用 (V1,V2) 来表示，而有向图中描述从 V1 到 V2 的"单向"关系用 <V1,V2> 来表示。由于图存储结构中顶点之间的关系是用线来表示的，因此 (V1,V2) 还可以用来表示无向图中连接 V1 和 V2 的线，又称为边；同样，<V1,V2> 也可用来表示有向图中从 V1 到 V2 带方向的线，又称为弧。

集合 VR 的含义

并且，图中习惯用 VR 表示图中所有顶点之间关系的集合。例如，图 1 中无向图的集合 VR={(v1,v2),(v1,v4),(v1,v3),(v3,v4)}，图 2 中有向图的集合 VR={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

路径和回路

无论是无向图还是有向图，从一个顶点到另一顶点途径的所有顶点组成的序列（包含这两个顶点），称为一条路径。如果路径中第一个顶点和最后一个顶点相同，则此路径称为"回路"（或"环"）。
并且，若路径中各顶点都不重复，此路径又被称为"简单路径"；同样，若回路中的顶点互不重复，此回路被称为"简单回路"（或简单环）。
拿图 1 来说，从 V1 存在一条路径还可以回到 V1，此路径为 {V1,V3,V4,V1}，这是一个回路（环），而且还是一个简单回路（简单环）。

在有向图中，每条路径或回路都是有方向的。

权和网的含义

在某些实际场景中，图中的每条边（或弧）会赋予一个实数来表示一定的含义，这种与边（或弧）相匹配的实数被称为"权"，而带权的图通常称为网。如图 3 所示，就是一个网结构：

子图：指的是由图中一部分顶点和边构成的图，称为原图的子图。

图存储结构的分类

根据不同的特征，图又可分为完全图，连通图、稀疏图和稠密图：

• 完全图：若图中各个顶点都与除自身外的其他顶点有关系，这样的无向图称为完全图（如图 4a)）。同时，满足此条件的有向图则称为有向完全图（图 4b)）。

具有 n 个顶点的完全图，图中边的数量为 n(n-1)/2；而对于具有 n 个顶点的有向完全图，图中弧的数量为 n(n-1)。

稀疏图和稠密图：这两种图是相对存在的，即如果图中具有很少的边（或弧），此图就称为"稀疏图"；反之，则称此图为"稠密图"。

稀疏和稠密的判断条件是：e<nlogn，其中 e 表示图中边（或弧）的数量，n 表示图中顶点的数量。如果式子成立，则为稀疏图；反之为稠密图。

什么是连通图，（强）连通图详解

图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的。例如图 1 中，虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径，分别是 V1-V2-V3 和 V1-V4-V3，因此称 V1 和 V3 之间是连通的。

无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。例如，图 2 中的无向图就是一个连通图，因为此图中任意两顶点之间都是连通的。

若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为连通分量。

前面讲过，由图中部分顶点和边构成的图为该图的一个子图，但这里的子图指的是图中"最大"的连通子图（也称"极大连通子图"）。

如图 3 所示，虽然图 3a) 中的无向图不是连通图，但可以将其分解为 3 个"最大子图"（图 3b)），它们都满足连通图的性质，因此都是连通分量。

提示，图 3a) 中的无向图只能分解为 3 部分各自连通的"最大子图"。

需要注意的是，连通分量的提出是以"整个无向图不是连通图"为前提的，因为如果无向图是连通图，则其无法分解出多个最大连通子图，因为图中所有的顶点之间都是连通的。

强连通图

有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图。如图 4 所示就是一个强连通图。

与此同时，若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。

如图 5 所示，整个有向图虽不是强连通图，但其含有两个强连通分量。

可以这样说，连通图是在无向图的基础上对图中顶点之间的连通做了更高的要求，而强连通图是在有向图的基础上对图中顶点的连通做了更高的要求。

什么是生成树，生成树（生成森林）详解

学习连通图的基础上，本节学习什么是生成树，以及什么是生成森林。

对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。

如图 1 所示，图 1a) 是一张连通图，图 1b) 是其对应的 2 种生成树。

连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有多种不同的生成树与之对应。

连通图中的生成树必须满足以下 2 个条件：

1. 包含连通图中所有的顶点；
2. 任意两顶点之间有且仅有一条通路；

因此，连通图的生成树具有这样的特征，即生成树中边的数量 = 顶点数 - 1。

生成森林

生成树是对应连通图来说，而生成森林是对应非连通图来说的。

我们知道，非连通图可分解为多个连通分量，而每个连通分量又各自对应多个生成树（至少是 1 棵），因此与整个非连通图相对应的，是由多棵生成树组成的生成森林。、

如图 2 所示，这是一张非连通图，可分解为 3 个连通分量，其中各个连通分量对应的生成树如图 3 所示：

注意，图 3 中列出的仅是各个连通分量的其中一种生成树。
因此，多个连通分量对应的多棵生成树就构成了整个非连通图的生成森林。

图的顺序存储结构及其C语言代码实现

使用图结构表示的数据元素之间虽然具有“多对多”的关系，但是同样可以采用顺序存储，也就是使用数组有效地存储图。

使用数组存储图时，需要使用两个数组，一个数组存放图中顶点本身的数据（一维数组），另外一个数组用于存储各顶点之间的关系（二维数组）。

存储图中各顶点本身数据，使用一维数组就足够了；存储顶点之间的关系时，要记录每个顶点和其它所有顶点之间的关系，所以需要使用二维数组。

不同类型的图，存储的方式略有不同，根据图有无权，可以将图划分为两大类：图和网 。

图，包括无向图和有向图；网，是指带权的图，包括无向网和有向网。存储方式的不同，指的是：在使用二维数组存储图中顶点之间的关系时，如果顶点之间存在边或弧，在相应位置用 1 表示，反之用 0 表示；如果使用二维数组存储网中顶点之间的关系，顶点之间如果有边或者弧的存在，在数组的相应位置存储其权值；反之用 0 表示。

结构代码表示：

#define MAX_VERtEX_NUM 20                   //顶点的最大个数
#define VRType int                          //表示顶点之间的关系的变量类型
#define InfoType char                       //存储弧或者边额外信息的指针变量类型
#define VertexType int                      //图中顶点的数据类型
typedef enum{DG,DN,UDG,UDN}GraphKind;       //枚举图的 4 种类型
typedef struct {
    VRType adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    InfoType * info;                        //弧或边额外含有的信息指针
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据
    AdjMatrix arcs;                         //二维数组，记录顶点之间的关系
    int vexnum,arcnum;                      //记录图的顶点数和弧（边）数
    GraphKind kind;                         //记录图的种类
}MGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

例如，存储图 1 中的无向图（B）时，除了存储图中各顶点本身具有的数据外，还需要使用二维数组存储任意两个顶点之间的关系。

由于 （B） 为无向图，各顶点没有权值，所以如果两顶点之间有关联，相应位置记为 1 ；反之记为 0 。构建的二维数组如图 2 所示。

在此二维数组中，每一行代表一个顶点，依次从 V1 到 V5 ，每一列也是如此。比如 arcs[0][1] = 1 ，表示 V1 和 V2 之间有边存在；而 arcs[0][2] = 0，说明 V1 和 V3 之间没有边。

对于无向图来说，二维数组构建的二阶矩阵，实际上是对称矩阵，在存储时就可以采用压缩存储的方式存储下三角或者上三角。

通过二阶矩阵，可以直观地判断出各个顶点的度，为该行（或该列）非 0 值的和。例如，第一行有两个 1，说明 V1 有两个边，所以度为 2。

存储图 1 中的有向图（A）时，对应的二维数组如图 3 所示：

例如，arcs[0][1] = 1 ，证明从 V1 到 V2 有弧存在。且通过二阶矩阵，可以很轻松得知各顶点的出度和入度，出度为该行非 0 值的和，入度为该列非 0 值的和。例如，V1 的出度为第一行两个 1 的和，为 2 ； V1 的入度为第一列中 1 的和，为 1 。所以 V1 的出度为 2 ，入度为 1 ，度为两者的和 3 。

图的顺序存储结构C语言实现

#include <stdio.h>
#define MAX_VERtEX_NUM 20                   //顶点的最大个数
#define VRType int                          //表示顶点之间的关系的变量类型
#define InfoType char                       //存储弧或者边额外信息的指针变量类型
#define VertexType int                      //图中顶点的数据类型
typedef enum{DG,DN,UDG,UDN}GraphKind;       //枚举图的 4 种类型
typedef struct {
    VRType adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    InfoType * info;                        //弧或边额外含有的信息指针
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据
    AdjMatrix arcs;                         //二维数组，记录顶点之间的关系
    int vexnum,arcnum;                      //记录图的顶点数和弧（边）数
    GraphKind kind;                         //记录图的种类
}MGraph;
//根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G,VertexType v){
    int i=0;
    //遍历一维数组，找到变量v
    for (; i<G->vexnum; i++) {
        if (G->vexs[i]==v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i>G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}
//构造有向图
void CreateDG(MGraph *G){
    //输入图含有的顶点数和弧的个数
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    //依次输入顶点本身的数据
    for (int i=0; i<G->vexnum; i++) {
        scanf("%d",&(G->vexs[i]));
    }
    //初始化二维矩阵，全部归0，指针指向NULL
    for (int i=0; i<G->vexnum; i++) {
        for (int j=0; j<G->vexnum; j++) {
            G->arcs[i][j].adj=0;
            G->arcs[i][j].info=NULL;
        }
    }
    //在二维数组中添加弧的数据
    for (int i=0; i<G->arcnum; i++) {
        int v1,v2;
        //输入弧头和弧尾
        scanf("%d,%d",&v1,&v2);
        //确定顶点位置
        int n=LocateVex(G, v1);
        int m=LocateVex(G, v2);
        //排除错误数据
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        //将正确的弧的数据加入二维数组
        G->arcs[n][m].adj=1;
    }
}
//构造无向图
void CreateDN(MGraph *G){
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    for (int i=0; i<G->vexnum; i++) {
        scanf("%d",&(G->vexs[i]));
    }
    for (int i=0; i<G->vexnum; i++) {
        for (int j=0; j<G->vexnum; j++) {
            G->arcs[i][j].adj=0;
            G->arcs[i][j].info=NULL;
        }
    }
    for (int i=0; i<G->arcnum; i++) {
        int v1,v2;
        scanf("%d,%d",&v1,&v2);
        int n=LocateVex(G, v1);
        int m=LocateVex(G, v2);
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj=1;
        G->arcs[m][n].adj=1;//无向图的二阶矩阵沿主对角线对称
    }
}
//构造有向网，和有向图不同的是二阶矩阵中存储的是权值。
void CreateUDG(MGraph *G){
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    for (int i=0; i<G->vexnum; i++) {
        scanf("%d",&(G->vexs[i]));
    }
    for (int i=0; i<G->vexnum; i++) {
        for (int j=0; j<G->vexnum; j++) {
            G->arcs[i][j].adj=0;
            G->arcs[i][j].info=NULL;
        }
    }
    for (int i=0; i<G->arcnum; i++) {
        int v1,v2,w;
        scanf("%d,%d,%d",&v1,&v2,&w);
        int n=LocateVex(G, v1);
        int m=LocateVex(G, v2);
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj=w;
    }
}
//构造无向网。和无向图唯一的区别就是二阶矩阵中存储的是权值
void CreateUDN(MGraph* G){
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    for (int i=0; i<G->vexnum; i++) {
        scanf("%d",&(G->vexs[i]));
    }
    for (int i=0; i<G->vexnum; i++) {
        for (int j=0; j<G->vexnum; j++) {
            G->arcs[i][j].adj=0;
            G->arcs[i][j].info=NULL;
        }
    }
    for (int i=0; i<G->arcnum; i++) {
        int v1,v2,w;
        scanf("%d,%d,%d",&v1,&v2,&w);
        int m=LocateVex(G, v1);
        int n=LocateVex(G, v2);
        if (m==-1 ||n==-1) {
            printf("no this vertex\n");
            return;
        }
        G->arcs[n][m].adj=w;
        G->arcs[m][n].adj=w;//矩阵对称
    }
}
void CreateGraph(MGraph *G){
    //选择图的类型
    scanf("%d",&(G->kind));
    //根据所选类型，调用不同的函数实现构造图的功能
    switch (G->kind) {
        case DG:
            return CreateDG(G);
            break;
        case DN:
            return CreateDN(G);
            break;
        case UDG:
            return CreateUDG(G);
            break;
        case UDN:
            return CreateUDN(G);
            break;
        default:
            break;
    }
}
//输出函数
void PrintGrapth(MGraph G)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        for (int j = 0; j < G.vexnum; j++)
        {
            printf("%d ", G.arcs[i][j].adj);
        }
        printf("\n");
    }
}
int main() {
    MGraph G;//建立一个图的变量
    CreateGraph(&G);//调用创建函数，传入地址参数
    PrintGrapth(G);//输出图的二阶矩阵
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178

注意：在此程序中，构建无向网和有向网时，对于之间没有边或弧的顶点，相应的二阶矩阵中存放的是 0。目的只是为了方便查看运行结果，而实际上如果顶点之间没有关联，它们之间的距离应该是无穷大（∞）。

例如，使用上述程序存储图 4（a）的有向网时，存储的两个数组如图 4（b）所示：

相应地运行结果为：

2
6,10
1
2
3
4
5
6
1,2,5
2,3,4
3,1,8
1,4,7
4,3,5
3,6,9
6,1,3
4,6,6
6,5,1
5,4,5
0 5 0 7 0 0
0 0 4 0 0 0
8 0 0 0 0 9
0 0 5 0 0 6
0 0 0 5 0 0
3 0 0 0 1 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

总结一下，主要详细介绍了使用数组存储图的方法，在实际操作中使用更多的是链式存储结构，例如邻接表、十字链表和邻接多重表，将在后文重点介绍

图的邻接表存储结构详解

通常，图更多的是采用链表存储，具体的存储方法有 3 种，分别是邻接表、邻接多重表和十字链表。

先讲解图的邻接表存储法。邻接表既适用于存储无向图，也适用于存储有向图。

在具体讲解邻接表存储图的实现方法之前，先普及一个"邻接点"的概念。在图中，如果两个点相互连通，即通过其中一个顶点，可直接找到另一个顶点，则称它们互为邻接点。

邻接指的是图中顶点之间有边或者弧的存在。

邻接表存储图的实现方式是，给图中的各个顶点独自建立一个链表，用节点存储该顶点，用链表中其他节点存储各自的临界点。

与此同时，为了便于管理这些链表，通常会将所有链表的头节点存储到数组中（也可以用链表存储）。也正因为各个链表的头节点存储的是各个顶点，因此各链表在存储临界点数据时，仅需存储该邻接顶点位于数组中的位置下标即可。

例如，存储图 1a) 所示的有向图，其对应的邻接表如图 1b) 所示：

拿顶点 V1 来说，与其相关的邻接点分别为 V2 和 V3，因此存储 V1 的链表中存储的是 V2 和 V3 在数组中的位置下标 1 和 2。

从图 1 中可以看出，存储各顶点的节点结构分为两部分，数据域和指针域。数据域用于存储顶点数据信息，指针域用于链接下一个节点，如图 2 所示：

在实际应用中，除了图 2 这种节点结构外，对于用链接表存储网（边或弧存在权）结构，还需要节点存储权的值，因此需使用图 3 中的节点结构：

图 1 中的链接表结构转化为对应 C 语言代码如下：

#define  MAX_VERTEX_NUM 20//最大顶点个数
#define  VertexType int//顶点数据的类型
#define  InfoType int//图中弧或者边包含的信息的类型
typedef struct ArcNode{
    int adjvex;//邻接点在数组中的位置下标
    struct ArcNode * nextarc;//指向下一个邻接点的指针
    InfoType * info;//信息域
}ArcNode;
typedef struct VNode{
    VertexType data;//顶点的数据域
    ArcNode * firstarc;//指向邻接点的指针
}VNode,AdjList[MAX_VERTEX_NUM];//存储各链表头结点的数组
typedef struct {
    AdjList vertices;//图中顶点的数组
    int vexnum,arcnum;//记录图中顶点数和边或弧数
    int kind;//记录图的种类
}ALGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

邻接表计算顶点的出度和入度

使用邻接表计算无向图中顶点的入度和出度会非常简单，只需从数组中找到该顶点然后统计此链表中节点的数量即可。

而使用邻接表存储有向图时，通常各个顶点的链表中存储的都是以该顶点为弧尾的邻接点，因此通过统计各顶点链表中的节点数量，只能计算出该顶点的出度，而无法计算该顶点的入度。

对于利用邻接表求某顶点的入度，有两种方式：

1. 遍历整个邻接表中的节点，统计数据域与该顶点所在数组位置下标相同的节点数量，即为该顶点的入度；
2. 建立一个逆邻接表，该表中的各顶点链表专门用于存储以此顶点为弧头的所有顶点在数组中的位置下标。比如说，建立一张图 1a) 对应的逆邻接表，如图 4 所示：
   

对于具有 n 个顶点和 e 条边的无向图，邻接表中需要存储 n 个头结点和 2e 个表结点。在图中边或者弧稀疏的时候，使用邻接表要比前一节介绍的邻接矩阵更加节省空间。

图的十字链表存储结构

前面介绍了图的邻接表存储法，本节继续讲解图的另一种链式存储结构——十字链表法。

与邻接表不同，十字链表法仅适用于存储有向图和有向网。不仅如此，十字链表法还改善了邻接表计算图中顶点入度的问题。

十字链表存储有向图（网）的方式与邻接表有一些相同，都以图（网）中各顶点为首元节点建立多条链表，同时为了便于管理，还将所有链表的首元节点存储到同一数组（或链表）中。

其中，建立个各个链表中用于存储顶点的首元节点结构如图 1 所示：

从图 1 可以看出，首元节点中有一个数据域和两个指针域（分别用 firstin 和 firstout 表示）：

• firstin 指针用于连接以当前顶点为弧头的其他顶点构成的链表；
• firstout 指针用于连接以当前顶点为弧尾的其他顶点构成的链表；
• data 用于存储该顶点中的数据；

由此可以看出，十字链表实质上就是为每个顶点建立两个链表，分别存储以该顶点为弧头的所有顶点和以该顶点为弧尾的所有顶点。

注意，存储图的十字链表中，各链表中首元节点与其他节点的结构并不相同，图 1 所示仅是十字链表中首元节点的结构，链表中其他普通节点的结构如图 2 所示：

从图 2 中可以看出，十字链表中普通节点的存储分为 5 部分内容，它们各自的作用是：

• tailvex 用于存储以首元节点为弧尾的顶点位于数组中的位置下标；
• headvex 用于存储以首元节点为弧头的顶点位于数组中的位置下标；
• hlink 指针：用于链接下一个存储以首元节点为弧头的顶点的节点；
• tlink 指针：用于链接下一个存储以首元节点为弧尾的顶点的节点；
• info 指针：用于存储与该顶点相关的信息，例如量顶点之间的权值；

比如说，用十字链表存储图 3a) 中的有向图，存储状态如图 3b) 所示：

拿图 3 中的顶点 V1 来说，通过构建好的十字链表得知，以该顶点为弧头的顶点只有存储在数组中第 3 位置的 V4（因此该顶点的入度为 1），而以该顶点为弧尾的顶点有两个，分别为存储数组第 1 位置的 V2 和第 2 位置的 V3（因此该顶点的出度为 2）。

对于图 3 各个链表中节点来说，由于表示的都是该顶点的出度或者入度，因此没有先后次序之分。
图 3 中十字链表的构建过程转化为 C 语言代码为：

#define  MAX_VERTEX_NUM 20
#define  InfoType int//图中弧包含信息的数据类型
#define  VertexType int
typedef struct ArcBox{
    int tailvex,headvex;//弧尾、弧头对应顶点在数组中的位置下标
    struct ArcBox *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=0;
    //遍历一维数组，找到变量v
    for (; 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){
    //输入有向图的顶点数和弧数
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    //使用一维数组存储顶点数据，初始化指针域为NULL
    for (int i=0; i<G->vexnum; i++) {
        scanf("%d",&(G->xlist[i].data));
        G->xlist[i].firstin=NULL;
        G->xlist[i].firstout=NULL;
    }
    //构建十字链表
    for (int k=0;k<G->arcnum; k++) {
        int v1,v2;
        scanf("%d,%d",&v1,&v2);
        //确定v1、v2在数组中的位置下标
        int i=LocateVex(G, v1);
        int j=LocateVex(G, v2);
        //建立弧的结点
        ArcBox * 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

提示，代码中新节点的插入采用的是头插法。