无向图c语言的程序代码.docx

/* 实验项目名称:图的操作的实现 实验目的与要求: 1.基础知识:掌握数据结构中图的相关知识; 掌握C或VC+语言中程序设计的方法. 2.参考教材相关算法,完成以下程序功能: (1) 利用邻接矩阵完成建图初始化； (2)利用广度优先或深度优先遍历算法编写对已建图的遍历工作; 实验性质：验证性（4学时） 说明:程序包含主要函数:主函数、建图、遍历、相关注释,并注意在程序中体现先建立后遍历的条件约束.*/-无向图的存储与表示-# include stdio.h# include stdlib.h# define M 10 /最大顶点个数int visitedM; /全局访问数组typedef structint vex,arc; /无向图的顶点数和边数char vexsM; /顶点数组int arcsMM; /边数组MGraph;typedef structint *base; /初始化的动态分配存储空间int front; /头指针,若队列不为空,指向队列头元素int rear; /尾指针,若队列不为空,指向队列尾元素的下一个位置Queue;int JianTu(MGraph &G) int s,i,y,j,n,v,x;char c1,c2;do /输入无向图的顶点个数printf (请输入无向图的顶点个数:);scanf (%d,&G.vex);if (G.vexM) /输入有误请重新输入printf (输入有误请重新输入!n);while(G.vexM);s=G.vex*(G.vex-1)/2; /此无向图的最多边数do /输入无向图的边个数printf (请输入无向图的边个数:);scanf (%d,&G.arc);if (G.arcs) /输入有误请重新输入printf (输入有误请重新输入!n);while(G.arcs); for (i=0;iG.vex;i+) /输入无向图的顶点printf (请输入第%d个顶点:,i+1);getchar();scanf (%c,&G.vexsi);for (y=0;yi;y+) /判断输入顶点是否正确while(G.vexsy)=(G.vexsi)printf (输入有误请重新输入第%d个顶点:,i+1);getchar();scanf(%c,&G.vexsi);y=0;for (i=0;iG.vex;i+) /邻接矩阵全置0for (j=0;jG.vex;j+)G.arcsij=0;for (n=0;nG.arc;n+) /输入无向图的边printf(请输入第%d条边用-隔开:,n+1);do /判断输入边是否正确s=0,y=0,v=0,x=0;getchar(); scanf(%c-%c,&c1,&c2);for (i=0;iG.vex;i+) /判断输入的c1是否合法if (c1=G.vexsi) s=1;for (i=0;iG.vex;i+) /判断输入的c2是否合法 if (c2=G.vexsi) y=1;if (c1=c2) v=1; /判断c1和c2是否相等 for(i=0;c1!=G.vexsi;i+); /找到c1所对应的顶点 for(j=0;c2!=G.vexsj;j+); /找到c2所对应的顶点if (G.arcsij=1) x=1;if (s=0|y=0|v=1|x=1)printf (输入有误请重新输入第%d条边用-隔开:,n+1);while(s!=1|y!=1|v=1|x=1);for(i=0;c1!=G.vexsi;i+); /找到c1所对应的顶点for(j=0;c2!=G.vexsj;j+); /找到c2所对应的顶点 G.arcsij=1; /将其对应数组元素置0 G.arcsji=G.arcsij; /置其对称边为1return 1;int DaYin(MGraph G) /打印出邻接矩阵int i,j;printf (此无向图的邻接矩阵为:n);printf ( );for (i=0;iG.vex;i+) /打印所有顶点printf ( %c,G.vexsi);printf (n);for (i=0;iG.vex;i+) /打印邻接矩阵printf (%c,G.vexsi);for (j=0;jG.vex;j+) printf ( %d,G.arcsij);printf (n);return 1;void DFS(MGraph G, int v) /从第v个顶点出发递归地深度优先遍历图Gint i; visitedv=1; /访问第v个顶点 printf (%c ,G.vexsv); /打印第v个顶点 for (i=0;iG.vex;i+)if(G.arcsvi=1&!visitedi) /对v的尚未访问的邻接顶点i递归调用DFSDFS(G,i);void ShenDu(MGraph G,int v) /对图G作深度优先遍历int i; for (i=0;iG.vex;i+) /访问标志数组初始化 visitedi=0; for (i=0;iG.vex;i+) if (!visitedv) /对尚未访问的顶点调用DFS访问DFS(G,v); int InitQueue(Queue &Q) /构造一个空队列Q.base=(int *)malloc(M*sizeof(int); /开辟内存if(!Q.base) /存储分配失败exit(-2);Q.front=Q.rear=0; /给数组下标赋值return 1;int EnQueue(Queue &Q,int e) /输入元素e为Q的新队尾元素if(Q.rear+1)%M=Q.front) /队列已满return 0;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%M; /尾指针后移一个单元return 1;int QueueLengh(Queue Q) /返回Q的元素个数,即队列的长度return (Q.rear-Q.front+M)%M;int DeQueue(Queue &Q,int &e) /若队列不为空,则删除Q的对头元素,用e返回其值,并返回OK;否则返回ERRORif (Q.front=Q.rear) /队列为空,返回ERRORreturn 0;e=Q.baseQ.front;Q.front=(Q.front+1)%M; /头指针后移一个单元return 1;void BFS(MGraph G) /按广度优先非递归遍历图G int i,u; Queue Q; for (i=0;iG.vex;i+) visitedi=0; InitQueue(Q); / 构建队列Q for (i=0;iG.vex;i+) if (!visitedi) /i尚未访问 visitedi=1; /访问i EnQueue(Q,i); /i入队列 while(QueueLengh(Q) /非空队列 DeQueue(Q,u); /队头元素出队并置为uprintf (%c ,G.vexsu); /打印此顶点 for (i=0;iG.vex;i+) if (G.arcsui=1&!visitedi) /u的尚未访问的邻接顶点i入队列Q visitedi=1; EnQueue(Q,i);/if/for/while/if/forint main () /主函数int i,a=0;MGraph G; /定义无向图while(1) system(cls);system(color F0);printf (t|=|tn); printf (t| |tn); printf (t| 无向图的存储与遍历 |tn); printf (t| |tn); printf (t|=|tn); printf (nt【1】 建立无向图并输入数据!t 【2】 打印无向图的邻接矩阵!n); printf (nt【3】 深度优先遍历打印图! t 【4】 广度优先遍历打印图!n); printf (nt【0】 退出程序!n); printf (nnttt请输入你的选择:); /输入选择的功能序号 scanf (%d,&i); switch(i) case 1: /建立无向图并输入数据JianTu(G); /建立无向图并输入数据a=1;system(pause); break; case 2: /打印无向图的邻接矩阵if (a=1) /打印无向图的邻接矩阵DaYin(G);else /未建立无向图printf (未建立无向图!n); system(pause); break;case 3: /深度优先遍历打印图if (a=1) /深度优先遍历打印图printf (深度优先遍历打印图:n);ShenDu(G,0);printf (n);else /未建立无向图printf (未建立无向图!n); system(pause); break;case 4: /广度优先遍历打印图if (a=1) /广度优先遍历打印