數(shù)據(jù)結構-試驗8-圖的基本操作

1、1 .實驗題目圖的基本操作2 .實驗目的1)掌握圖的鄰接矩陣、鄰接表的表示方法。2)掌握建立圖的鄰接矩陣的算法。3)掌握建立圖的鄰接表的算法。4)加深對圖的理解，逐步培養(yǎng)解決實際問題的編程能力3 .需求分析(1)編寫圖基本操作函數(shù)。建立圖的鄰接表，鄰接矩陣鄰接表表示的圖的遞歸深度優(yōu)先遍歷鄰接矩陣表示的圖的遞歸深度優(yōu)先遍歷鄰接表表示的圖的廣度優(yōu)先遍歷鄰接矩陣表示的圖的廣度優(yōu)先遍歷Create_Graph(LGraphlg.MGraphmg)LDFS(LGraphg,inti)MDFS(MGraphg,inti,intvn)LBFS(LGraphg,ints,intn)MBFS(MGraphg,i

2、nts,intn)(2)調用上述函數(shù)實現(xiàn)下列操作。建立一個圖的鄰接矩陣和圖的鄰接表。采用遞歸深度優(yōu)先遍歷輸出圖的鄰接矩陣采用遞歸深度優(yōu)先遍歷輸出圖的鄰接表。采用圖的廣度優(yōu)先調歷輸出圖的鄰接表。采用圖的廣度優(yōu)先遍歷輸出圖的鄰接矩陣4.概要設計(1)結構體typedefstructcharvexsMAX_VERTEX_NUM;/頂點向量intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣intvexnum,arcnum;/圖當前頂點數(shù)和弧數(shù)MGraph;typedefstructArcNodeintadjvex;/該弧所指向的頂點的位置福建師范大學物光院計算機教學輔導

3、講義structArcNode*nextarc;/指向下一條弧的指針ArcNode;/頂點信息typedefstructVNodechardata;ArcNode*firstarc;/指向第一條依附該頂點的弧的指針VNode,AdjListMAX_VERTEX_NUM;typedefstructAdjListvertices;intvexnum,arcnum;/圖當前頂點數(shù)和弧數(shù)LGraph;typedefstructQueueintarryMAX_VERTEX_NUM;intfront,rear;Queue;(2)本程序主要包含6個函數(shù):主函數(shù)main()建立圖的鄰接矩陣，鄰接表鄰接表表示的

4、圖的遞歸深度優(yōu)先遍歷鄰接矩陣表示的圖的遞歸深度優(yōu)先遍歷鄰接表表示的圖的廣度優(yōu)先遍歷鄰接矩陣表示的圖的廣度優(yōu)先遍歷各函數(shù)間調用關系如下：Create_Graph()LDFS()MDFS()LBFS()MBFS()2Dreate_Graph()LDFS()福建師范大學物光院計算機教學輔導講義(3)主函數(shù)的偽碼main()(定義鄰接矩陣和鄰接表；建立鄰接矩陣和鄰接表；鄰接矩陣MDFS深度優(yōu)先遍歷;鄰接矩陣MBFS廣度優(yōu)先遍歷鄰接表LDFS深度優(yōu)先遍歷；鄰接表LBFS廣度優(yōu)先遍歷)5詳細設計#include<stdio.h>#include<malloc.h>#include&

5、lt;stddef.h>#include<math.h>#defineOK1#defineERROR0#defineMAX_VERTEX_NUM33intvisitedMAX_VERTEX_NUM;typedefstruct(/圖當前頂點數(shù)和弧數(shù)intvexnum,arcnum;福建師范大學物光院計算機教學輔導講義charvexsMAX_VERTEX_NUM;/頂點向量intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣MGraph;typedefstructArcNodeintadjvex;structArcNode*nextarc;ArcNo

