1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<time.h>
4 #include<stdarg.h>
5 #define OK 1
6 #define NO 0
7 #define TRUE 1
8 #define FALSE 0
9 #define ERROR -1
10 #define MAX_VERTEX_NUM 20
//最大顶点个数
11
12 typedef
int Status;
13
14 typedef
int QElemType_L;
15
16 typedef
struct QNode
17 {
18 QElemType_L data;
19 struct QNode *
next;
20 }QNode;
21 typedef QNode *
QueuePtr;
22
23 typedef
struct
24 {
25 QueuePtr front;
26 QueuePtr rear;
27
28 }LinkQueue;
29
30 typedef
enum{DG,UDG}GraphKind;
31
32 typedef
struct ArcNode
33 {
34 int adjvex;
//该弧指向的顶点的位置
35 struct ArcNode *nextarc;
//指向下一个弧结点的指针
36 }ArcNode;
37
38 typedef
char VertexType_AL;
39 typedef
struct VNode
//头结点
40 {
41 VertexType_AL data;
42 ArcNode *
firstarc;
43 }VNode;
44 typedef VNode AdjList[MAX_VERTEX_NUM+
1];
45
46 /*图的存储方式*/
47 typedef
struct
48 {
49 AdjList vertices;
//邻接表
50 int vexnum,arcnum;
//图当前顶点数和弧数
51 GraphKind kind;
52 }ALGraph;
53
54 Status visited[MAX_VERTEX_NUM+
1];
55
56 void (*VisitFunc)(VertexType_AL e);
//函数指针变量
57
58 Status CreateGraph_AL(ALGraph *G,
int r);
59
60 Status CreateDG_AL(ALGraph *
G);
61
62 Status CreateUDG_AL(ALGraph *
G);
63
64 int LocateVex_AL(ALGraph G,VertexType_AL u);
65
66 Status FitstAdjVex_AL(ALGraph G,VertexType_AL u);
67
68 Status NextAdjVex_AL(ALGraph G,VertexType_AL v,VertexType_AL w);
69
70 Status PutVex_AL(ALGraph *
G,VertexType_AL v,VertexType_AL value);
71
72 Status InsertVex_AL(ALGraph *
G,VertexType_AL v);
73
74 Status InsertArc_AL(ALGraph *
G,VertexType_AL v,VertexType_AL w);
75
76 Status DeleteArc_AL(ALGraph *
G,VertexType_AL v,VertexType_AL w);
77
78 Status DeleteVex_AL(ALGraph *
G,VertexType_AL v);
79
80 void OutputALGraph(ALGraph G);
81
82 VertexType_AL GetVex_AL(ALGraph G,
int order);
83
84 void DFSTraverse_AL(ALGraph G);
85
86 void DFS_AL(ALGraph G,
int v);
87
88 void BFSTraverse_AL(ALGraph G);
89
90
91 Status InitQueue_L(LinkQueue *
Q);
92
93 Status QueueEmpyt(LinkQueue Q);
94
95 Status EnQueue_L(LinkQueue *
Q,QElemType_L e);
96
97 Status DeQueue_L(LinkQueue *Q,QElemType_L *
e);
98
99 Status ClearGraph_AL(ALGraph *
G);
100
101
102 int main(
int argc,
char**
argv)
103 {
104 ALGraph G;
105 printf(
"1、2、3\n函数CreateGraph_AL等测试..\n");
106 {
107 int r;
108 srand((unsigned)time(NULL));
//用系统的时间做随机数的种子
109 r=rand()%
2;
//对4取余只能产生0，1这几个数
110 switch(r)
111 {
112 case DG:
113 printf(
"初始化有向图 G..\n");
114 break;
115 case UDG:
116 printf(
"初始化无向图 G..\n");
117 break;
118 }
119 CreateGraph_AL(&
G,r);
120 printf(
"\n");
121 }
122
123
124 printf(
"17\n函数OutputALGraph 测试..\n");
125 {
126 printf(
"输出图的邻接表 G = \n");
127 OutputALGraph(G);
128 printf(
"\n");
129
130
131 }
132 printf(
"6\n函数 GetVex_AL 测试..\n");
133 {
134 printf(
"第%d个顶点的值为'%c'\n",
3,GetVex_AL(G,
3));
135
136 }
137 printf(
"8\n函数 FitstAdjVex_AL 测试..\n");
138 {
139 printf(
"'%c'的第一个邻接顶点的序号为 %d \n",
'B',FitstAdjVex_AL(G,
'B'));
140 printf(
"\n");
141 }
142
143 printf(
"9\n函数 NextAdjVex_AL 测试..\n");
144 {
145 printf(
"'%c'相对与'%c'的下一个邻接顶点的序号为 %d \n",
'A',
'B',NextAdjVex_AL(G,
'A',
'B'));
146 printf(
"\n");
147 }
148
149 printf(
"7\n函数PutVex_AL 测试..\n");
150 {
151 printf(
"对顶点'%c'赋值'%c'后，G=\n",
'A',
'X');
152 PutVex_AL(&G,
'A',
'X');
153 OutputALGraph(G);
154 printf(
"\n");
155
156 }
157 printf(
"10\n函数 InsertVex_AL 测试..\n");
158 {
159 printf(
"插入顶点'%c'后，G = \n",
'H');
160 InsertVex_AL(&G,
'H');
161 OutputALGraph(G);
162 printf(
"\n");
163 }
164 printf(
"12\n函数 InsertArc_AL 测试..\n");
165 {
166 printf(
"按顺序插入弧<%c,%c>、",
'H',
'X');
167 printf(
"<%c,%c>、",
'H',
'C');
168 printf(
"<%c,%c>后,G = \n",
'D',
'H');
169 InsertArc_AL(&G,
'H',
'X');
170 InsertArc_AL(&G,
'H',
'C');
171 InsertArc_AL(&G,
'D',
'H');
172 OutputALGraph(G);
173 printf(
"\n");
174
175 }
176
177 printf(
"13\n函数DeleteArc_AL 测试..\n");
178 {
179 printf(
"删除弧<%c,%c>后,G = \n",
'H',
'X');
180 DeleteArc_AL(&G,
'H',
'X');
181 OutputALGraph(G);
182 printf(
"\n");
183
184 }
185
186 printf(
"13\n函数DeleteArc_AL 测试..\n");
187 {
188 printf(
"删除顶点'%c'后,G = \n",
'H');
189 DeleteVex_AL(&G,
'H');
190 OutputALGraph(G);
191 printf(
"\n");
192
193 }
194
195
196 printf(
"14、15\n函数DFSTraverse_AL 等测试..\n");
197 {
198 printf(
"深度优先遍历图 G= ");
199 DFSTraverse_AL(G);
200 printf(
"\n");
201
202 }
203
204
205 printf(
"16\n函数BFSTraverse_AL 等测试..\n");
206 {
207 printf(
"广度优先遍历图 G= ");
208 BFSTraverse_AL(G);
209 printf(
"\n");
210
211 }
212
213 printf(
"4\n函数ClearGraph_AL 测试..\n");
214 {
215 printf(
"清空图\n");
216 ClearGraph_AL(&
G);
217 OutputALGraph(G);
218 printf(
"\n");
219
220
221 }
222
223 return 0;
224 }
225
226 Status InitQueue_L(LinkQueue *
Q){
227 Q->front=Q->rear=(QueuePtr)
malloc(
sizeof(QNode));
228 if(!Q->
front)
229 exit(ERROR);
230 Q->front->next=
NULL;
231 return OK;
232 }
233
234 Status QueueEmpyt(LinkQueue Q){
235 if(Q.front==
Q.rear)
236 return TRUE;
237 else
238 return FALSE;
239 }
240
241 Status EnQueue_L(LinkQueue *
Q,QElemType_L e){
242 QueuePtr p;
243 p=(QueuePtr)
malloc(
sizeof(QNode));
244 if(!
p)
245 exit(ERROR);
246 p->data=
e;
247 p->next=
NULL;
248 Q->rear->next=
p;
249 Q->rear=
p;
250 return OK;
251
252 }
253
254
255 Status DeQueue_L(LinkQueue *Q,QElemType_L *e){
//从头部删除
256 QueuePtr p;
257 if(Q->front==Q->
rear)
258 return ERROR;
259 p=Q->front->
next;
260 *e=p->
data;
261 Q->front->next=p->
next;
262 if(Q->rear==p)
//如果删除的是队列的最后一个元素，此时对队尾指针进行重新赋值
263 Q->rear=Q->
front;
264 }
265
266
267
268 Status CreateGraph_AL(ALGraph *G,
int r){
269
270 switch(r)
271 {
272 case DG:
273 G->kind=
DG;
274 return CreateDG_AL(G);
275 case UDG:
276 G->kind=
UDG;
277 return CreateUDG_AL(G);
278 default:
279 return ERROR;
280
281 }
282
283 return OK;
284
285
286
287 }
288
289 int LocateVex_AL(ALGraph G,VertexType_AL u)
290 {
291 int i;
292 for(i=
1;i<=G.vexnum;i++
)
293 {
294 if(G.vertices[i].data==
u)
295 return i;
296 }
297 return 0;
298
299 }
300 Status CreateDG_AL(ALGraph *
G){
301 int i,j,k;
302 VertexType_AL v1,v2;
303 ArcNode *
p;
304 ArcNode *r[MAX_VERTEX_NUM+
1];
305 printf(
"输入顶点数 ");
306 scanf(
"%d",&(G->
vexnum));
307 printf(
"输入弧数 ");
308 scanf(
"%d",&(G->
arcnum));
309 printf(
"输入各个顶点值 ");
310 getchar();
311 for(i=
1;i<=G->vexnum;i++
)
312 {
313 scanf(
"%c",&(G->
vertices[i].data));
314 G->vertices[i].firstarc=
NULL;
315 r[i]=
NULL;
316 }
317
318 printf(
"读取各边，制作邻接表\n");
319 for(k=
1;k<=G->arcnum;k++
)
320 {
321 getchar();
322 printf(
"输入相邻结点（添加弧的信息）");
323 scanf(
"%c%c",&v1,&
v2);
324 i=LocateVex_AL(*G,v1);
//第i个结点的链表相连
325 j=LocateVex_AL(*
G,v2);
326 p=(ArcNode*)
malloc(
sizeof(ArcNode));
327 if(!
p)
328 exit(ERROR);
329 p->adjvex=
j;
330 p->nextarc=
NULL;
331 if(r[i]==
NULL)
332 G->vertices[i].firstarc=
p;
333 else
334 r[i]->nextarc=
p;
335 r[i]=p;
//r[i]用来标记链表的最后一个结点指针，起到延长链表添加新的结点的作用
336
337 }
338
339 return OK;
340 }
341 Status CreateUDG_AL(ALGraph *
G){
342 int i,j,k;
343 VertexType_AL v1,v2;
344 ArcNode *p,*
q;
345 ArcNode *r[MAX_VERTEX_NUM+
1];
346 printf(
"输入顶点数 ");
347 scanf(
"%d",&(G->
vexnum));
348 printf(
"输入弧数 ");
349 scanf(
"%d",&(G->
arcnum));
350 printf(
"输入各个顶点值 ");
351 getchar();
352 for(i=
1;i<=G->vexnum;i++
)
353 {
354 scanf(
"%c",&(G->
vertices[i].data));
355 G->vertices[i].firstarc=
NULL;
356 r[i]=
NULL;
357 }
358
359 printf(
"读取各边，制作邻接表\n");
360 for(k=
1;k<=G->arcnum;k++
)
361 {
362 getchar();
363 printf(
"输入相邻结点（添加弧的信息）");
364 scanf(
"%c%c",&v1,&
v2);
365 i=LocateVex_AL(*G,v1);
//第i个结点的链表相连
366 j=LocateVex_AL(*
G,v2);
367 p=(ArcNode*)
malloc(
sizeof(ArcNode));
368 if(!
p)
369 exit(ERROR);
370 p->adjvex=
j;
371 p->nextarc=
NULL;
372 if(r[i]==
NULL)
373 G->vertices[i].firstarc=
p;
374 else
375 r[i]->nextarc=
p;
376 r[i]=p;
//r[i]用来标记链表的最后一个结点指针，起到延长链表添加新的结点的作用
377 q=(ArcNode*)
malloc(
sizeof(ArcNode));
378 if(!
q)
379 exit(ERROR);
380 q->adjvex=
i;
381 q->nextarc=
NULL;
382 if(r[j]==
NULL)
383 G->vertices[j].firstarc=
q;
384 else
385 r[j]->nextarc=
q;
386 r[j]=q;
//i和j轮换对称，上面的方法可以给i添加邻接表，下面的也可以给j按同样的方法添加，只是也就是输入两个结点的时候会同时进行两次操作
387
388
389 }
390
391
392 return OK;
393 }
394
395 void OutputALGraph(ALGraph G){
396 int i,j;
397 ArcNode *
p;
398 if(!G.vexnum&&!
G.arcnum)
399 printf(
"空图！\n");
400 else
401 {
402 for(i=
1;i<=G.vexnum;i++
)
403 {
404 printf(
"%c->",G.vertices[i].data);
405 p=
G.vertices[i].firstarc;
406 while(p)
407 {
408 printf(
" %c",G.vertices[p->
adjvex].data);
409 p=p->
nextarc;
410
411 }
412 printf(
"\n");
413 }
414 }
415 }
416 Status ClearGraph_AL(ALGraph *
G){
417 int i;
418 ArcNode *p,*
q;
419 for(i=
1;i<G->vexnum;i++
)
420 {
421 p=G->
vertices[i].firstarc;
422 while(p)
423 {
424 q=
p;
425 p=p->
nextarc;
426 free(q);
427 }
428 }
429 G->vexnum=
0;
430 G->arcnum=
0;
431 return OK;
432 }
433
434
435 VertexType_AL GetVex_AL(ALGraph G,
int order){
436 if(order>=
1&&order<=
G.vexnum)
437 return G.vertices[order].data;
438 else
439 return '\0';
440
441
442
443 }
444 Status FitstAdjVex_AL(ALGraph G,VertexType_AL u){
445 int k;
446 ArcNode *
p;
447 k=
LocateVex_AL(G,u);
448 if(k&&
G.vertices[k].firstarc)
449 return G.vertices[k].firstarc->
adjvex;
450
451 }
452 Status NextAdjVex_AL(ALGraph G,VertexType_AL v,VertexType_AL w){
453 int k1,k2;
454 ArcNode *p,*
q;
455 k1=
LocateVex_AL(G,v);
456 k2=
LocateVex_AL(G,w);
457
458 if(k1&&
k2)
459 {
460 for(p=G.vertices[k1].firstarc;p;p=p->
nextarc)
461 {
462 if(p->adjvex==
k2)
463 {
464 if(p->
nextarc)
465 return p->nextarc->
adjvex;
466 else
467 return 0;
468
469 }
470
471
472 }
473
474
475 }
476
477 }
478 Status PutVex_AL(ALGraph *
G,VertexType_AL v,VertexType_AL value){
479 int k;
480 k=LocateVex_AL(*
G,v);
481 if(k)
482 {
483 G->vertices[k].data=
value;
484 return OK;
485
486 }
487 else
488 return ERROR;
489
490 }
491
492 Status InsertVex_AL(ALGraph *
G,VertexType_AL v){
493 int i,j,k;
494 if((*G).vexnum==
MAX_VERTEX_NUM)
495 return ERROR;
496 G->vexnum++
;
497 G->vertices[G->vexnum].data=
v;
498 G->vertices[G->vexnum].firstarc=
NULL;
499 return OK;
500 }
501
502 Status InsertArc_AL(ALGraph *
G,VertexType_AL v,VertexType_AL w){
503 int k1,k2;
504 ArcNode *p,*
q;
505 k1=LocateVex_AL(*
G,v);
506 k2=LocateVex_AL(*
G,w);
507
508 p=(ArcNode *)
malloc(
sizeof(ArcNode));
509 if(!
p)
510 exit(ERROR);
511 p->adjvex=k2;
//p的指针指向的结点值为k2
512 q=G->
vertices[k1].firstarc;
513 if(!q||q->adjvex>k2)
//另一个结点的按照大小排列
514 {
515 p->nextarc=G->
vertices[k1].firstarc;
516 G->vertices[k1].firstarc=
p;
517
518 }
519 else
520 {
521 while(q->nextarc&&q->nextarc->adjvex<
k2)
522 q=q->nextarc;
//这个时候q->nextarc->adjvex要大于k2，因此吧k2插到q->nextarc的前面去
523 p->nextarc=q->
nextarc;
524 q->nextarc=
p;
525
526 /*p是新建的结点，而q是旧的结点，这个时候由于q的下一个结点大于k2,并且q小于k2所以这个时候将p的next指向q的next
527 然后吧q的next指向p，也就相当于找到了在q,和q->next中间的一个值*/
528
529 }
530 if(G->kind==
UDG)
531 {
532 p=(ArcNode *)
malloc(
sizeof(ArcNode));
533 if(!
p)
534 exit(ERROR);
535 p->adjvex=
k1;
536 q=G->
vertices[k2].firstarc;
537 if(!q||q->adjvex>
k1)
538 {
539 p->nextarc=G->
vertices[k2].firstarc;
540 G->vertices[k2].firstarc=
p;
541
542 }
543 else
544 {
545 while(q->nextarc&&q->nextarc->adjvex<
k1)
546 q=q->
nextarc;
547 p->nextarc=q->
nextarc;
548 q->nextarc=
p;
549
550 }
551
552 }
553
554 return OK;
555
556
557
558 }
559 Status DeleteArc_AL(ALGraph *
G,VertexType_AL v,VertexType_AL w){
560 int k1,k2;
561 ArcNode *p,*
q;
562 k1=LocateVex_AL(*
G,v);
563 k2=LocateVex_AL(*
G,w);
564
565 p=G->
vertices[k1].firstarc;
566 if(p&&p->adjvex==
k2)
567 {
568 G->vertices[k1].firstarc=p->
nextarc;
569 free(p);
570 }
571 else
572 {
573 while(p&&p->adjvex!=
k2)
574 {
575 q=p;
//标记找到的时候的前一个位置
576 p=p->
nextarc;
577 }
578 if(!
p)
579 return ERROR;
580 else //这个时候p->adjvex=k2;
581 {
582 q->nextarc=p->nextarc;
//将p直接跳过
583 free(p);
584
585 }
586 }
587 if(G->kind==
UDG)
588 {
589 p=G->
vertices[k2].firstarc;
590 if(p&&p->adjvex==
k1)
591 {
592 G->vertices[k2].firstarc=p->
nextarc;
593 free(p);
594 }
595 else
596 {
597 while(p&&p->adjvex!=
k1)
598 {
599 q=
p;
600 p=p->
nextarc;
601 }
602 if(!
p)
603 return ERROR;
604 else
605 {
606 q->nextarc=p->
nextarc;
607 free(p);
608
609 }
610
611 }
612 }
613 return OK;
614 }
615
616 Status DeleteVex_AL(ALGraph *
G,VertexType_AL v){
617 int i,k;
618 ArcNode *p,*
q;
619 k=LocateVex_AL(*
G,v);
620 if(!
k)
621 return ERROR;
622 p=G->
vertices[k].firstarc;
623 while(p)
//先将结点所在的本条的弧全部删除使G->vertices[k].firstarc=NULL；
624 {
625 q=
p;
626 p=p->
nextarc;
627 DeleteArc_AL(G,v,G->vertices[q->
adjvex].data);
628 }
629 for(i=k+
1;i<=G->vexnum;i++)
//移动结点
630 {
631 G->vertices[i-
1].data=G->
vertices[i].data;
632 G->vertices[i-
1].firstarc=G->
vertices[i].firstarc;
633 }
634 G->vexnum--
;
635 if(G->kind==
DG)
636 {
637 for(i=
1;i<=G->vexnum;i++
)
638 {
639 p=G->
vertices[i].firstarc;
640 while(p&&p->adjvex<
k)
641 {
642 q=
p;
643 p=p->
nextarc;
644
645 }
646 if(p)
647 {
648 if(p->adjvex==
k)
649 {
650 if(p==G->
vertices[i].firstarc)
651 G->vertices[i].firstarc=p->
nextarc;
652 else
653 q->nextarc=p->
nextarc;
654 free(p);
655 G->arcnum--
;
656
657
658 }
659
660 }
661 }
662 }
663
664 return OK;
665 }
666
667 void DFSTraverse_AL(ALGraph G){
668 int v;
669 for(v=
1;v<=G.vexnum;v++
)
670 {
671 visited[v]=
FALSE;
672 }
673 for(v=
1;v<=G.vexnum;v++
)
674 {
675 if(!
visited[v])
676 DFS_AL(G,v);
677
678
679 }
680
681 }
682 void DFS_AL(ALGraph G,
int v){
683 int w;
684 ArcNode *
p;
685 visited[v]=
TRUE;
686 printf(
"%c ",G.vertices[v].data);
687
688 p=
G.vertices[v].firstarc;
689 for(;p;p=p->
nextarc)
690 {
691 w=p->
adjvex;
692 if(!
visited[w])
693 DFS_AL(G,w);
694
695 }
696
697 }
698
699 /*****************************************************************************************************************
700 *利用队列的先进先出来暂时储存访问的结点。最一开始从序号为1的结点出发，这个时候将1放入队列，这个标记着，队列中有 *
701 *一个元素需要被访问，然后进入循环首先将这个元素删除，因为代表已经进来访问了，然后一次遍历这个元素的邻接点，并将其*
702 *依次放入队列中并且对它们的值进行分别的输出，然后退出循环，进入队列中的下一个元素，直到队列中所有的元素都背访问过*
703 *意味着这个时候和第一个结点（序号为1有关的结点都已经访问完毕）防止有与其不想连的结点存在，在外面套一个for循环遍历*
704 ******************************************************************************************************************/
705 void BFSTraverse_AL(ALGraph G){
706 int v,w;
707 LinkQueue Q;
708 QElemType_L e;
709 ArcNode *
p;
710 for(v=
1;v<=G.vexnum;v++)
//初始化
711 visited[v]=
FALSE;
712 InitQueue_L(&
Q);
713 for(v=
1;v<=G.vexnum;v++
)
714 {
715 if(!
visited[v])
716 {
717 visited[v]=
TRUE;
718 printf(
"%c ",G.vertices[v].data);
719 EnQueue_L(&
Q,v);
720 while(!
QueueEmpyt(Q))
721 {
722 DeQueue_L(&Q,&
e);
723 p=
G.vertices[e].firstarc;
724
725 for(;p;p=p->
nextarc)
726 {
727 w=p->
adjvex;
728 if(!
visited[w])
729 {
730 visited[w]=
TRUE;
731 printf(
"%c ",G.vertices[w].data);
732 EnQueue_L(&
Q,w);
733
734 }
735 }
736 }
737 }
738 }
739 }
740
741
742 //出现一直在输入没有继续说明出现了死循环，特别是循环的退出条件要注意
参考：http://www.cnblogs.com/kangjianwei101/p/5222014.html
转载于:https://www.cnblogs.com/lovecodepql/p/7742967.html
相关资源：图的遍历邻接表存储
