图实验报告.docx

1、图实验报告 闽 江 学 院 电 子 系实 验 报 告学生姓名：班级：学 号：课程：算法与数据结构一、实验题目：图及其应用一、 实验地点：实验楼A210二、 实验目的：. 熟练掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法. 掌握图的基本运算及应用. 加深对图的理解，逐步培养解决实际问题的编程能力三、 实验内容：. 采用邻接表或邻接矩阵方式存储图，实现图的深度遍历和广度遍历；. 用广度优先搜索方法找出从一顶点到另一顶点边数最少的路径；. 图的存储结构的转换。四、 实验环境（使用的软硬件）：Visual C+集成开发环境5、实验步骤及操作1启动VC+；2. 新建工程/Win32 Console

2、 Application，选择输入位置：输入工程的名称：tu；按“确定”按钮，选择“An Empty Project”，再按“完成”按钮，3.新建文件/C+ Source File，选中“添加到工程的复选按钮”，输入文件名“1. cpp”，按“确定”按钮，在显示的代码编辑区内输入如下的参考程序:#include #include #define Infinity 1000#define MAX 20typedef struct int vexnum; 按F7 键，或工具图标进行工程的建立，如有错误，根据错误显示区中的提示，改正错误，重新建立应用程序；5按Ctrl+F5 键，或工具图标进行工程的

3、执行。6.新建工程/Win32 Console Application，选择输入位置：输入工程的名称：图的存储结构转换；按“确定”按钮，选择“An Empty Project”，再按“完成”按钮，7.新建文件/C+ Source File，选中“添加到工程的复选按钮”，输入文件名“1. cpp”，按“确定”按钮，在显示的代码编辑区内输入如下的参考程序:#include#include#define MAX 5#define INF 100000int visitMAX=0;typedef struct mgraph int edgesMAXMAX; int n,e;MGraph;typedef

4、 struct node int adjvex; struct node *nextarc;ArcNode;typedef struct Vnode ArcNode *firstarc;VNode;typedef struct algraph VNode adjlistMAX; int n,e;ALGraph;void MtoAL(MGraph mg,ALGraph* &alg) int i,j,n=; ArcNode *p; alg=(ALGraph *)malloc(sizeof(ALGraph); for(i=0;iadjlisti.firstarc=NULL; for(i=0;i=0;

5、j-) ifij!=0) p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=j; p-nextarc=alg-adjlisti.firstarc; alg-adjlisti.firstarc=p; alg-n=; alg-e=; void ALtoM(ALGraph *alg,MGraph &mg) int i=0,n=alg-n; ArcNode *p; for(i=0;iadjlisti.firstarc; while(p) ip-adjvex=1; p=p-nextarc; =alg-n; =alg-e;void PrintMGraph(MGrap

6、h mg) for(int i=0;iMAX;i+) for(int j=0;jMAX;j+) printf(%-3d,ij); printf(n); printf(the num of edge is:%-3dn,; printf(the num of vertex is:%-3dn,;void PrintALGraph(ALGraph* alg) for(int i=0;iadjlisti.firstarc) printf(vertex%d:,i); ArcNode* p=alg-adjlisti.firstarc; while(p) printf(%-3d,p-adjvex); p=p-

7、nextarc; printf(n); void main() MGraph mg; ALGraph *alg; =5;=6; int pathMAX; int aMAXMAX= 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; int i,j; for(i=0;i;i+) for(int j=0;j;j+) ij=aij; printf(邻接矩阵表示图:n); PrintMGraph(mg); MtoAL(mg,alg); printf(转化为邻接表表示图:n); PrintALGraph(alg); ALtoM(alg,mg); prin

8、tf(转化为邻接矩阵表示图:n); PrintMGraph(mg);8. 按F7 键，或工具图标进行工程的建立，如有错误，根据错误显示区中的提示，改正错误，重新建立应用程序；9.按Ctrl+F5 键，或工具图标进行工程的执行。六、实验结果：（1）无向图（2）有向图（3）图的存储结构的转换五、 实验总结及心得体会： 从一个顶点出发只能访问到它所在连通分量的各顶点。如果有回路存在，一个顶点被访问之后又可能沿回路回到该顶点，为了避免对同一个顶点多次访问，在遍历过程中必须记下已经访问过的顶点，通常利用一维辅助数组记录顶点被访问的情况。六、 对本实验过程及方法、手段的改进建议：报告评分：指导教师签字： 批阅日期：