图 |
您所在的位置：网站首页 › 多重图的特点 › 图 |
图
|
文字描述 邻接多重表是无向图的另一种链式存储结构. 虽然邻接表是无向图的一种很有效的存储结构,在邻接表中容易求得顶点和边的各种信息. 但是,在邻接表中每一条边(vi,vj)有两个结点，分别在第i个和第j个链表中，这给某些图的操作带来不便。如对已被搜索过的边作记号或删除一条边等，此时需要找到表示同一条边的两个结点。因此，在进行这类操作的无向图的问题中采用邻接多重表更合适。 邻接多重表的结构和十字链表类型。边结点和顶点结点如下示： 边结点由6个域组成：mark为标志域，可标记这条边是否被搜索过； ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边，info为指向和边相关的各种信息的指针域。 顶点结点由2个域组成：data存储和该顶点相关的信息如顶点名称；firstedge域指示第一条依附于该顶点的边。 示意图
算法分析 建立邻接多重链表的时间复杂度和建立邻接表是相同的. 另外邻接多重表几乎只针对无向图或无向网。 代码实现
 
1 /*
2 以邻接多重表作为图的存储结构创建无向图。
3 */
4 #include
5 #include
6 #include
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; ivexnum, &G->edgenum, &IncInfo);
64
65 for(i=0; ivexnum; 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; kedgenum; 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("还不支持!\n");
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\n", G.vexnum, G.edgenum);
121 }else if(G.kind == DN){
122 printf("类型：有向网；顶点数 %d, 边数 %d\n", G.vexnum, G.edgenum);
123 }else if(G.kind == UDG){
124 printf("类型：无向图；顶点数 %d, 边数 %d\n", G.vexnum, G.edgenum);
125 }else if(G.kind == UDN){
126 printf("类型：无向网；顶点数 %d, 边数 %d\n", 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; iilink;
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("\n");
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 }
邻接多重表存储结构(图)
代码运行
|
【本文地址】