上机练习三-图的操作

一、实验内容图的生成图的遍历。二、实验目的1．掌握图的基本存储方法――邻接表和邻接矩阵。2．掌握有关图的操作算法并用高级语言编程实现；3．熟练掌握图的两种搜索路径的遍历方法。三、实验题目本实验要求实现以下功能：1．以邻接矩阵或邻接表作为存储结构建立一个无向图。2．深度（或广度）优先搜索该无向图，输出遍历序列。[测试数据]：对如图的无向图建立存储并遍历：四、实验报告图的存储可采用邻接表或邻接矩阵；定义下列过程：CreateGraph():按从键盘的数据建立图DFSGrahp()：深度优先遍历图BFSGrahp()：广度优先遍历图算法描述：可以用自然语言、伪代码或流程图等方式VertexType;//顶点类型MGraph;//图的邻接矩阵类型ArcNode;//定义邻接表类型voidDispMat(MGraphg)//输出邻接矩阵voidMatToList(MGraphg,ALGraph*&G)//将邻接矩阵g转换为邻接表GvoidDispAdj(ALGraph*G)//输出邻接表voidListToMat(ALGraph*G,MGraphg)//将邻接表转换为邻接矩阵的形式voidDFS(ALGraph*G,intv)//递归深度优先遍历voidBFS(ALGraph*G,intv)//广度优先遍历源代码：#includestdio.h#includemalloc.h#definemax100//最大顶点个数typedefstruct//以下定义临接矩阵类型{intnumber;//顶点编号intinfo;//顶点其他信息,边的权值}VertexType;//顶点类型typedefstruct//图的定义{intedges[max][max];//邻接矩阵intn,e;//顶点数和弧数VertexTypevexs[max];//存放定点信息}MGraph;//图的邻接矩阵类型typedefstructANode//弧的结点结构类型{intadjvex;//弧的重点位置,就是放值的structANode*nextarc;//指向下一条弧的指针intinfo;//存放弧的信息（权值）}ArcNode;typedefstructVnode{intdata;//邻接表头结点的的类型ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[max];//AdjList是邻接表类型，把大表变成几个小的连接到一起typedefstruct{AdjListadjlist;//邻接表intn,e;//图中顶点数和和边数}ALGraph;//图的邻接表类型intvisited[max];//全局数组用于判断后面节点是否被访问过voidDispMat(MGraphg)//输出邻接矩阵{inti,j;for(i=0;ig.n;i++){for(j=0;jg.n;j++)if(g.edges[i][j]==0)printf(0);elseprintf(%d,g.edges[i][j]);printf(\n);}}voidMatToList(MGraphg,ALGraph*&G)//将邻接矩阵g转换为邻接表G{inti,j;intn=g.n;//n为顶点数ArcNode*p;//弧节点结构的类型G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;in;i++)//给大的邻接表中所有头结点的指针域副初值G-adjlist[i].firstarc=NULL;for(i=0;in;i++)//检查邻接矩阵的每个元素for(j=0;jn;j++)if(g.edges[i][j]!=0){p=(ArcNode*)malloc(sizeof(ArcNode));//新申请一个节点空间，就是后面的一段段小的节点p-adjvex=j;p-info=g.edges[i][j];//存放边的权值p-nextarc=G-adjlist[i].firstarc;//将*p连接到表后G-adjlist[i].firstarc=p;}G-e=g.e;G-n=g.n;}voidDispAdj(ALGraph*G)//输出邻接表{inti;ArcNode*p;//弧的类型for(i=0;iG-n;i++){p=G-adjlist[i].firstarc;if(p!=NULL)printf(%d:,i);//这是那个大链表的头while(p!=NULL)//顺着那个头向下查看{printf(%d,p-adjvex);//输出弧的终点p=p-nextarc;}printf(\n);}}voidchange(intvisited[],ALGraph*G)//给全局变量visited赋初值{inti;for(i=0;iG-n;i++)visited[i]=0;}voidListToMat(ALGraph*G,MGraphg)//将邻接表转换为邻接矩阵的形式{inti,j;intn=G-n;ArcNode*p;for(i=0;in;i++)for(j=0;jn;j++)g.edges[i][j]=0;for(i=0;in;i++){p=G-adjlist[i].firstarc;while(p!=NULL){g.edges[i][p-adjvex]=p-info;p=p-nextarc;}}g.n=n;g.e=G-e;}voidDFS(ALGraph*G,intv)//递归深度优先遍历{ArcNode*p;//change(visited,G);visited[v]=1;//第一个点设为已被访问并输出，接着以他为主进行遍历printf(%d,v);p=G-adjlist[v].firstarc;while(p!=NULL){if(visited[p-adjvex]==0)DFS(G,p-adjvex);p=p-nextarc;}}voidBFS(ALGraph*G,intv)//广度优先遍历，一个点先找和其有关的所有节点，{ArcNode*p;intqueue[max],front=0,rear=0;//定义循环队列并初始化intvisited[max];intw,i;for(i=0;iG-n;i++)visited[i]=0;printf(%d,v);//把输入的第v个作为第一个广度遍历的节点，一直这样进行下去visited[v]=1;rear=(rear+1)%max;//要入队了queue[rear]=v;//把v入队while(front!=rear)//队列不为空的时候{front=(front+1)%max;//要出队了w=queue[front];p=G-adjlist[w].firstarc;//跟前面差不多开始查找与顶点w邻接的第一个顶点了while(p!=NULL){if(visited[p-adjvex]==0)//就是当前节点未被访问{printf(%d,p-adjvex);visited[p-adjvex]=1;rear=(rear+1)%max;//又要入队了，马上要重复之前的操作了queue[rear]=p-adjvex;}p=p-nextarc;}}printf(\n);}voidmain(){inti,j;MGraphg;ALGraph*G;//没有定义过的邻接表类型加上*intA[max][6];printf(请输入邻接矩阵：\n);for(i=0;i6;i++)for(j=0;j6;j++)scanf(%d,&A[i][j]);g.n=6;g.e=10;for(i=0;ig.n;i++)for(j=0;jg.n;j++)g.edges[i][j]=A[i][j];//这是给邻接矩阵赋值printf(这是图的邻接矩阵的形式：);printf(\n);DispMat(g);//输出邻接矩阵的函数G=(ALGraph*)malloc(sizeof(ALGraph));MatToList(g,G);printf(这是图的邻接表的形式：);printf(\n);DispAdj(G);printf(从顶点0开始的深度优先遍历：\n);DFS(G,0);printf(\n);printf(从顶点0开始的广度优先遍历：\n);BFS(G,0);printf(\n);}