图建立及应用

《图建立及应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验4图的遍历及应用一、实验目的1)掌握图的邻接矩阵存储；2)利用邻接矩阵存储图；3)掌握图的邻接表存储；4)利用邻接表存储图并实现图的遍历；二、实验内容已知图1，分别用邻接矩阵，邻接表表示两种表示法创建g1,g2.DA30101Edges=1011BC01001001图1无向图无向图对应的邻接表表示如下图所示：序号0A13∧B1023∧∧112CD301∧一个无向图的邻接表表示1、利用邻接矩阵存储图1。要求：数据元素类型ElemType取char。实现如下算法：1）利用邻接矩阵存储一个图；2、利用邻接表存储图1并实现图的遍历。要求：数据元素类

2、型ElemType取char。实现如下算法：1）利用邻接表存储一个图；2）输出邻接表；编程代码如下:#include#includeusingnamespacestd;#defineMAXV30typedefcharElemType;typedefstruct{intno;ElemTypedata;}VertexType;typedefstruct{intedges[MAXV][MAXV];intvexnum,arcnum;VertexTypevexs[MAXV];}MGraph;voidCreateMGr

3、aph(MGraph*G){inti;printf("利用邻接矩阵创建图输入顶点数:");scanf("%d",&G->vexnum);printf("请输入顶点：");for(i=0;ivexnum;i++){scanf("%c",&G->vexs[i].data);}printf("输入边数:");fflush(stdin);scanf("%d",&G->arcnum);for(i=0;ivexnum;i++){for(intj=0;jvexnum;j++){G->edges[i][j]=0;}}for(

4、intk=0;karcnum;k++){inti,j;printf("输入边（vi,vj）上的下标i,下标j");scanf("%d,%d",&i,&j);G->edges[j][i]=G->edges[i][j]=1;}}voidprintfMG(MGraph*G){printf("输出邻接矩阵");for(inti=0;ivexnum;i++){for(intj=0;jvexnum;j++){if(i==j)printf("0");elseprintf("%d",G->edges[i][j]);}printf

5、("");}}typedefstructANode{intadjvex;structANode*nextarc;}ArcNode;typedefstructVnode{ElemTypedata;ArcNode*firstarc;}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;intvexnum,arcnum;}ALGraph;voidCreateALGraph(ALGraph*G){printf("利用邻接表创建图输入顶点数:");scanf("%d",&G->

6、vexnum);printf("输入边数:");scanf("%d",&G->arcnum);printf("输入顶点：");for(inti=0;ivexnum;i++){cin>>G->adjlist[i].data;G->adjlist[i].firstarc=NULL;}fflush(stdin);for(intk=0;karcnum;k++){inti,j;printf("输入边（vi,vj）上的顶点序号：");scanf("%d,%d",&i,&j);ArcNode*e;e=newArcNode;e->adj

7、vex=j;e->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=e;e=newArcNode;e->adjvex=i;e->nextarc=G->adjlist[j].firstarc;G->adjlist[j].firstarc=e;}}voidprintfALG(ALGraph*G){ArcNode*p;inti;printf("输出邻接表");for(i=0;ivexnum;i++){printf("%c",G->adjlist[i].data);p=G->adjl

8、ist[i].firstarc;while(p){printf("-->%d",p->adjvex);p=p->nextarc;}printf("--