文字描述
邻接多重表是无向图的另一种链式存储结构. 虽然邻接表是无向图的一种很有效的存储结构,在邻接表中容易求得顶点和边的各种信息. 但是,在邻接表中每一条边(vi,vj)有两个结点，分别在第i个和第j个链表中，这给某些图的操作带来不便。如对已被搜索过的边作记号或删除一条边等，此时需要找到表示同一条边的两个结点。因此，在进行这类操作的无向图的问题中采用邻接多重表更合适。
邻接多重表的结构和十字链表类型。边结点和顶点结点如下示：
边结点由6个域组成：mark为标志域，可标记这条边是否被搜索过； ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边，info为指向和边相关的各种信息的指针域。
顶点结点由2个域组成：data存储和该顶点相关的信息如顶点名称；firstedge域指示第一条依附于该顶点的边。
示意图
算法分析
建立邻接多重链表的时间复杂度和建立邻接表是相同的. 另外邻接多重表几乎只针对无向图或无向网。
代码实现
/*
以邻接多重表作为图的存储结构创建无向图。
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h> #define MAX_VERTEX_NUM 20
typedef enum {DG, DN, UDG, UDN} GraphKind;
typedef enum {unvisited, visited} VisitIf;
typedef char InfoType;
typedef char VertexType;
//顶点结点
typedef struct EBox{
VisitIf mark;//访问标记
int ivex, jvex;//该边依附的两个顶点的位置
struct EBox *ilink, *jlink;//分别指向依附这两个顶点的下一条边
InfoType *info;//该边信息指针
}EBox;
//边结点
typedef struct VexBox{
VertexType data;//存储顶点名称
EBox *firstedge;//指向第一条依附该顶点的边
}VexBox;
//图结点
typedef struct{
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,edgenum; //无向图的当前顶点数和边数
GraphKind kind;
}AMLGraph; /*
若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。
*/
int LocateVex(AMLGraph G, VertexType v)
{
int i = ;
for(i=; i<G.vexnum; i++){
if(v == G.adjmulist[i].data)
return i;
}
return -;
} /*
若G中存在顶点位置loc存在,则返回其顶点名称
*/
VertexType LocateVInfo(AMLGraph G, int loc){
return G.adjmulist[loc].data;
} /*
采用邻接多重表的存储结构，构造无向图
*/
int CreateUDG(AMLGraph *G)
{
int i = , j = , k = , IncInfo = ;
int vi = , vj = ;
char tmp[] = {};
EBox *p = NULL; printf("输入顶点数，边数，其他信息标志位: ");
scanf("%d,%d,%d", &G->vexnum, &G->edgenum, &IncInfo); for(i=; i<G->vexnum; i++){
//输入顶点值
printf("输入第%d个顶点: ", i+);
memset(tmp, , sizeof(tmp));
scanf("%s", tmp);
G->adjmulist[i].data = tmp[];
G->adjmulist[i].firstedge = NULL;
}
for(k=; k<G->edgenum; k++){
printf("输入第%d条边(顶点1, 顶点2): ", k+);
memset(tmp, , sizeof(tmp));
scanf("%s", tmp);
sscanf(tmp, "%c,%c", &vi, &vj);
i = LocateVex(*G, vi);
j = LocateVex(*G, vj);
p = (EBox*)malloc(sizeof(EBox));
p->ivex = i;
p->jvex = j;
p->mark = unvisited;
p->ilink = G->adjmulist[i].firstedge;
p->jlink = G->adjmulist[j].firstedge;
G->adjmulist[i].firstedge = p;
G->adjmulist[j].firstedge = p;
if(IncInfo){
//Input(p->info);
}
}
return ;
} /*
采用邻接多重表的存储结构，构造图
*/
int CreateGrap(AMLGraph *G)
{
printf("输入图类型: -有向图(0), -有向网(1), +无向图(2), -无向网(3): ");
scanf("%d", &G->kind);
switch(G->kind){
case DG:
case DN:
default:
printf("还不支持!\n");
return -;
case UDG:
return CreateUDG(G);
}
return ;
} /*
输出图的信息
*/
void printG(AMLGraph G)
{
if(G.kind == DG){
printf("类型：有向图；顶点数 %d, 边数 %d\n", G.vexnum, G.edgenum);
}else if(G.kind == DN){
printf("类型：有向网；顶点数 %d, 边数 %d\n", G.vexnum, G.edgenum);
}else if(G.kind == UDG){
printf("类型：无向图；顶点数 %d, 边数 %d\n", G.vexnum, G.edgenum);
}else if(G.kind == UDN){
printf("类型：无向网；顶点数 %d, 边数 %d\n", G.vexnum, G.edgenum);
}
int i = ;
EBox *vi = NULL;
EBox *vj = NULL;
EBox *vf = NULL;
for(i=; i<G.vexnum; i++){
printf("%c(%d): ", G.adjmulist[i].data, i);
vf = G.adjmulist[i].firstedge;
vi = vf->ilink;
vj = vf->jlink;
printf("fistedge:%c(%d)->%c(%d); ", LocateVInfo(G, vf->ivex), vf->ivex, LocateVInfo(G, vf->jvex), vf->jvex);
printf(" || ilink:");
while(vi){
printf("%c(%d)->%c(%d);", LocateVInfo(G, vi->ivex), vi->ivex, LocateVInfo(G, vi->jvex), vi->jvex);
vi = vi->ilink;
}
printf(" || jlink:");
while(vj){
printf("%c(%d)->%c(%d);", LocateVInfo(G, vj->ivex), vj->ivex, LocateVInfo(G, vj->jvex), vj->jvex);
vj = vj->jlink;
}
printf("\n");
}
return ;
} int main(int argc, char *argv[])
{
AMLGraph G;
if(CreateGrap(&G) > -){
printG(G);
}
return ;
}
邻接多重表存储结构(图)
代码运行