资源描述：
《数据结构（c语言版）程海英-上机6》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、上机6图的存储与遍历1•问题描述实现有向图和无向图的邻接矩阵存储，并输出图的两种遍历的序列。用一维数组存储图中顶点的信息，用二维数组存储图中边或弧的信息，该二维数组称为邻接矩阵。邻接表表示法对图中的每个顶点建立一个带头结点的线性链表，用于存储图屮与顶点相邻接的边或弧的信息，头结点中存放该顶点的信息，所有头结点用一个顺序表存放。2•数据结构设计图的数据类型：typedefstruct{charvexsfGRAPHMAX];intedges[GRAPHMAX][GRAPHMAX];intn,e;}MGraph;typedefstruct{intfront;i
2、ntrear;intcount;intdatafQueueSize];}cirQueue;3•函数说明图的基本操作：〃建立邻接矩阵〃实现深度优先搜索遍历〃实现广度优先搜索遍历voidCreateMGraph(MGraph*G)voidDFSTraverse(MGraph*G)voidBFSTraverse(MGraph*G)4•编码实现#include#defineGRAPHMAX30#defineFALSE0#defineTRUE1#defineErrorprintf#defineQueueSize30typedefstruct{ch
3、arvexsIGRAPHMAXJ;intedges[GRAPHMAX][GRAPHMAXI;intn,e;}MGraph;typedefstruct{intfront;intrear;intcount;intdata
4、QueueSizeI;}cirQueue;intvisitedf10];voidCreateMGraph(MGraph*G){〃建立邻接矩阵inti,j,k;charchl,ch2;printf(utt请输入顶点数，边数并按冋车(格式如:3,4):J;scanf(“％d,%cT,&G・>n,&G->e);〃输入顶点数、边数for(i
5、=0;in;i++){getchar();printf(utt请输入第％d个顶点并按回车二i+1);scanf(“％c",&G->vexsfi]);〃输入顶点for(i=0;in:i++)for(j=0;jn;j+4-)G->edges[i][j]=O;for(k=0;ke;k++){getchar();printf(44tt请输入第％d条边的顶点序号(格式如:i,j):二k+1);scanf(“％c,%c",&chl,&ch2);〃输入边for(i=0;chl!=G->vexs[i];i++);for(j
6、=0;ch2!=G->vexs[j]；j++)；G->edges
7、i
8、
9、j]=l;}}voidDFSM(MGraph*G,inti){〃实现深度优先搜索遍历intj;printf(44tt深度优先遍历序列:％c,G->vexsfi]);visited
10、i]=FALSE;for(j=0;jn;j++)if(G->edges[i]fj]==1&&!visited[jl)DFSM(G,j);}voidDFSTraverse(MGraph*G){inti;for(i=0;in;i++)visited[il=FALSE;for(i=0
11、;in;i++)if(!visited
12、i
13、)DFSM(G,i);〃实现广度优先搜索遍历voidBFSM(MGraph*G,intk){inti,j;cirQueueQ;InitQueue(&Q);printf(“ltt广度优先迫历遍历序列:%c,5,G->vexs[k]);visited*]二TRUE;EnQueue(&Q,k);while(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=O;jn;j++)if(G->edges[i]
14、j]==l&&!visited
15、j]){visited[j]二TR
16、UE;EnQueue(&Q,j);}}}voidBFSTraverse(MGraph*G){inti;for(i=0;in;i++)visited
17、i]=FALSE;for(i=0;in;i++)if(!visited
18、i
19、)BFSM(G,i);}voidInitQueue(cirQueue*Q){〃队列操作Q->front=Q->rear=0;Q->count=0;intQueueEmpty(cirQueue*Q){returnQ->count=QueueSize;}intQueueFull(cirQueue*Q){returnQ->c
20、ount=QueueSize;}voidEnQueue(cirQueue*Q，i
