数据结构(B)上机实验四-图

数据结构(B)上机实验四--图数据结构上机实验六实验内容:图的基本操作实验要求:1)图的遍历与基本操作要作为函数被调用.2)把自己使用的图结构明确的表达出来.3)基本上实现每个实验题目的要求.分组要求：可单独完成，也可两人一组。实验目的:1)熟悉C/C++基本编程,培养动手能力.2)通过实验,加深对图的理解.评分标准：1)只完成第一和第二题，根据情况得4，5分；2）完成前3题，根据情况得5，6分；3）在2）基础上，选做四）中题目，根据情况得7到10分。 题目:一)建立一个无向图+遍历+插入(1)以数组表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图；(2)对（1）中生成的无向图进行广度优先遍历并打印结果；(3)向（1）中生成的无向图插入一条新弧并打印结果；二)建立一个有向图+遍历+插入+删除(1)以邻接表作为图的存储结构，从键盘输入图的顶点与弧的信息建立一个有向图；(2)对（1）中生成的有向图进行深度优先遍历并打印结果；(3)在（1）中生成的有向图中，分别插入与删除一条弧并打印其结果；(4)在（1）中生成的有向图中，分别插入与删除一个顶点并打印结果；(5)在（1）中生成的有向图中,各顶点的入度与出度并打印结果；三）基本应用题（1）编写算法，判断图中指定的两个顶点是否连通。（2）编写算法，判断图的连通性。如果不连通，求连通分量的个数（3）编写算法，判断图中任意两个顶点的连通性（4）编写算法，判断图中是否存在回路。（5）实现图的广度优先搜索算法。四）高级应用题（1）实现Prim算法（2）实现Kruskal算法（3）实现迪杰斯特拉算法（4）实现拓扑排序算法（5）实现关键路径算法数据结构(B)上机实验四--图全文共15页，当前为第1页。数据结构(B)上机实验四--图全文共15页，当前为第1页。一)建立一个无向图+遍历+插入(1)以数组表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图；(2)对（1）中生成的无向图进行广度优先遍历并打印结果；(3)向（1）中生成的无向图插入一条新弧并打印结果；#include<stdio.h>#include<string.h>#include<malloc.h>#include<stdlib.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2#defineMAX_NAME5/*顶点字符串的最大长度+1*/#defineMAX_INFO20/*相关信息字符串的最大长度+1*/#defineINFINITYINT_MAX/*用整型最大值代替∞*/#defineMAX_VERTEX_NUM20/*最大顶点个数*/typedefintBoolean;Booleanvisited[MAX_VERTEX_NUM];/*访问标志数组(全局量)*/typedefintStatus;typedefintVRType;typedefcharInfoType;typedefcharVertexType[MAX_NAME];typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图,有向网,无向图,无向网}*/typedefstruct{ VRTypeadj;/*顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；*/ /*对带权图，c则为权值类型*/InfoType*info;/*该弧相关信息的指针(可无)*/}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*图的当前顶点数和弧数*/GraphKindkind;/*图的种类标志*/}MGraph;intLocateVex(MGraphG,VertexTypeu){/*初始条件:图G存在,u和G中顶点有相同特征*//*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/数据结构(B)上机实验四--图全文共15页，当前为第2页。 inti;数据结构(B)上机实验四--图全文共15页，当前为第2页。for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i])==0) returni; return-1;}StatusCreateAG(MGraph&G){/*采用数组(邻接矩阵)表示法,构造无向图G*/inti,j,k,l,IncInfo;charch,s[MAX_INFO],*info;VertexTypeva,vb;printf("请输入无向图G的顶点数,边数,边是否含其它信息(是:1,否:0):");scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);for(i=0;i<G.vexnum;++i)/*构造顶点向量*/ scanf("%s",G.vexs[i]);for(i=0;i<G.vexnum;++i)/*初始化邻接矩阵*/for(j=0;j<G.vexnum;++j) { G.arcs[i][j].adj=0;/*图*/ G.arcs[i][j].info=NULL; }printf("请输入%d条边的顶点1顶点2(以空格作为间隔):\n",G.arcnum);for(k=0;k<G.arcnum;++k){ scanf("%s",va); scanf("%s",vb); ch=getchar();i=LocateVex(G,va);j=LocateVex(G,vb);G.arcs[i][j].adj=G.arcs[j][i].adj=1;/*无向图*/if(IncInfo) { printf("请输入该边的相关信息(<%d个字符):",MAX_INFO);scanf("%s",s);l=strlen(s);if(l) { info=(char*)malloc((l+1)*sizeof(char)); strcpy(info,s); G.arcs[i][j].info=G.arcs[j][i].info=info;/*无向*/ } } if(k<G.arcnum-1) printf("请输入下一条边的顶点1顶点2：\n"); }G.kind=AG;returnOK;}数据结构数据结构(B)上机实验四--图全文共15页，当前为第3页。typedefVRTypeQElemType;/*队列类型*/typedefstructQNode{ QElemTypedata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront,rear;/*队头、队尾指针*/}LinkQueue;StatusInitQueue(LinkQueue*Q){/*构造一个空队列Q*/ (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if(!(*Q).front) exit(OVERFLOW); (*Q).front->next=NULL; returnOK;}StatusQueueEmpty(LinkQueueQ){/*若Q为空队列,则返回TRUE,否则返回FALSE*/ if(Q.front==Q.rear) returnTRUE; else returnFALSE;}StatusEnQueue(LinkQueue*Q,QElemTypee){/*插入元素e为Q的新的队尾元素*/ QueuePtrp=(QueuePtr)malloc(sizeof(QNode)); if(!p)/*存储分配失败*/ exit(OVERFLOW); p->data=e; p->next=NULL; (*Q).rear->next=p; (*Q).rear=p; returnOK;}StatusDeQueue(LinkQueue*Q,QElemType*e){/*若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/ QueuePtrp; if((*Q).front==(*Q).rear) returnERROR; p=(*Q).front->next;数据结构(B)上机实验四--图全文共15页，当前为第4页。数据结构(B)上机实验四--图全文共15页，当前为第4页。 (*Q).front->next=p->next; if((*Q).rear==p) (*Q).rear=(*Q).front; free(p); returnOK;}voidVisit(VertexTypeV){ printf("%s ",V);}intFirstAdjVex(MGraphG,VertexTypev){/*初始条件:图G存在,v是G中某个顶点*//*操作结果:返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1*/ inti,j=0,k; k=LocateVex(G,v);/*k为顶点v在图G中的序号*/ for(i=0;i<G.vexnum;i++) if(G.arcs[k][i].adj!=j) returni; return-1;}intNextAdjVex(MGraphG,VertexTypev,VertexTypew){/*初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点*//*操作结果:返回v的(相对于w的)下一个邻接顶点的序号,*//*若w是v的最后一个邻接顶点,则返回-1*/ inti,j=0,k1,k2; k1=LocateVex(G,v);/*k1为顶点v在图G中的序号*/ k2=LocateVex(G,w);/*k2为顶点w在图G中的序号*/ for(i=k2+1;i<G.vexnum;i++) if(G.arcs[k1][i].adj!=j) returni; return-1;}VertexType*GetVex(MGraphG,intv){/*初始条件:图G存在，v是G中某个顶点的序号。操作结果:返回v的值*/ if(v>=G.vexnum||v<0) exit(ERROR); return&G.vexs[v];}voidBFSTraverse(MGraphG){/*初始条件:图G存在,Visit是顶点的应用函数。算法7.6*//*操作结果:从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数*//*Visit一次且仅一次。一旦Visit()失败,则操作失败。*//*使用辅助队列Q和访问标志数组visited*/数据结构(B)上机实验四--图全文共15页，当前为第5页。数据结构(B)上机实验四--图全文共15页，当前为第5页。 VertexTypew1,u1; LinkQueueQ; for(v=0;v<G.vexnum;v++) visited[v]=FALSE;/*置初值*/ InitQueue(&Q);/*置空的辅助队列Q*/ printf("按广度优先遍历图：\n"); for(v=0;v<G.vexnum;v++) if(!visited[v])/*v尚未访问*/ { visited[v]=TRUE;/*设置访问标志为TRUE(已访问)*/ Visit(G.vexs[v]); EnQueue(&Q,v);/*v入队列*/ while(!QueueEmpty(Q))/*队列不空*/ { DeQueue(&Q,&u);/*队头元素出队并置为u*/ strcpy(u1,*GetVex(G,u)); for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w)))) if(!visited[w])/*w为u的尚未访问的邻接顶点的序号*/ { visited[w]=TRUE; Visit(G.vexs[w]); EnQueue(&Q,w); } } } printf("\n");}StatusInsertArc(MGraph&G,VertexTypev,VertexTypew){/*初始条件:图G存在,v和W是G中两个顶点*//*操作结果:在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>*/ inti,l,v1,w1; char*info,s[MAX_INFO]; v1=LocateVex(G,v);/*尾*/ w1=LocateVex(G,w);/*头*/ if(v1<0||w1<0) returnERROR; G.arcnum++;/*弧或边数加1*/ G.arcs[v1][w1].adj=1; printf("是否有该弧或边的相关信息(0:无1:有):"); scanf("%d%*c",&i); if(i) { printf("请输入该弧或边的相关信息(<%d个字符)：",MAX_INFO); gets(s); l=strlen(s); if(l) {数据结构(B)上机实验四--图全文共15页，当前为第6页。数据结构(B)上机实验四--图全文共15页，当前为第6页。 strcpy(info,s); G.arcs[v1][w1].info=info; } } G.arcs[w1][v1].adj=G.arcs[v1][w1].adj;G.arcs[w1][v1].info=G.arcs[v1][w1].info;/*指向同一个相关信息*/ returnOK;}voidDisplay(MGraphG){/*输出邻接矩阵G*/ inti,j; chars[7],s1[3]; switch(G.kind) { caseDG:strcpy(s,"有向图\0"); strcpy(s1,"弧\0"); break; caseDN:strcpy(s,"有向网\0");strcpy(s1,"弧\0");break; caseAG:strcpy(s,"无向图\0");strcpy(s1,"边\0");break; caseAN:strcpy(s,"无向网\0");strcpy(s1,"边\0"); } printf("%d个顶点%d条%s的%s\n",G.vexnum,G.arcnum,s1,s); for(i=0;i<G.vexnum;++i)/*输出G.vexs*/ printf("G.vexs[%d]=%s\n",i,G.vexs[i]);printf("G.arcs.adj:\n");/*输出G.arcs.adj*/for(i=0;i<G.vexnum;i++){ for(j=0;j<G.vexnum;j++) printf("%6d",G.arcs[i][j].adj); printf("\n"); } printf("G.:\n");/*输出G.*/ printf("顶点1(弧尾)顶点2(弧头)该%s信息：\n",s1); for(i=0;i<G.vexnum;i++) for(j=i+1;j<G.vexnum;j++) if(G.arcs[i][j].info) printf("%5s%11s%s\n",G.vexs[i],G.vexs[j],G.arcs[i][j].info);}voidmain(){数据结构(B)上机实验四--图全文共15页，当前为第7页。数据结构(B)上机实验四--图全文共15页，当前为第7页。VertexTypeva,vb; MGraphG; CreateAG(G); Display(G); printf("\n"); BFSTraverse(G); printf("\n"); printf("请输入要插入的弧所连接的顶点："); scanf("%s",va); scanf("%s",vb); //ch=getchar(); InsertArc(G,va,vb); Display(G); printf("\n"); BFSTraverse(G);}二)建立一个有向图+遍历+插入+删除(1)以邻接表作为图的存储结构，从键盘输入图的顶点与弧的信息建立一个有向图；(2)对（1）中生成的有向图进行深度优先遍历并打印结果；(3)在（1）中生成的有向图中，分别插入与删除一条弧并打印其结果；(4)在（1）中生成的有向图中，分别插入与删除一个顶点并打印结果；(5)在（1）中生成的有向图中,各顶点的入度与出度并打印结果；#include<stdio.h>#include<string.h>#include<malloc.h>#include<stdlib.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2#defineMAX_VERTEX_NUM20#defineMAX_NAME5/*顶点字符串的最大长度+1*/typedefintBoolean;Booleanvisited[MAX_VERTEX_NUM];/*访问标志数组(全局量)*/typedefintStatus;typedefintVRType;typedefcharInfoType;typedefcharVertexType[MAX_NAME];typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图,有向网,无向图,无向网}*/typedefstructArcNode{ intadjvex;/*该弧所指向的顶点的位置*/ structArcNode*nextarc;/*指向下一条弧的指针*/ InfoType*info;/*网的权值指针）*/}ArcNode;数据结构(B)上机实验四--图全文共15页，当前为第8页。数据结构(B)上机实验四--图全文共15页，当前为第8页。{ VertexTypedata;/*顶点信息*/ ArcNode*firstarc;/*第一个表结点的地址,指向第一条依附该顶点的弧的指针*/}VNode,AdjList[MAX_VERTEX_NUM];/*头结点*/typedefstruct{ AdjListvertices; intvexnum,arcnum;/*图的当前顶点数和弧数*/ intkind;/*图的种类标志*/}ALGraph;intLocateVex(ALGraphG,VertexTypeu){/*初始条件:图G存在,u和G中顶点有相同特征*//*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/ inti; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vertices[i].data)==0) returni; return-1;}StatusCreateGraph(ALGraph&G){/*采用邻接表存储结构,构造没有相关信息的有向图G*/ inti,j,k; VertexTypeva,vb; ArcNode*p; G.kind=0; printf("请输入图的顶点数,边数:"); scanf("%d%d",&G.vexnum,&G.arcnum); printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME); for(i=0;i<G.vexnum;++i)/*构造顶点向量*/ { scanf("%s",G.vertices[i].data); G.vertices[i].firstarc=NULL; }printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n"); for(k=0;k<G.arcnum;++k)/*构造表结点链表*/ { scanf("%s%s",va,vb); i=LocateVex(G,va);/*弧尾*/ j=LocateVex(G,vb);/*弧头*/ p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=NULL; if(G.vertices[i].firstarc==NULL) {数据结构(B)上机实验四--图全文共15页，当前为第9页。数据结构(B)上机实验四--图全文共15页，当前为第9页。 G.vertices[i].firstarc=p; } else { p->nextarc=G.vertices[i].firstarc->nextarc; G.vertices[i].firstarc->nextarc=p; } if(k<G.arcnum-1) printf("请输入下一条弧的弧尾和弧头(以空格作为间隔):\n"); } returnOK;}VertexType*GetVex(ALGraphG,intv){/*初始条件:图G存在,v是G中某个顶点的序号。操作结果:返回v的值*/ if(v>=G.vexnum||v<0) exit(ERROR); return&G.vertices[v].data;}intFirstAdjVex(ALGraphG,VertexTypev){/*初始条件:图G存在,v是G中某个顶点*//*操作结果:返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1*/ ArcNode*p; intv1; v1=LocateVex(G,v);/*v1为顶点v在图G中的序号*/ p=G.vertices[v1].firstarc; if(p) returnp->adjvex; else return-1;}intNextAdjVex(ALGraphG,VertexTypev,VertexTypew){/*初始条件:图G存在,v是G中某个顶点,w是v的邻接顶点*//*操作结果:返回v的(相对于w的)下一个邻接顶点的序号。*//*若w是v的最后一个邻接点,则返回-1*/ ArcNode*p; intv1,w1; v1=LocateVex(G,v);/*v1为顶点v在图G中的序号*/ w1=LocateVex(G,w);/*w1为顶点w在图G中的序号*/ p=G.vertices[v1].firstarc; while(p&&p->adjvex!=w1)/*指针p不空且所指表结点不是w*/ p=p->nextarc; if(!p||!p->nextarc)/*没找到w或w是最后一个邻接点*/ return-1; else/*p->adjvex==w*/ returnp->nextarc->adjvex;/*返回v的(相对于w的)下一个邻接顶点的序号*/数据结构(B)上机实验四--图全文共15页，当前为第10页。数据结构(B)上机实验四--图全文共15页，当前为第10页。voidVisitFunc(VertexTypev){ printf("%s ",v);}voidDFS(ALGraphG,intv){/*从第v个顶点出发递归地深度优先遍历图G*/ intw; VertexTypev1,w1; strcpy(v1,*GetVex(G,v)); visited[v]=TRUE;/*设置访问标志为TRUE(已访问)*/ VisitFunc(G.vertices[v].data);/*访问第v个顶点*/ for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w)))) if(!visited[w]) DFS(G,w);/*对v的尚未访问的邻接点w递归调用DFS*/}voidDFSTraverse(ALGraphG){/*对图G作深度优先遍历。算法7.4*/ printf("深度优先遍历图：\n"); intv; for(v=0;v<G.vexnum;v++) visited[v]=FALSE;/*访问标志数组初始化*/ for(v=0;v<G.vexnum;v++) if(!visited[v]) DFS(G,v);/*对尚未访问的顶点调用DFS*/ printf("\n");}StatusInsertArc(ALGraph&G,VertexTypev,VertexTypew){/*初始条件:图G存在,v和w是G中两个顶点*//*操作结果:在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>*/ ArcNode*p; inti,j; i=LocateVex(G,v);/*弧尾或边的序号*/ j=LocateVex(G,w);/*弧头或边的序号*/ if(i<0||j<0) returnERROR; G.arcnum++;/*图G的弧或边的数目加1*/ p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=NULL; if(G.vertices[i].firstarc==NULL) { p->nextarc=G.vertices[i].firstarc;/*插在表头*/ G.vertices[i].firstarc=p; }数据结构(B)上机实验四--图全文共15页，当前为第11页。数据结构(B)上机实验四--图全文共15页，当前为第11页。 { p->nextarc=G.vertices[i].firstarc->nextarc; G.vertices[i].firstarc->nextarc=p; } returnOK;}StatusDeleteArc(ALGraph&G,VertexTypev,VertexTypew){/*初始条件:图G存在,v和w是G中两个顶点*//*操作结果:在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>*/ ArcNode*p,*q; inti,j; i=LocateVex(G,v);/*i是顶点v(弧尾)的序号*/ j=LocateVex(G,w);/*j是顶点w(弧头)的序号*/ if(i<0||j<0||i==j) returnERROR; p=G.vertices[i].firstarc;/*p指向顶点v的第一条出弧*/ while(p&&p->adjvex!=j)/*p不空且所指之弧不是待删除弧<v,w>*/ {/*p指向下一条弧*/ q=p; p=p->nextarc; } if(p&&p->adjvex==j)/*找到弧<v,w>*/ { if(p==G.vertices[i].firstarc)/*p所指是第1条弧*/ G.vertices[i].firstarc=p->nextarc;/*指向下一条弧*/ else q->nextarc=p->nextarc;/*指向下一条弧*/ free(p);/*释放此结点*/ G.arcnum--;/*弧或边数减1*/ } returnOK;}voidInsertVex(ALGraph&G,VertexTypev){/*初始条件:图G存在,v和图中顶点有相同特征*//*操作结果:在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)*/ strcpy(G.vertices[G.vexnum].data,v);/*构造新顶点向量*/ G.vertices[G.vexnum].firstarc=NULL; G.vexnum++;/*图G的顶点数加1*/}StatusDeleteVex(ALGraph&G,VertexTypev){/*初始条件:图G存在,v是G中某个顶点*//*操作结果:删除G中顶点v及其相关的弧*/ inti,j; ArcNode*p,*q; j=LocateVex(G,v);/*j是顶点v的序号*/ if(j<0)/*v不是图G的顶点*/数据结构(B)上机实验四--图全文共15页，当前为第12页。数据结构(B)上机实验四--图全文共15页，当前为第12页。 p=G.vertices[j].firstarc;/*删除以v为出度的弧或边*/ while(p) { q=p; p=p->nextarc; free(q); G.arcnum--;/*弧或边数减1*/ } G.vexnum--;/*顶点数减1*/ for(i=j;i<G.vexnum;i++)/*顶点v后面的顶点前移*/ G.vertices[i]=G.vertices[i+1]; for(i=0;i<G.vexnum;i++)/*删除以v为入度的弧或边且必要时修改表结点的顶点位置值*/ { p=G.vertices[i].firstarc;/*指向第1条弧或边*/ while(p)/*有弧*/ { if(p->adjvex==j) { if(p==G.vertices[i].firstarc)/*待删结点是第1个结点*/ {