实验五 图操作实现.doc

_实验五 图操作实现实验日期： 2017 年 4 月 27 日 实验目的及要求1. 熟练掌握图的邻接矩阵和邻接表的存储方式；2. 实现图的一些基本运算，特别是深度优先遍历和广度优先遍历；实验内容用邻接矩阵法建一个无向连通图（顶点信息为顺序字母A，B，C，D.，而非键盘输入），分别用dfs（深度优先搜索）和bfs(广度优先搜索)遍历，输出图中顶点信息并验证。邻接矩阵图类型定义：#define MAX 40 typedef char vexType; /*顶点类型*/ typedef struct vexType vexMAX; int arcsMAXMAX; int vn,en; MGraph; 访问标记数组定义：int visitedMAX; /*值为0时对应顶点未被访问，值为1时对应顶点已被访问 */顺序存储的循环队列类型定义：typedef int datatype; /*队列元素为图的顶点下标,int型*/typedef struct node datatype dataMAX; int front, rear; SeqQueue; /*顺序存储的循环队列类型*/任务1自定义函数库文件Queue.h，完成队列的相关操作。2创建一个程序文件sy15.cpp，自定义相应函数完成以下操作：（1）void createGraph(MGraph *g) /*建邻接矩阵存储的无向图*/（2）void visit(MGraph *g,int v) /*访问v号顶点*/（3）void dfs(MGraph *g,int v) /*邻接矩阵存储的图的深度优先搜索*/（4）void bfs(MGraph *g,int v) /*邻接矩阵存储的图的广度优先搜索*/3回答下列问题（1）现有定义：MGraph *g，并且g指针指向的无向图已创建完成，请写出该图遍历前需初始化visited数组的C程序语句。for (i = 0; i g.vn; i+) /*标记数组初始化*/visitedi = 0;（2）定义函数int count (MGraph *g)统计非连通图的连同分量个数。（说明：借助遍历算法实现）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 InitQueue(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(队列已满!); /*判队满*/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) % MAX = Q-front;sy5.cpp:#define MAX 40#includeQueue.hint 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, 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+) /*确定数据*/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); /*递归*/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输出*/dfs(&g, v);printf(n);for (i = 0; i g.vn; i+) /*标记数