图的实验报告.docx
- 文档编号:14298157
- 上传时间:2023-06-22
- 格式:DOCX
- 页数:15
- 大小:130.75KB
图的实验报告.docx
《图的实验报告.docx》由会员分享,可在线阅读,更多相关《图的实验报告.docx(15页珍藏版)》请在冰点文库上搜索。
图的实验报告
《数据结构》
实验报告
题目:
图
-、实现图的邻接矩阵和邻接表存储
(一)需求分析
对于下图所示的有向图G,编写一个程序完成如下功能:
1.建立G的邻接矩阵并输出之
2•由G的邻接矩阵产生邻接表并输岀之
3.再由2的邻接表产生对应的邻接矩阵并输岀之
(二)系统设计
1、本程序屮用到的所有抽彖数据类型的定义;
typedefstruct
{intno;InfbType
into;
}VertexType;
typedefstruct
{intedges[MAXV][MAXV];
intvexnum,arcnum;
VertexTypevexs[MAXV];
)MGraph;
typedefstructANode
{intadjvex;
structANode*nextarc;
InfbTypeinfo;
}ArcNode;
typedefintVertex;
typedefstructVnode
{Vertexdata;
ArcNode*firstarc;
}VNode;
typedefVNodeAdjList[MAXV];typedefstruct
〃顶点类型
//图的定义
〃图的邻接矩阵类型
〃弧的结点结构类型
〃邻接表头结点的类型
〃指向第一条弧
//AdjList是邻接表类型
intn,e;
〃图的邻接表类型
3、列出各个功能模块的主要功能及输入输出参数
voidMatToList(MGraphg,ALGraph*&G)将邻接矩阵g转换成邻接表G
voidDispMat(MGraphg)输出邻接矩阵g
voidDispAdj(ALGraph*G)输岀邻接表G
intOutDegree(ALGraph*G,intv)求图中每个顶点的出度
(3)调试分析
调试过程中还是出现了一些拼写错误,经检查后都能及时修正。
有些是语法设计上的小
错误,比如一些参变量的初始值设置错误,使得程序调试出错。
在小组讨论分析后纠正了这
些结果,并尽量改进了算法的性能,减小时间复杂度。
将邻接矩阵g转换成邻接表G,输出邻接矩阵g,输出邻接表G的算法时间复杂度都是0(nA2)o
通过这次实验,对图的存储方法有了更深刻的印象。
(4)测试结果
测试结果:
(1)有向图G的邻接矩阵为
0104
0092
3580
0060
(2)图G的邻接矩阵转换成的邻接表为:
0:
13
1:
23
2:
012
3:
2
(5)用户手册
不需要输入参数
(六)附录
源程序
#include
#include
#defineMAXV100
#detineINF32767typedefintInibType;
typedefstruct
{
intno;
InfbTypeinfo;
}VertexType;
typedefstruct
{
intedges[MAXV][MAXV];intvexnum,arcnum;
VertexTypevexs[MAXV];}MGraph;
typedefstructANode
{
intadjvex;
structANode*nextarc;
InfbTypeinfo;
}ArcNode;
typedefintVertex;
typedefstructVnode
{
Vertexdata;
ArcNode*firstarc;
}VNode;
〃最大顶点个数
//INF表示g
〃顶点编号
〃顶点其他信息
〃顶点类型
//图的定义
〃邻接矩阵
〃顶点数,弧数
〃存放顶点信息
〃图的邻接矩阵类型
〃弧的结点结构类型
//该弧的终点位置
〃指向下一条弧的指针
〃该弧的相关信息,这里用于存放权值
〃邻接表头结点的类型
〃顶点信息
〃指向第一条弧
typedefVNodeAdjList[MAXV];typedefstruct
{
AdjListadjlist;
intn,e;
//AdjList是邻接表类型
//邻接表
〃图屮顶点数n和边数e
}ALGraph;〃图的邻接表类型
voidMatToList(MGraphg,ALGraph*&G)〃将邻接矩阵g转换成邻接表G
inti,j,n=g.vexnum;
ArcNode*p;
//n为顶点数
G=(ALGraph*)malloc(sizeof(ALGraph));
for(i=0;i G->adjlist[i].firstarc=NULL; 〃检查邻接矩阵中每个元素 if(g.edges[i][j]! =O)〃邻接矩阵的当前元素不为0 〃创建一个结点巾 p二(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j; 〃将*p链到链表后 p->info=g.edges p->nextarc=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p; G->n=n;G->e=g.arcnum; } voidDispMat(MGraphg) 〃输出邻接矩阵g { inti,j; for(i=0;i for(j=0;j if(g.edges[i][j]==INF)printf(,,%3sn,u8••);else printf(n%3du,g.edges[i][j]);printf(n\nn); voidDispAdj(ALGraph*G)〃输出邻接表G { inti; ArcNode巾; for(i=0;i p=G->adjlist[i].firstarc; if(p! =NULL)printf(u%3d: n,i);while(p! =NULL) { printf(n%3d",p->adjvex);p=p・>ncxtarc; printf(n\nn); intOutDegree(ALGraph*G,intv)//求图中每个顶点的出度 { ArcNode*p; intn=0; p=G->adjlist[v].firstarc; while(p! 二NULL) {n++; p=p->nextarc; } returnn; } voidmain() { inti,j; MGraphg,gl; ALGraph*G; intA[MAXV][4]={ {0,1,0,4}, {0,0,9,2}, {3,5,8,0},{0,0,6,0},}; g.vexnum=4;g.arcnum=8; for(i=0;i for(j=0;j g.edges[i][j]=A[i]|j]; printf(An”); printf(u (1)有向图G的邻接矩阵为: \n"); DispMat(g); G=(ALGraph*)malloc(sizeof(ALGraph)); printf(** (2)图G的邻接矩阵转换成邻接表为: \n“);MatToList(g,G); DispAdj(G); 运行后结果显示: 二、实现图的遍历算法 (一)需求分析 对于上图G,编写一个程序输岀从顶点0开始的深度优先遍历序列(递归算法)和广度优先遍历序列(非递归算法)。 (二)系统设计 1.说明本程序屮用到的所有抽象数据类型的定义; typedefstruct{ charvexs[MaxVertexNum];〃顶点表 intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵,可看作边表 intn,e;〃图中的顶点数n和边数e JMGraph;//用邻接矩阵表示的图的类型 2.主程序的流程以及各程序模块之间的层次调用关系,画出函数的调用关系图。 3.列出各个功能模块的主要功能及输入输出参数。 voidCreatMGraph(MGraph*G)创建邻接矩阵G voidDFSM(MGraphKj,inti)以Vi为出发点对0・1邻接矩阵表示的图G进行DFS搜索voidDFS(MGraph*G)深度优先遍历 voidBFS(MGraph*G,intk)以Vk为源点对用邻接矩阵表示的图G进行广度优先遍历 (3)调试分析 调试过程中还是出现了一些拼写错误,经检查后都能及时修正。 有些是语法设计上的小 错误,比如一些参变量的初始值设置错误,使得程序调试出错。 在小组讨论分析后纠正了这 些结果,并尽量改进了算法的性能,减小时间复杂度。 创建邻接矩阵算法的时间复杂度是O(2n+n人2),深度优先遍历和广度优先遍历的算法时 间复杂度都是O(nT)。 通过这次实验,加深了对遍历图的递归和非递归的算法的印象。 (4)测试结果 输入节点数8和边数9,各节点标示01234567,边是01,02,13,14,25,26,37,47,56 运行后深度优先遍历是01374256,广度优先遍历是01234567。 (5)用户手册 根据提示输入节点和边数,然后再由提示输入各节点标示,接下来输入各边。 运行后便得 到深度优先遍历和广度优先遍历结果。 (6)附录 源程序: #includeHstdio.h" #includeHstdlib.hH #defineMaxVertexNum100〃定义最大顶点数 typedefstructf charvexs[MaxVertexNum];〃顶点表 intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵,可看作边表 intn,e;〃图中的顶点数n和边数e JMGraph;//用邻接矩阵表示的图的类型 voidCreatMGraph(MGraph*G)//建立邻接矩阵 { inti,j,k; chara; printf(nInputVertexNum(n)andEdgesNum(e): "); scanf(n%d,%du,&G->n,&G->e);//输入顶点数和边数 scanf(”%c",&a); printf(HInputVertexstring: M); for(i=0;i scanf(”%cJ&a); 〃读入顶点信息,建立顶点表 G->vexs[i]=a; for(i=O;i for(j=O;j G->edges[i][j]=O;〃初始化邻接矩阵 prints"Inputedges,CreatAdjacencyMatrix\nn); for(k=0;k scanf(n%d%dn,&i,&j);〃输入边(Vi,Vj)的顶点序号 G->edges[i][j]=l; G->edges[j][i]=l;//若为无向图,矩阵为对称矩阵;若建立有向图,去掉该条语句} } typedefenum{FALSE,TRUE}Boolean; Booleanvisited[MaxVertexNum]; voidDFSM(MGraph*G,inti) {〃以Vi为出发点对邻接矩阵表示的图G进行DFS搜索,邻接矩阵是0,1矩阵 intj; printf("%cH,G->vexs[i]);visited[i]=TRUE; fbr(j=O;j if(G->edges[i](j]==l&&! visited[j]) DFSM(GJ); } voidDFS(MGraphP) { inti; for(i=0;i for(i=0;i if(! visited[i])DFSM(G,i); ) voidBFS(MGraph*G,intk){〃以Vk inti,j,f=O,r=O;intcq[MaxVertexNum];ft)r(i=0;i 〃访问顶点Vi 〃置已访问标志 〃依次搜索Vi的邻接点 //(Vi, //标志向量初始化 〃Vi未访问过 //以Vi为源点开始 为源点对用邻接矩阵表示的图 〃定义队列 //标志向量初始化 //队列初始化 〃访问源点Vk Vj)eE,且Vj未访问过,故 Vj为新出发点 DFS搜索 G进行广度优先搜索 已访问,将其入队。 注意,实际上是将其序号入队 while(cq[f]! =-l){〃队非空则执行 i=cq[f];仕却1;//Vf出队 for(j=0;j if(G->edges[i][j]==l&&! visited[j]){//Vj未访问 prirHf(”%c”,G・>vcxs[j]);〃访问Vj visited[j]=TRUE; r=r+1;cq[r]=j;〃访问过Vj入队 voidmain() { inti; MGraph*G; G=(MGraph*)malloc(sizeof(MGraph));//为图G申请内存空间 CreatMGraph(G); 〃建立邻接矩阵 printf(nPrintGraphDFS: H) ■ DFS(G); //深度优先遍历 printf(An”); printf(TrintGraphBFS: ”) ■ BFS(G,0); 〃以序号为3的顶点开始广度优先遍历 printf(An"); } 测试结果 cc*G: \下载专Be\DebugV1-exe* InputUertexHun 8,9 InputUertexstring=01234567 rnputedgesGreatfidjacencyMatrix 01 02 i3 14 2S 26 37 4? §6 PrintGraphDFS: 01374256 PrintGraphBFS: 0123456? Pressanykeytocontinue
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 报告