数据结构图实验报告

1、上机实验报告实验七、图算法上机实现一、实验目的：1 .了解熟知图的定义和图的根本术语,掌握图的几种存储结构.2 .掌握邻接矩阵和邻接表定义及特点,并通过实例解析掌握邻接矩阵和邻接表的类型定义.3 .掌握图的遍历的定义、复杂性分析及应用,并掌握图的遍历方法及其根本思想.二、实验内容：1 .建立无向图的邻接矩阵2 .图的深度优先搜索3 .图的广度优先搜索三、实验步骤及结果：1.建立无向图的邻接矩阵：1源代码：#include"stdio.h"#include"stdlib.h"#defineMAXSIZE30typedefstructcharvertexMA

2、XSIZE;/顶点为字符型且顶点表的长度小于MAXSIZEintedgesMAXSIZEMAXSIZE;/边为整形且edges为邻近矩阵MGraph;/MGraph为采用邻近矩阵存储的图类型voidCreatMGraph(MGraph*g,inte,intn)/建立无向图白邻近矩阵g->egdes,n为顶点个数,e为边数inti,j,k;printf("Inputdataofvertexs(0n-1):n");for(i=0;i<n;i+)g->vertexi=i;/读入顶点信息for(i=0;i<n;i+)for(j=0;j<n;j+)g-&

