图实验报告.docx
- 文档编号:16439747
- 上传时间:2023-07-13
- 格式:DOCX
- 页数:9
- 大小:197.93KB
图实验报告.docx
《图实验报告.docx》由会员分享,可在线阅读,更多相关《图实验报告.docx(9页珍藏版)》请在冰点文库上搜索。
图实验报告
闽江学院电子系
实验报告
学生姓名:
班级:
学号:
课程:
算法与数据结构
一、实验题目:
:
图及其应用
一、实验地点:
实验楼A210
二、实验目的:
.熟练掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法
.掌握图的基本运算及应用
.加深对图的理解,逐步培养解决实际问题的编程能力
三、实验内容:
.采用邻接表或邻接矩阵方式存储图,实现图的深度遍历和广度遍历;
.用广度优先搜索方法找出从一顶点到另一顶点边数最少的路径;
.图的存储结构的转换。
四、实验环境(使用的软硬件):
VisualC++集成开发环境
5、实验步骤及操作
1.启动VC++;
2.新建工程/Win32ConsoleApplication,选择输入位置:
输入工程的名称:
tu;
按“确定”按钮,选择“AnEmptyProject”,再按“完成”按钮,
3.新建文件/C++SourceFile,选中“添加到工程的复选按钮”,输入文件名“1.cpp”,按“确定”
按钮,在显示的代码编辑区内输入如下的参考程序:
#include<>
#include<>
#defineInfinity1000
#defineMAX20
typedefstruct{
intvexnum;按F7键,或工具图标进行工程的建立,如有错误,根据错误显示区中的提示,改正错误,重新建立
应用程序;
5.按Ctrl+F5键,或工具图标进行工程的执行。
6.新建工程/Win32ConsoleApplication,选择输入位置:
输入工程的名称:
图的存储结构转换;
按“确定”按钮,选择“AnEmptyProject”,再按“完成”按钮,
7.新建文件/C++SourceFile,选中“添加到工程的复选按钮”,输入文件名“1.cpp”,按“确定”
按钮,在显示的代码编辑区内输入如下的参考程序:
#include<>
#include<>
#defineMAX5
#defineINF100000
intvisit[MAX]={0};
typedefstructmgraph
{
intedges[MAX][MAX];
intn,e;
}MGraph;
typedefstructnode
{
intadjvex;
structnode*nextarc;
}ArcNode;
typedefstructVnode
{
ArcNode*firstarc;
}VNode;
typedefstructalgraph
{
VNodeadjlist[MAX];
intn,e;
}ALGraph;
voidMtoAL(MGraphmg,ALGraph*&alg)
{
inti,j,n=;
ArcNode*p;
alg=(ALGraph*)malloc(sizeof(ALGraph));
for(i=0;i alg->adjlist[i].firstarc=NULL; for(i=0;i { for(j=n-1;j>=0;j--) { if[i][j]! =0) { p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=alg->adjlist[i].firstarc; alg->adjlist[i].firstarc=p; } } alg->n=; alg->e=; } } voidALtoM(ALGraph*alg,MGraph&mg) { inti=0,n=alg->n; ArcNode*p; for(i=0;i { p=alg->adjlist[i].firstarc; while(p) { [i][p->adjvex]=1; p=p->nextarc; } } =alg->n; =alg->e; } voidPrintMGraph(MGraphmg) { for(inti=0;i { for(intj=0;j printf("%-3d",[i][j]); printf("\n"); } printf("thenumofedgeis: %-3d\n",; printf("thenumofvertexis: %-3d\n",; } voidPrintALGraph(ALGraph*alg) { for(inti=0;i { if(alg->adjlist[i].firstarc) { printf("vertex[%d]: ",i); ArcNode*p=alg->adjlist[i].firstarc; while(p) { printf("%-3d",p->adjvex); p=p->nextarc; } } printf("\n"); } } voidmain() { MGraphmg; ALGraph*alg; =5;=6; intpath[MAX]; inta[MAX][MAX]={{0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0}}; inti,j; for(i=0;i<;i++) for(intj=0;j<;j++) [i][j]=a[i][j]; printf("邻接矩阵表示图: \n"); PrintMGraph(mg); MtoAL(mg,alg); printf("转化为邻接表表示图: \n"); PrintALGraph(alg); ALtoM(alg,mg); printf("转化为邻接矩阵表示图: \n"); PrintMGraph(mg); } 8.按F7键,或工具图标进行工程的建立,如有错误,根据错误显示区中的提示,改正错误,重新建立 应用程序; 9.按Ctrl+F5键,或工具图标进行工程的执行。 六、实验结果: (1)无向图 (2)有向图 (3)图的存储结构的转换 五、实验总结及心得体会: 从一个顶点出发只能访问到它所在连通分量的各顶点。 如果有回路存在,一个顶点被访问之后又可能沿回路回到该顶点,为了避免对同一个顶点多次访问,在遍历过程中必须记下已经访问过的顶点,通常利用一维辅助数组记录顶点被访问的情况。 六、对本实验过程及方法、手段的改进建议: 报告评分: 指导教师签字: 批阅日期:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 报告