上一节介绍了如何使用顺序存储结构存储多个相邻表和
相邻是指顶点之间存在边或弧，通过当前顶点可以直接找到下一个顶点。
旁边的桌子
使用邻表保存图时，图中的每个顶点及其关联的邻居都将被保存在链表中。 每个链表都有一个头节点，头节点的数据字段用于存储顶点本身的数据，而不是空值。 后续链表中的每个节点包含当前顶点的所有相邻点。
因此，使用邻接表存储图表时，将构建与顶点数量相同的链表。 为了便于管理这些链表，经常使用按一定顺序存储所有链表的链表头的方法
图1的表节点结构
因为info域对于有向图没有权重和其他相关信息，所以可以根据需要删除。
例如，存储图2(a )所示的有向图时，构成的邻接表如图2(a )所示。
图2有向图和对应的邻接表
邻接表的存储映射的存储结构如下。
#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数据； //顶点数据字段
ArcNode * firstarc； //指向相邻点指针
}VNode，AdjList[MAX_VERTEX_NUM]； //存储各链表开头节点的数组
typedef struct {
AdjList vertices； //图中顶点和各相邻点的排列
int vexnum，arcnum； //记录图表的顶点数和边或弧数
int kind； //记录图的种类
(}ALGraph；
邻接表计算顶点的度
使用邻接表格容纳有向图时，各顶点的度是包含在各自的链表中的节点数； 有向图被收藏的情况下，各个链表所具备的节点数是其顶点的出现度。 求入度需要遍历整个邻接表的节点，统计数据字段与其顶点数据字段相同的节点数量，即顶点的入度。
求有向图中某个节点的进入度，还有一种制作逆邻接表的方法。 此表仅用于存储图表中指向该顶点的所有顶点数组中的位置下标。 例如，构建图2(a )的反向邻接表时，如下所示。
图3逆邻表
在有n个顶点和e条边的有向图的情况下，邻接表中需要容纳n个头节点和2e个表节点。 如果图中的边和弧稀疏，使用邻接表比上一节中说明的邻接矩阵更能节约空间。
十字链表
十字链表存储的对象是有向图或者有向网络。 和邻接表相同，图(网)的各顶点分别构成链表，是链表的最初节点。 另外，有向图(网)中的弧有弧头和弧尾。 一个顶点的所有弧头的数量是该顶点的入度，弧尾的数量是该顶点的出度。 在每个顶点构成的链表中，以其顶点为弧首的弧单独构成链表，以其顶点为弧尾的弧也单独构成链表，两个链表的表头都是其顶点构成的节点。
这样，为每个顶点构建的链表按照一定的顺序存储在数组中，构成十字链表。
因此，交叉链表由顶点节点和弧节点两种节点构成。 各个结构如下图所示。
图4交叉链表的节点结构
在弧节点中，tailvex和headvex分别存储弧尾和弧头对应的顶点数组中的下标； hlink和tlink是指针字段，分别指向下一个具有相同弧头和相同弧尾的弧； info是指针字段，其保存该弧所具有的关联信息，例如权重等。
在顶点节点中，data域保存包含在该顶点中的数据； firstin和firstout是两个指针字段，分别指向以其顶点为弧头和弧尾的第一个弧节点。
图5有向图及其十字链表
例如，使用十字链表存储在图5(a )中，如图5(a )所示，构建代码如下。
#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 (; ivexnum; 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; ivexnum; i++) {
scanf(“%d”,&(G->xlist[i].data));
G->xlist[i].firstin=NULL;
G->xlist[i].firstout=NULL;
}
//构建十字链表
for (int k=0;karcnum; 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;
}
}
对于链表中的各个结点来说，由于表示的都是该顶点的出度或者入度，所以结点之间没有先后次序之分，程序中构建链表对于每个新初始化的结点采用头插法进行插入。
十字链表计算顶点的度
采用十字链表表示的有向图，在计算某顶点的出度时，为 firstout 域链表中结点的个数；入度为 firstin 域链表中结点的个数。
邻接多重表
使用邻接表解决在无向图中删除某两个结点之间的边的操作时，由于表示边的结点分别处在两个顶点为头结点的链表中，所以需要都找到并删除，操作比较麻烦。处理类似这种操作，使用邻接多重表会更合适。
邻接多重表可以看做是邻接表和十字链表的结合体。和十字链表唯一不同的是顶点结点和表结点的结构组成不同；同邻接表相比，不同的地方在于邻接表表示无向图中每个边都用两个结点，分别在两个不同链表中；而邻接多重表表示无向图中的每个边只用一个结点。
邻接多重表的顶点结点和表结点的构成如图 6 所示：
图 6 邻接多重表
表结点构成：
skdl 为标志域，作用是标记某结点是否已经被操作过，例如在遍历各结点时， skdl 域为 0 表示还未遍历；skdl 域为 1 表示该结点遍历过；
ivex 和 jvex 分别表示该结点表示的边两端的顶点在数组中的位置下标； ilink 指向下一条与 ivex 相关的边；
jlink 指向下一条与 jvex 相关的边；
info 指向与该边相关的信息。
顶点结点构成：
data 为该顶点的数据域；
firstedge 为指向第一条跟该顶点有关系的边。
图 7 无向图及对应的邻接多重表
例如，使用邻接多重表表示图 7中左边的无向图时，与之相对应的邻接多重表如图右侧所示。
邻接多重表的存储结构用代码表示为：
#define MAX_VERTEX_NUM 20 //图中顶点的最大个数
#define InfoType int //边含有的信息域的数据类型
#define VertexType int //图顶点的数据类型
typedef enum {unvisited,visited}VisitIf; //边标志域
typedef struct EBox{
VisitIf skdl; //标志域
int ivex,jvex; //边两边顶点在数组中的位置下标
struct EBox * ilink,*jlink; //分别指向与ivex、jvex相关的下一个边
InfoType *info; //边包含的其它的信息域的指针
}EBox;
typedef struct VexBox{
VertexType data; //顶点数据域
EBox * firstedge; //顶点相关的第一条边的指针域
}VexBox;
typedef struct {
VexBox adjmulist[MAX_VERTEX_NUM];//存储图中顶点的数组
int vexnum,degenum;//记录途中顶点个数和边个数的变量
}AMLGraph;
总结
本节介绍了有关图的三种链式存储结构：邻接表、十字链表和邻接多重表。
邻接表适用于所有的图结构，无论是有向图(网)还是无向图(网)，存储结构较为简单，但是在存储一些问题时，例如计算某顶点的度，需要通过遍历的方式自己求得。
十字链表适用于有向图(网)的存储，使用该方式存储的有向图，可以很容易计算出顶点的出度和入度，只需要知道对应链表中的结点个数即可。
邻接多重表适用于无向图(网)的存储，该方式避免了使用邻接表存储无向图时出现的存储空间浪费的现象，同时相比邻接表存储无向图，更方便了某些边操作(遍历、删除等)的实现。
支付宝扫一扫
微信扫一扫