3、gt;edgesij=0;/初始化邻接矩阵for(k=1;k<=e;k+)/输入e条边printf("Inputedgesof(i,j):");scanf("%d,%d",&i,&j);g->edgesij=1;g->edgesji=1;)voidmain()(inti,j,n,e;MGraph*g;/建立指向采用邻接矩阵存储图类型指针g=(MGraph*)malloc(sizeof(MGraph);/生成采用邻接举证存储图类型的存储空间printf("InputsizeofMGraph:");/输入

4、邻接矩阵的大小scanf("%d",&n);printf("Inputnumberofedge:");/输入邻接矩阵的边数scanf("%d",&e);CreatMGraph(g,e,n);/生成存储图的邻接矩阵printf("OutputMGraph:n");/输出存储图的邻接矩阵for(i=0;i<n;i+)(for(j=0;j<n;j+)printf("%4d",g->edgesij);printf("n");)2)运行结果:Inpur

5、sizeofHGi*aph=4Inputnuinjjepofe-4Inputdataofuei*texsCSn1>:Input:edgfesInputedgesInput;elitesInputedQfesof<i,j5他:Lof<i,j>：0,3of<i,j>=1.3o£<i,j>=1,2OutputHGi*dph-0101101101001130Py-essanvlieytocontinue2.图的深度优先搜索:1源代码:#include"stdio.h"#include"stdlib.h"#

6、defineMAXSIZE30typedefstructnode/邻接表结点intadjvex;/邻接点域structnode*next;指向下一个邻接边结点的指针域EdgeNode;/邻接表结点类型typedefstructvnode/顶点表结点intvertex;/顶点域EdgeNode*firstedge;指向邻接表第一个邻接边节点的指针VertexNode;/顶点表结点类型voidCreatAdjlist(VertexNodeg,inte,intn)/建立无向图白邻接表,n为顶点数,e为边数,g口存储n个顶点表结点EdgeNode*p;inti,j,k;printf("Inp

7、utdataofvetex(0n-1);n");for(i=0;i<n;i+)/建立有n个顶点的顶点表gi.vertex=i;/读入顶点i信息gi.firstedge=NULL;/初始化指向顶点i的邻接表表头指针for(k=1;k<=e;k+)/输入e条边printf("Inputedgeof(i,j):");scanf("%d,%d",&i,&j);p=(EdgeNode*)malloc(sizeof(EdgeNode);p->adjvex=j;/在顶电vi的邻接表中添加邻接点为j的结点p->next=

8、gi.firstedge;/插入是在邻接表表头进行的gi.firstedge=p;p=(EdgeNode*)malloc(sizeof(EdgeNode);p->adjvex=i;/在顶电vj的邻接表中添加邻接点为i的结点p->next=gj.firstedge;/插入是在邻接表表头进行的gj.firstedge=p;)intvisitedMAXSIZE;/MAXSIZE为大于或等于无向图顶点个数的常量voidDFS(VertexNodeg,inti)EdgeNode*p;printf("%4d",gi.vertex);输出顶点i信息,即访问顶点ivisited

9、i=1;p=gi.firstedge;/根据顶点i的指针firstedge查找其邻接表的第一个邻接边结点while(p!=NULL)if(!visitedp->adjvex)/如果邻接的这个边结点未被访问过DFS(g,p->adjvex);/对这个边结点进行深度优先搜索p=p->next;/查找顶点i的下一个邻接边结点)voidDFSTraverse(VertexNodeg,intn)深度优先搜索遍历以邻接表存储的图,其中g为顶点数,n为顶点个数inti;for(i=0;i<n;i+)visitedi=0;/访问标志置0for(i=0;i<n;i+)/对n个顶点的

10、图查找未访问过的顶点并由该顶点开始遍历if(!visitedi)/当visitedi等于0时即顶点i未访问过DFS(g,i);/从未访问过的顶点i开始遍历voidmain()inte,n;VertexNodegMAXSIZE;定义顶点表结点类型数组gprintf("Inputnumberofnode:n");/输入图中节点个数边的个数scanf("%d",&n);printf("Inputnumberofedge:n");/输入图中边的个数scanf("%d",&e);printf("Ma

11、keadjlist:n");CreatAdjlist(g,e,n);/建立无向图的邻接表printf("DFSTraverse:n");DFSTraverse(g,n);/徐度优先遍历以邻接表存储的无向图printf("n");)2)运行结果：r1-1斓施阖跳实惹内容152Debugl52-exe"rnputnumberofnode：Inputnumbero£eds(e-4MaHeadjlist：Inputdataofvetex<0""n-l)；Inputedgeofj>：0,1Inputed

12、geofti,：6,3Inputedgeof：1,3InputedgeofCi,J)：1,2DFSTpauepse；0312Pi'assanyIteytocontinue3.图的广度优先搜索：1)源代码：#include"stdio.h"#include"stdlib.h"#defineMAXSIZE30typedefstructnode1/邻接表结点intadjvex;/邻接点域structnode1*next;/指向下一个邻接边结点的指针域EdgeNode;/邻接表结点类型typedefstructvnode/顶点表结点intvertex;/

13、顶点域EdgeNode*firstedge;指向邻接表第一个邻接边结点的指针域VertexNode;/顶点表结点类型voidCreatAdjlist(VertexNodeg,inte,intn)建立无向图的邻接表,n为顶点数,e为边数,g口存储n个顶点表结点EdgeNode*p;inti,j,k;printf("Inputdataofvetex(0n-1):n");for(i=0;i<n;i+)/建立有n个顶点的顶点表gi.vertex=i;/读入顶点i信息gi.firstedge=NULL;/初始化指向顶点i的邻接表表头指针for(k=1;k<=e;k+)/输

14、入e条边printf("Inputedgeof(i,j):");scanf("%d,%d",&i,&j);p=(EdgeNode*)malloc(sizeof(EdgeNode);p->adjvex=j;/在定点vi的邻接表中添加邻接点为j的结点p->next=gi.firstedge;/插入是在邻接表表头进行的gi.firstedge=p;p=(EdgeNode*)malloc(sizeof(EdgeNode);p->adjvex=i;/在顶电vj的邻接表中添加邻接点为i的结点p->next=gj.firsted

15、ge;/插入是在邻接表表头进行的gj.firstedge=p;typedefstructnodeintdata;structnode*next;QNode;/链队列结点的类型typedefstructQNode*front,*rear;/将头、尾指针纳入到一个结构体的链队列LQueue;/链队列类型voidInit_LQueue(LQueue*q)/创立一个带头结点的空队列QNode*p;*q=(LQueue*)malloc(sizeof(LQueue);/申请带头、尾指针的链队列p=(QNode*)malloc(sizeof(QNode);/申请链队列的头结点p->next=NULL;

16、/头结点的next指针置为空(*q)->front=p;/队头指针指向头结点(*q)->rear=p;/队尾指针指向头结点intEmpty_LQueue(LQueue*q)/判队空if(q->front=q->rear)/队为空return1;elsereturn0;voidIn_LQueue(LQueue*q,intx)/入队QNode*p;p=(QNode*)malloc(sizeof(QNode);/申请新链队列结点p->data=x;p->next=NULL;/新结点作为队尾结点时其next域为空q->rear->next=p;/将新结点

17、*p链到原队尾结点之后q->rear=p;/使队尾指针指向新的队尾结点*pvoidOut_LQueue(LQueue*q,int*x)/出队QNode*p;if(Empty_LQueue(q)printf("Queueisempty!n");/对空,出队失败else(p=q->front->next;指针p指向链队列第一个数据结点(即对头结点)q->front->next=p->next;头结点的next指针指向链队列第二个数据结点(即删除第一个数据结点)*x=p->data;/将删除的对头结点数据经由x返回free(p);if(q

18、->front->next=NULL)/出队后队为空,那么置为空队列q->rear=q->front;intvisitedMAXSIZE;/MAXSIZE为大于或等于无向图顶点个数的常量voidBFS(VertexNodeg,LQueue*Q,inti)/广度优先搜索遍历邻接表存储的图,g为顶点表,Q为队指针,i为第i个顶点intj,*x=&j;EdgeNode*p;printf("%4d",gi.vertex);输出顶点i信息,即访问顶点ivisitedi=1;/置顶点i为访问过标志In_LQueue(Q,i);/顶点i入队Qwhile(!

19、Empty_LQueue(Q)当队Q非空时Out_LQueue(Q,x);对头顶点出队并送j(暂记为顶点j)p=gj.firstedge;/根据顶点j的表头指针查找其邻接表的第一个邻接边结点while(p!=NULL)if(!visitedp->adjvex)/如果邻接的这个边结点未被访问过printf("%4d",gp->adjvex.vertex);/输出这个邻接边结点的顶点信息visitedp->adjvex=1;/置该邻接边结点为访问过标志In_LQueue(Q,p->adjvex);将该邻接边结点送人队Qp=p->next;/在顶电j的邻接表中查找j的下一个邻接边结点)voidmain()(inte,n;VertexNodegMAXSIZE;/定义顶点表结点类型数组gLQueue*q;printf("Inputnumberofnode:n"