6、de;typedefstructVNodechardata;ArcNode*firstarc;VNode,AdjListMAX_VERTEX_NUM;typedefstructAdjListvertices;intvexnum,arcnum;LGraph;typedefstructQueueintarryMAX_VERTEX_NUM;intfront,rear;福建師范大學物光院計算機教學輔導講義Queue;QueueQ;voidInitQueue()(Q.front=Q.rear=0;intQueueEmpty(Queue*Q)(if(Q->front=Q->rear)retur

7、n1;elsereturn0;voidEnQueue(Queue*Q,intw)(if(Q->rear+1)%MAX_VERTEX_NUM=Q->front)printf("Error!");else(Q->arryQ->rear=w;Q->rear=(Q->rear+1)%MAX_VERTEX_NUM福建師范大學物光院計算機教學輔導講義)intDeQueue(Queue*Q)(intu;if(Q->front=Q->rear)return-1;u=Q->front;Q->front=(Q->front+1)

8、%MAX_VERTEX_NUMreturnu;)intLocatevex(MGraph*Mg,charv)(inti;for(i=0;Mg->vexsi!=v;i+);if(i>Mg->vexnum)printf("ERROR");returni;)intCreate_Graph(MGraph*Mg,LGraph*Lg)(inti,j,k;charv1,v2;ArcNode*q,*p;福建師范大學物光院計算機教學輔導講義printf("輸入圖的頂點數(shù)和弧數(shù)：");scanf("%d%d",&Mg->ve

9、xnum,&Mg->arcnum);getchar();Lg->vexnum=Mg->vexnum;Lg->arcnum=Mg->arcnum;for(i=0;i<Mg->vexnum;i+)printf("請輸入一個字符彳為圖的頂點：")；scanf("%c",&Mg->vexsi);getchar();Lg->verticesi.data=Mg->vexsi;Lg->verticesi.firstarc=NULL;for(i=0;i<Mg->vexnum;i

10、+)for(j=0;j<Mg->vexnum;j+)Mg->acrsij=0;for(k=0;k<Mg->arcnum;k+)printf（"請輸入一條邊連接的2個頂點："）;福建師范大學物光院計算機教學輔導講義scanf("%c%c",&v1,&v2);getchar();i=Locatevex(Mg,v1);j=Locatevex(Mg,v2);Mg->acrsji=Mg->acrsij=1;p=(ArcNode*)malloc(sizeof(ArcNode);p->adjvex=i;p

11、->nextarc=Lg->verticesj.firstarc;Lg->verticesj.firstarc=p;q=(ArcNode*)malloc(sizeof(ArcNode);q->adjvex=j;q->nextarc=Lg->verticesi.firstarc;Lg->verticesi.firstarc=q;returnOK;intLAdjVex(LGraph*Lg,intk)ArcNode*p;for(p=Lg->verticesk.firstarc;p!=NULL;p=p->nextarc)if(!visitedp-&

12、gt;adjvex)returnp->adjvex;福建師范大學物光院計算機教學輔導講義return-1;)voidLDFS(LGraph*Lg,inti)(intk;visitedi=OK;printf("%c",Lg->verticesi.data);Lg,k)for(k=LAdjVex(Lg,i);k>=0;k=LAdjVex(if(!visitedk)LDFS(Lg,k);)intAdjVes(MGraph*Mg,intk)(inti;for(i=0;i<Mg->vexnum;i+)if(Mg->acrski&&(

13、!visitedi)returni;return-1;)voidMDFS(MGraph*Mg,inti)(intk;福建師范大學物光院計算機教學輔導講義visitedi=1;printf("%c",Mg->vexsi);for(k=AdjVes(Mg,i);k>=0;k=AdjVes(Mg,k)if(!visitedk)MDFS(Mg,k);/遞歸voidLBFS(LGraph*Lg)(inti,u,w;for(i=0;i<Lg->vexnum;+i)visitedi=0;InitQueue();for(i=0;i<Lg->vexnum;

14、+i)if(!visitedi)(visitedi=1;printf("%c",Lg->verticesi.data);EnQueue(&Q,i);while(!QueueEmpty(&Q)(u=DeQueue(&Q);Lg,u)for(w=LAdjVex(Lg,u);w>=0;w=LAdjVex(if(!visitedw)10福建師范大學物光院計算機教學輔導講義(visitedw=1;printf("%c",Lg->verticesw.data);EnQueue(&Q,w);voidMBFS(MGrap

15、h*Mg)(inti,w,u;for(i=0;i<Mg->vexnum;i+)visitedi=0;InitQueue();for(i=0;i<Mg->vexnum;+i)if(!visitedi)/沒被訪問過(visitedi=1;printf("%c",Mg->vexsi);EnQueue(&Q,i);while(!QueueEmpty(&Q)(u=DeQueue(&Q);11福建師范大學物光院計算機教學輔導講義for(w=AdjVes(Mg,u);w>=0;w=AdjVes(Mg,u)if(!visitedw

16、)/沒被訪問過(visitedw=1;printf("%c",Mg->vexsw);EnQueue(&Q,w);/入隊voidmain()(inti;MGraphMg;LGraphLg;Create_Graph(&Mg,&Lg);printf("鄰接表深度優(yōu)先遍歷LDFS:t");for(i=0;i<Lg.vexnum;+i)visitedi=0;for(i=0;i<Lg.vexnum;+i)if(!visitedi)LDFS(&Lg,i);printf("n");12福建師范大學物光院計算機教學輔導講義printf("鄰接矩陣深度優(yōu)先遍歷MDFS:t");for(i=0;i<Mg.vexnum;i+)visitedi=0;for(i=0;i<Mg.vexnum;i+)if(!visitedi)MDFS(&Mg,i);printf("n鄰接表廣度優(yōu)先遍歷LBFS:t"