图->存储结构->邻接多重表

文字描述

　　邻接多重表是无向图的另一种链式存储结构. 虽然邻接表是无向图的一种很有效的存储结构,在邻接表中容易求得顶点和边的各种信息. 但是,在邻接表中每一条边(vi,vj)有两个结点，分别在第i个和第j个链表中，这给某些图的操作带来不便。如对已被搜索过的边作记号或删除一条边等，此时需要找到表示同一条边的两个结点。因此，在进行这类操作的无向图的问题中采用邻接多重表更合适。

　　邻接多重表的结构和十字链表类型。边结点和顶点结点如下示：

　　边结点由6个域组成：mark为标志域，可标记这条边是否被搜索过； ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边，info为指向和边相关的各种信息的指针域。

　　顶点结点由2个域组成：data存储和该顶点相关的信息如顶点名称；firstedge域指示第一条依附于该顶点的边。

示意图

算法分析

　　建立邻接多重链表的时间复杂度和建立邻接表是相同的. 另外邻接多重表几乎只针对无向图或无向网。

代码实现

  1 /*
  2     以邻接多重表作为图的存储结构创建无向图。
  3 */
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 #include <string.h>
  7 
  8 #define    MAX_VERTEX_NUM    20
  9 typedef enum {DG, DN, UDG, UDN} GraphKind;
 10 typedef enum {unvisited, visited} VisitIf;
 11 typedef char InfoType;
 12 typedef char VertexType;
 13 //顶点结点
 14 typedef struct EBox{
 15     VisitIf mark;//访问标记
 16     int ivex, jvex;//该边依附的两个顶点的位置
 17     struct EBox *ilink, *jlink;//分别指向依附这两个顶点的下一条边
 18     InfoType *info;//该边信息指针
 19 }EBox;
 20 //边结点
 21 typedef struct VexBox{
 22     VertexType data;//存储顶点名称
 23     EBox *firstedge;//指向第一条依附该顶点的边
 24 }VexBox;
 25 //图结点
 26 typedef struct{
 27     VexBox adjmulist[MAX_VERTEX_NUM];
 28     int vexnum,edgenum;    //无向图的当前顶点数和边数
 29     GraphKind kind;
 30 }AMLGraph;
 31 
 32 /*
 33     若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。
 34 */
 35 int LocateVex(AMLGraph G, VertexType v)
 36 {
 37     int i = 0;
 38     for(i=0; i<G.vexnum; i++){
 39         if(v == G.adjmulist[i].data)
 40             return i;
 41     }
 42     return -1;
 43 }
 44 
 45 /*
 46     若G中存在顶点位置loc存在,则返回其顶点名称
 47 */
 48 VertexType LocateVInfo(AMLGraph G, int loc){
 49     return G.adjmulist[loc].data;
 50 }
 51 
 52 /*
 53     采用邻接多重表的存储结构，构造无向图
 54  */
 55 int CreateUDG(AMLGraph *G)
 56 {
 57     int i = 0, j = 0, k = 0, IncInfo = 0;
 58     int vi = 0, vj = 0;
 59     char tmp[10] = {0};
 60     EBox *p = NULL;
 61     
 62     printf("输入顶点数，边数，其他信息标志位: ");
 63     scanf("%d,%d,%d", &G->vexnum, &G->edgenum, &IncInfo);
 64 
 65     for(i=0; i<G->vexnum; i++){
 66         //输入顶点值
 67         printf("输入第%d个顶点: ", i+1);
 68         memset(tmp, 0, sizeof(tmp));
 69         scanf("%s", tmp);
 70         G->adjmulist[i].data = tmp[0];
 71         G->adjmulist[i].firstedge = NULL;
 72     }
 73     for(k=0; k<G->edgenum; k++){
 74         printf("输入第%d条边(顶点1, 顶点2): ", k+1);
 75         memset(tmp, 0, sizeof(tmp));
 76         scanf("%s", tmp);
 77         sscanf(tmp, "%c,%c", &vi, &vj);
 78         i = LocateVex(*G, vi);
 79         j = LocateVex(*G, vj);
 80         p = (EBox*)malloc(sizeof(EBox));
 81         p->ivex = i;
 82         p->jvex = j;
 83         p->mark = unvisited;
 84         p->ilink = G->adjmulist[i].firstedge;
 85         p->jlink = G->adjmulist[j].firstedge;
 86         G->adjmulist[i].firstedge = p;
 87         G->adjmulist[j].firstedge = p;
 88         if(IncInfo){
 89             //Input(p->info);
 90         }
 91     }
 92     return 0;
 93 }
 94 
 95 /*
 96     采用邻接多重表的存储结构，构造图
 97 */
 98 int CreateGrap(AMLGraph *G)
 99 {
100     printf("输入图类型: -有向图(0), -有向网(1), +无向图(2), -无向网(3): ");
101     scanf("%d", &G->kind);
102     switch(G->kind){
103         case DG:
104         case DN:
105         default:
106             printf("还不支持!
");
107             return -1;
108         case UDG:
109             return CreateUDG(G);
110     }
111     return 0;
112 }
113 
114 /*
115     输出图的信息
116 */
117 void printG(AMLGraph G)
118 {
119     if(G.kind == DG){
120         printf("类型：有向图；顶点数 %d, 边数 %d
", G.vexnum, G.edgenum);
121     }else if(G.kind == DN){
122         printf("类型：有向网；顶点数 %d, 边数 %d
", G.vexnum, G.edgenum);
123     }else if(G.kind == UDG){
124         printf("类型：无向图；顶点数 %d, 边数 %d
", G.vexnum, G.edgenum);
125     }else if(G.kind == UDN){
126         printf("类型：无向网；顶点数 %d, 边数 %d
", G.vexnum, G.edgenum);
127     }
128     int i = 0;
129     EBox *vi = NULL;
130     EBox *vj = NULL;
131     EBox *vf = NULL;
132     for(i=0; i<G.vexnum; i++){
133         printf("%c(%d): ", G.adjmulist[i].data, i);
134         vf = G.adjmulist[i].firstedge;
135         vi = vf->ilink;
136         vj = vf->jlink;
137         printf("fistedge:%c(%d)->%c(%d); ", LocateVInfo(G, vf->ivex), vf->ivex, LocateVInfo(G, vf->jvex), vf->jvex);
138         printf(" || ilink:");
139         while(vi){
140             printf("%c(%d)->%c(%d);", LocateVInfo(G, vi->ivex), vi->ivex, LocateVInfo(G, vi->jvex), vi->jvex);
141             vi = vi->ilink;
142         }
143         printf(" || jlink:");
144         while(vj){
145             printf("%c(%d)->%c(%d);", LocateVInfo(G, vj->ivex), vj->ivex, LocateVInfo(G, vj->jvex), vj->jvex);
146             vj = vj->jlink;
147         }
148         printf("
");
149     }
150     return ;
151 }
152 
153 int main(int argc, char *argv[])
154 {
155     AMLGraph G;
156     if(CreateGrap(&G) > -1){
157         printG(G);
158     }
159     return 0;
160 }

邻接多重表存储结构(图)

代码运行