图实验报告.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;ialg->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;jprintf（"%-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）图的存储结构的转换
五、实验总结及心得体会：
从一个顶点出发只能访问到它所在连通分量的各顶点。
如果有回路存在，一个顶点被访问之后又可能沿回路回到该顶点，为了避免对同一个顶点多次访问，在遍历过程中必须记下已经访问过的顶点，通常利用一维辅助数组记录顶点被访问的情况。
六、对本实验过程及方法、手段的改进建议：
报告评分：
指导教师签字：
批阅日期：
升级会员 