《实验五图操作实现》由会员分享，可在线阅读，更多相关《实验五图操作实现（12页珍藏版）》请在金锄头文库上搜索。
1、实验五图操作实现实验日期：2017年 4月27日实验目的及要求1 .熟练掌握图的邻接矩阵和邻接表的存储方式；2 .实现图的一些基本运算，特别是深度优先遍历和广度优先遍历；实验内容用邻接矩阵法建一个无向连通图（顶点信息为顺序字母 A, B, C, D.,而 非键盘输入），分别用dfs （深度优先搜索）和bfs（广度优先搜索）遍历，输出图 中顶点信息并验证。邻接矩阵图类型定义：#define MAX 40typedef char vexType; /* 顶点类型 */typedef structvexType vexMAX;int arcsMAXMAX;int vn,en; MGraph;访问标记
2、数组定义：int visitedMAX; /*值为0时对应顶点未被访问，值为1时对应顶点已被访问 */顺序存储的循环队列类型定义：typedef int datatype; /* 队列元素为图的顶点下标,int 型*/typedef struct nodedatatype dataMAX;int front, rear; SeqQueue; /*顺序存储的循环队列类型*/任务1 自定义函数库文件Queue.h ，完成队列的相关操作。2 创建一个程序文件sy15.cpp ，自定义相应函数完成以下操作：( 1 ) void createGraph(MGraph *g)( 2) void visit
3、(MGraph *g,int v)( 3 ) void dfs(MGraph *g,int v)*/( 4 ) void bfs(MGraph *g,int v)3 回答下列问题/*建邻接矩阵存储的无向图 */*访问 v 号顶点 */*邻接矩阵存储的图的深度优先搜索/*邻接矩阵存储的图的广度优先搜索 */1)现有定义： MGraph *g ，并且 g 指针指向的无向图已创建完成，请写出 该图遍历前需初始化 visited 数组的 C 程序语句。for (i = 0; i g.vn; i+) /*标记数组初始化*/visitedi = 0;(2)定义函数int count (MGraph*g)统
4、计非连通图的连同分量个数。(说明:借助遍历算法实现)int count (MGraph *g) int i, m=0;for(i=0; ivn; i+)if(visitedi=0) m+;dfs(g, i);return m;4 自定义函数库文件Queue.h 与 sy15.cpp 源程序清单(含必要的注释)Queue.h:#includetypedef int datatype;/*队列元素为图的顶点下标,int 型*/typedef struct node datatype dataMAX;int front, rear; SeqQueue; /*顺序存储的循环队列类型*/void Ini
5、tQueue(SeqQueue *Q);/*初始化队列*/void EnQueue(SeqQueue *Q, int v);/*入队 */datatype DeQueue(SeqQueue *Q);/* 出队 */int EmptyQueue(SeqQueue *Q);/*判队空*/int FullQueue(SeqQueue *Q);/*判队满 */void InitQueue(SeqQueue *Q) Q-front = Q-rear = 0;void EnQueue(SeqQueue *Q, int v) if (FullQueue(Q) printf( 队列已满 !);/*判队满 */
6、return;Q-rear = (Q-rear + 1) % MAX;/*入队 */Q-dataQ-rear = v;datatype DeQueue(SeqQueue *Q) if (EmptyQueue(Q) printf( 队列为空 !);/*判队空 */return -1;/* 出队 */Q-front = (Q-front + 1) % MAX;return Q-dataQ-front;int EmptyQueue(SeqQueue *Q) return Q-front = Q-rear;int FullQueue(SeqQueue *Q) return (Q-rear + 1) %
7、 MAX = Q-front;sy5.cpp:#define MAX 40#includeQueue.h*/int visitedMAX; /* 值为 0 时对应顶点未被访问，值为 1 时对应顶点已被访问typedef char vexType; /* 顶点类型 */typedef struct vexType vexMAX;int arcsMAXMAX;int vn, en; MGraph;void createGraph(MGraph *g);/*建邻接矩阵存储的无向图*/void visit(MGraph *g, int v);/*访问v 号顶点 */void dfs(MGraph *g
8、, int v);/* 邻接矩阵存储的图的深度优先搜索*/void bfs(MGraph *g, int v);/* 邻接矩阵存储的图的广度优先搜索*/void createGraph(MGraph *g) int i, j, v;char a = A;printf(输入顶点数：)；/*输入顶点数和边数*/scanf(%d, &g-vn);printf(输入边数:);scanf(%d, &g-en);for (i = 0; i vn; i+) /*二维数组初始化*/for (j = 0; j vn; j+) g-arcsij = 0;for (v = 0; v vn; v+) /*确定数据*/
9、g-vexv = a;a+;printf(输入结构:n);/*确定边*/for (v = 0; v en; v+) scanf(%d %d, &i, &j);g-arcsij = 1;g-arcsji = 1;void visit(MGraph *g, int v) printf(%c, g-vexv);void dfs(MGraph *g, int v) int j;visit(g, v);/*输出数据*/visitedv = 1;/*标记已访问 */for (j = 0; j vn; j+) if (g-arcsvj = 1 & visitedj = 0) dfs(g, j);/*递归 *
10、/void bfs(MGraph *g, int v) int i, w;SeqQueue Q;InitQueue(&Q);/*队列初始化*/EnQueue(&Q,v);/*入队 */visitedv = 1;/*标记已访问*/while (!EmptyQueue(&Q) w = DeQueue(&Q);/*出队 */visit(g, w);/*输出数据*/for (i = 0; i vn; i+) if (g-arcswi = 1 & visitedi = 0) EnQueue(&Q, i);/*入队 */visitedi = 1;/*标记已访问 */void main() MGraph g;int i, v;createGraph(&g);/*建图 */精品资料for (i = 0; i g.vn; i+) visitedi = 0;printf(开始顶点:);scanf(%d, &v);printf(输出(dfs):);dfs(&g, v);printf(n);for (i = 0; i 边结L 点fsfs意实验总结分析（本程序的重点与难点，调试中出现的问题及解决方法等 ）Welcome ToDownload !欢迎您的下载，资料仅供参考！
