上机练习三-图的操作.doc

一、实验内容图的生成图的遍历。二、实验目的1掌握图的基本存储方法邻接表和邻接矩阵。2掌握有关图的操作算法并用高级语言编程实现；3熟练掌握图的两种搜索路径的遍历方法。三、实验题目本实验要求实现以下功能：1以邻接矩阵或邻接表作为存储结构建立一个无向图。2深度（或广度）优先搜索该无向图，输出遍历序列。 测试数据：对如图的无向图建立存储并遍历：四、实验报告图的存储可采用邻接表或邻接矩阵；定义下列过程： CreateGraph(): 按从键盘的数据建立图 DFSGrahp()：深度优先遍历图 BFSGrahp()：广度优先遍历图算法描述：可以用自然语言、伪代码或流程图等方式VertexType; /顶点类型MGraph; /图的邻接矩阵类型ArcNode; /定义邻接表类型void DispMat(MGraph g) /输出邻接矩阵void MatToList(MGraph g,ALGraph *&G) /将邻接矩阵g转换为邻接表Gvoid DispAdj(ALGraph *G) /输出邻接表void ListToMat(ALGraph *G,MGraph g) /将邻接表转换为邻接矩阵的形式void DFS(ALGraph *G,int v) /递归深度优先遍历void BFS(ALGraph *G,int v) /广度优先遍历源代码：#include#include#define max 100 /最大顶点个数typedef struct /以下定义临接矩阵类型int number; /顶点编号int info; /顶点其他信息,边的权值VertexType; /顶点类型typedef struct /图的定义int edgesmaxmax; /邻接矩阵int n,e; /顶点数和弧数 VertexType vexsmax; /存放定点信息MGraph; /图的邻接矩阵类型typedef struct ANode /弧的结点结构类型int adjvex; /弧的重点位置,就是放值的struct ANode *nextarc; /指向下一条弧的指针int info; /存放弧的信息（权值）ArcNode;typedef struct Vnode int data; /邻接表头结点的的类型ArcNode *firstarc; /指向第一条弧VNode;typedef VNode AdjListmax; /AdjList是邻接表类型，把大表变成几个小的连接到一起typedef struct AdjList adjlist; /邻接表int n,e; /图中顶点数和和边数ALGraph; /图的邻接表类型int visitedmax; /全局数组用于判断后面节点是否被访问过void DispMat(MGraph g) /输出邻接矩阵int i,j;for(i=0;ig.n;i+)for(j=0;jg.n;j+)if(g.edgesij=0)printf(0 );else printf(%d ,g.edgesij);printf(n);void MatToList(MGraph g,ALGraph *&G) /将邻接矩阵g转换为邻接表Gint i,j;int n=g.n; /n为顶点数ArcNode *p; /弧节点结构的类型G=(ALGraph *)malloc(sizeof(ALGraph);for(i=0;iadjlisti.firstarc=NULL;for(i=0;in;i+) /检查邻接矩阵的每个元素for(j=0;jadjvex=j; p-info=g.edgesij; /存放边的权值p-nextarc=G-adjlisti.firstarc; /将*p连接到表后G-adjlisti.firstarc=p;G-e=g.e;G-n=g.n;void DispAdj(ALGraph *G) /输出邻接表 int i;ArcNode *p; /弧的类型for(i=0;in;i+)p=G-adjlisti.firstarc;if(p!=NULL)printf( %d: ,i); /这是那个大链表的头while(p!=NULL) /顺着那个头向下查看printf( %d ,p-adjvex); /输出弧的终点p=p-nextarc; printf(n);void change(int visited,ALGraph *G) /给全局变量visited赋初值int i;for(i=0;in;i+)visitedi=0;void ListToMat(ALGraph *G,MGraph g) /将邻接表转换为邻接矩阵的形式int i,j;int n=G-n;ArcNode *p;for(i=0;in;i+)for(j=0;jn;j+)g.edgesij=0;for(i=0;iadjlisti.firstarc;while(p!=NULL)g.edgesip-adjvex=p-info;p=p-nextarc;g.n=n;g.e=G-e;void DFS(ALGraph *G,int v) /递归深度优先遍历ArcNode *p;/change(visited,G);visitedv=1; /第一个点设为已被访问并输出，接着以他为主进行遍历printf( %d,v); p=G-adjlistv.firstarc;while(p!=NULL)if(visitedp-adjvex=0)DFS(G,p-adjvex);p=p-nextarc; void BFS(ALGraph *G,int v) /广度优先遍历，一个点先找和其有关的所有节点， ArcNode *p;int queuemax,front=0,rear=0; /定义循环队列并初始化int visitedmax;int w,i;for(i=0;in;i+)visitedi=0;printf( %d ,v); /把输入的第v个作为第一个广度遍历的节点，一直这样进行下去visitedv=1; rear=(rear+1)%max; /要入队了queuerear=v; /把v入队while(front!=rear) /队列不为空的时候front=(front+1)%max; /要出队了w=queuefront;p=G-adjlistw.firstarc; /跟前面差不多开始查找与顶点w邻接的第一个顶点了while(p!=NULL)if(visitedp-adjvex=0) /就是当前节点未被访问printf(%d ,p-adjvex);visitedp-adjvex=1;rear=(rear+1)%max; /又要入队了，马上要重复之前的操作了queuerear=p-adjvex;p=p-nextarc;printf(n);void main()int i,j;MGraph g;ALGraph *G; /没有定义过的邻接表类型加上*int Amax6; printf(请输入邻接矩阵：n);for(i=0;i6;i+)for(j=0;j6;j+)scanf(%d,&Aij);g.n=6;g.e=10;for(i=0;ig.n;i+)for(j=0;jg.n;j+)g.edgesij=Aij; /这是给邻接矩阵赋值printf(这是图的邻接矩阵的形式：);printf(n);DispMat(g); /输出邻接矩阵的函数G=(ALGraph *)mall