图的建立及基本运算的实现

《图的建立及基本运算的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图的建立及基本运算的实现实验目的：掌握图形结构的特点、存储方式以及相应基本运算的编程实现。实验内容：(1)用邻接矩阵或者邻接表存储结构形式表示一个图，图中每个顶点代表一个字符（自定义），打印出深度优先搜索和广度优先搜索的节点序列。程序代码：（1）用邻接矩阵方式存储FBAECDG#include#defineMaxVertexNum50#defineQueueSize50typedefenum{FALSE,TRUE}define;definevisited[MaxVertexNum];typedefcharVertexType;

2、//顶点是字符型typedefintEdgeType;//边是整型typedefstruct{VertexTypevexs[MaxVertexNum];//顶点向量EdgeTypeedges[MaxVertexNum][MaxVertexNum];//邻接矩阵intvexnum,arcnum;//图中当前的顶点数和边数}Graph;/*邻接矩阵的建立*/voidCreateGraph(Graph*G){inti,j,k;charch1,ch2;printf("请输入顶点数和边数(输入格式为:顶点数,边数):");scanf("%d,%d",&(

3、G->vexnum),&(G->arcnum));printf("请输入顶点名称(输入格式为:a,b,c...)：");for(i=0;ivexnum;i++){getchar();scanf("%c",&(G->vexs[i]));}for(i=0;ivexnum;i++)for(j=0;jvexnum;j++)G->edges[i][j]=0;printf("请输入每条边对应的两个顶点名称(输入格式为:a,b):");for(k=0;karcnum;k++){getchar();printf("请输入第%

4、d条边的两个顶点名称：",k+1);scanf("%c,%c",&ch1,&ch2);for(i=0;ch1!=G->vexs[i];i++);for(j=0;ch2!=G->vexs[j];j++);G->edges[i][j]=1;}}/*深度优先遍历*/voidDepth(Graph*G,inti){intj;printf("%c",G->vexs[i]);//访问顶点vivisited[i]=TRUE;for(j=0;jvexnum;j++)//依次搜索vi邻接点if(G->edges[i][j]==1&&!visited[

5、j])Depth(G,j);}voidDepthsearch(Graph*G){inti;for(i=0;ivexnum;i++)visited[i]=FALSE;for(i=0;ivexnum;i++)if(!visited[i])Depth(G,i);}/*广度优先遍历*/typedefstruct{intfront;intrear;intcount;intdata[QueueSize];}AQueue;voidInitQueue(AQueue*Q){Q->front=Q->rear=0;Q->count=0;}intQue

6、ueEmpty(AQueue*Q){returnQ->count=QueueSize;}intQueueFull(AQueue*Q){returnQ->count==QueueSize;}voidEnQueue(AQueue*Q,intx){if(QueueFull(Q))printf("Queueoverflow");else{Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;}}intDeQueue(AQueue*Q){inttemp;if(QueueEmpty(Q)){

7、printf("Queueunderflow");returnNULL;}else{temp=Q->data[Q->front];Q->count--;Q->front=(Q->front+1)%QueueSize;returntemp;}}voidBreadth(Graph*G,intk){inti,j;AQueueQ;InitQueue(&Q);printf("%c",G->vexs[k]);visited[k]=TRUE;EnQueue(&Q,k);while(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=

8、0;jvexnum;j++)if(G->edges[i][j]==1&&!visited[j]){printf("%c",G->vexs[