实验五 图操作实现.docVIP

实验五 图操作实现 实验日期： 2017 年 4 月 27 日 实验目的及要求 1. 熟练掌握图的邻接矩阵和邻接表的存储方式； 2. 实现图的一些基本运算，特别是深度优先遍历和广度优先遍历； 实验内容 用邻接矩阵法建一个无向连通图（顶点信息为顺序字母A，B，C，D...，而非键盘输入），分别用dfs（深度优先有哪些信誉好的足球投注网站）和bfs(广度优先有哪些信誉好的足球投注网站)遍历，输出图中顶点信息并验证。 邻接矩阵图类型定义： #define MAX 40 typedef char vexType; /*顶点类型*/ typedef struct{ vexType vex[MAX]; int arcs[MAX][MAX]; int vn,en; } MGraph; 访问标记数组定义： int visited[MAX]; /*值为0时对应顶点未被访问，值为1时对应顶点已被访问 */ 顺序存储的循环队列类型定义： typedef int datatype; /*队列元素为图的顶点下标,int型*/ typedef struct node{ datatype data[MAX]; int front, rear; } SeqQueue; /*顺序存储的循环队列类型*/ 任务 1．自定义函数库文件Queue.h，完成队列的相关操作。 2．创建一个程序文件sy.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程序语句。 visited[i] = 0; } （2）定义函数int count (MGraph *g)统计非连通图的连同分量个数。（说明：借助遍历算法实现）int count (MGraph *g) { int i, m=0; for(i=0; ig-vn; i++) if(visited[i]==0) { m++; dfs(g, i); } return m; } 4．自定义函数库文件Queue.h 与sy.cpp源程序清单（含必要的注释） #includestdio.h typedef int datatype; /*队列元素为图的顶点下标,int型*/ typedef struct node { datatype data[MAX]; 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-data[Q-rear] = v; } datatype DeQueue(SeqQueue *Q) { if (EmptyQueue(Q)) { printf(队列为空!); /*判队空*/ return -1; } Q-front = (Q-front + 1) % MAX; /*出队*/ return Q-data[Q-front]; } int EmptyQueue(SeqQueue *Q) { return Q-front == Q-rear; } int