2022年图实验报告 .pdf

闽 江 学 院 电 子 系实验报告学生姓名：班级：学 号：课程： 算法与数据结构一、实验题目：图及其应用一、实验地点： 实验楼 A210二、实验目的：. 熟练掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法. 掌握图的基本运算及应用. 加深对图的理解，逐步培养解决实际问题的编程能力三、实验内容：. 采用邻接表或邻接矩阵方式存储图，实现图的深度遍历和广度遍历；. 用广度优先搜索方法找出从一顶点到另一顶点边数最少的路径；. 图的存储结构的转换。四、实验环境（使用的软硬件） ：Visual C+ 集成开发环境五、实验步骤及操作1启动 VC+ ；2. 新建工程 /Win32 Console Application ，选择输入位置：输入工程的名称：tu；按“确定”按钮，选择“An Empty Project ” ，再按“完成”按钮，3. 新建文件 /C+ Source File ，选中“添加到工程的复选按钮”，输入文件名“1. cpp” ，按“确定”按钮，在显示的代码编辑区内输入如下的参考程序: #include #include #define Infinity 1000 #define MAX 20 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - 精选文档2 typedef struct int vexnum; /顶点数目int arcnum; /弧数目char vexsMAX; /顶点向量int arcsMAXMAX; /邻接矩阵char kind; /图的种类：有向图D，无向图U MGraph; / 图的建立MGraph Creat_MGraph() MGraph G; int i,j,k,w; char v1,v2; printf(请输入图的种类（有向图（D）, 无向图（ U） ！n); scanf(%c,&G.kind); printf(请输入顶点数目和弧数目!n); scanf(%d%d,&G.vexnum,&G.arcnum); getchar(); printf(请输入各个顶点（abc）!n); for(i=0;iG.vexnum;i+) scanf(%c,&G.vexsi); getchar(); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=Infinity; for(i=0;iG.arcnum;i+) printf(请输入第 (%d) 条弧的起始点和它的权重（ccd）!n,i+1); scanf(%c%c%d,&v1,&v2,&w); getchar(); j=k=0; while(G.vexsj!=v1) j+; /起点while(G.vexsk!=v2) k+; /终点G.arcsjk=w; if(G.kind=U) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页 - - - - - - - - - 精选文档3 G.arcskj=w; return G; int visitedMAX; /标志数组，显示是否遍历/ 递归深度遍历调用函数void DFS(MGraph G,int i) int j; visitedi=1; printf( %c ,G.vexsi); for(j=0;jG.vexnum;j+) if(!visitedj&G.arcsijInfinity) DFS(G,j); / 深度遍历函数void M_DFSTraverse(MGraph G) int i; printf(深度遍历图结果如下： n); for(i=0;iG.vexnum;i+) visitedi=0; for(i=0;iG.vexnum;i+) if(!visitedi) DFS(G,i); printf(n); / 广度遍历函数void M_BFSTraverse(MGraph G) int i,j,k,QMAX,w; j=k=0; printf(广度遍历图结果如下： n); for(i=0;iG.vexnum;i+) visitedi=0; for(i=0;iG.vexnum;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - 精选文档4 if(!visitedi) visitedi=1; printf( %c ,G.vexsi); Qk+=i; while(j!=k) j+; for(w=0;wG.vexnum;w+) if(!visitedw & G.arcsjwInfinity) visitedw=1; printf( %c ,G.vexsw); Qk+=w; printf(n); / 最小生成树函数，对无向图适用void MiniSpanTree_PRIM(MGraph G,char u) char adjvexMAX; int lowcostMAX; int i,j,k=0,min; printf(图的最小生成树为： n); while(G.vexsk!=u) k+; for(i=0;iG.vexnum;i+) if(i!=k) adjvexi=u; lowcosti=G.arcski; lowcostk=0; for(i=0;iG.vexnum-1;i+) min=Infinity; for(j=0;jG.arcnum;j+) if(lowcostj & lowcostjmin) min=lowcostj; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - 精选文档5 k=j; printf(%c-(%d)-%cn,adjvexk,lowcostk,G.vexsk); lowcostk=0; for(j=0;jG.vexnum;j+) if(G.arcskjlowcostj) adjvexj=G.vexsk; lowcostj=G.arcskj; / 求最短路径的函数，对有向图适用void ShortestPath_DIJ(MGraph G,char u) int PMAXMAX, /二维数组，标志最短路径上的点DMAX, /记录最短路径的长度finalMAX, /标志是否求的它的最短路径i,j,v,w,v0,min; v0=0; while(G.vexsv0!=u) v0+; for(v=0;vG.vexnum;+v) /初始化Dv=G.arcsv0v; finalv=0; for(w=0;wG.vexnum;w+) Pvw=0; if(DvInfinity) Pvv0=1; Pvv=1; Dv0=0;finalv0=1; for(i=1;iG.vexnum;i+) /循环求出各个最短路径min=Infinity; for(w=0;wG.vexnum;+w) if(!finalw) if(Dwmin) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 - - - - - - - - - 精选文档6 v=w; min=Dw; finalv=1; for(w=0;wG.vexnum;w+) if(!finalw & (min+G.arcsvwDw) /修改最短路径 Dw=min+G.arcsvw; for(j=0;jG.vexnum;j+) Pwj=Pvj; Pww=1; printf(从已知点到其他各点的最短路径为： n); for(v=0;vG.vexnum;v+) if(finalv) printf(%c-%c 的最短路径长度为 %d ，路径为： ,u,G.vexsv,Dv); for(w=0;wG.vexnum;w+) if(Pvw) printf( %c ,G.vexsw); printf(n); void main() MGraph G; G=Creat_MGraph(); M_DFSTraverse(G); M_BFSTraverse(G); if(G.kind=U) MiniSpanTree_PRIM(G,a); /无向图就求它的最小生成树else ShortestPath_DIJ(G,a); /有向图就求它的最短路径 4. 按 F7 键，或工具图标进行工程的建立，如有错误，根据错误显示区中的提示，改正错误，重新建立应用程序；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 13 页 - - - - - - - - - 精选文档7 5按 Ctrl+F5 键，或工具图标进行工程的执行。6. 新建工程 /Win32 Console Application ，选择输入位置：输入工程的名称：图的存储结构转换；按“确定”按钮，选择“An Empty Project ” ，再按“完成”按钮，7. 新建文件 /C+ Source File ，选中“添加到工程的复选按钮”，输入文件名“1. cpp” ，按“确定”按钮，在显示的代码编辑区内输入如下的参考程序: #include #include #define MAX 5 #define INF 100000 int visitMAX=0; typedef struct mgraph int edgesMAXMAX; int n,e; MGraph; typedef 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=mg.n; ArcNode *p; alg=(ALGraph *)malloc(sizeof(ALGraph); for(i=0;iadjlisti.firstarc=NULL; for(i=0;i=0;j-) if(mg.edgesij!=0) p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=j; p-nextarc=alg-adjlisti.firstarc; alg-adjlisti.firstarc=p; alg-n=mg.n; alg-e=mg.e; void ALtoM(ALGraph *alg,MGraph &mg) int i=0,n=alg-n; ArcNode *p; for(i=0;iadjlisti.firstarc; while(p) mg.edgesip-adjvex=1; p=p-nextarc; mg.n=alg-n; mg.e=alg-e; void PrintMGraph(MGraph mg) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 13 页 - - - - - - - - - 精选文档9 for(int i=0;iMAX;i+) for(int j=0;jMAX;j+) printf(%-3d,mg.edgesij); printf(n); printf(the num of edge is:%-3dn,mg.e); printf(the num of vertex is:%-3dn,mg.n); 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-nextarc; printf(n); void main() MGraph mg; ALGraph *alg; mg.n=5;mg.e=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;img.n;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 13 页 - - - - - - - - - 精选文档10 for(int j=0;jmg.n;j+) mg.edgesij=aij; printf(邻接矩阵表示图:n); PrintMGraph(mg); MtoAL(mg,alg); printf(转化为邻接表表示图:n); PrintALGraph(alg); ALtoM(alg,mg); printf(转化为邻接矩阵表示图:n); PrintMGraph(mg); 8. 按 F7 键，或工具图标进行工程的建立，如有错误，根据错误显示区中的提示，改正错误，重新建立应用程序；9. 按 Ctrl+F5 键，或工具图标进行工程的执行。六、实验结果：（1）无向图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - 精选文档11 （2）有向图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 13 页 - - - - - - - - - 精选文档12 （3）图的存储结构的转换名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - 精选文档13 五、实验总结及心得体会：从一个顶点出发只能访问到它所在连通分量的各顶点。如果有回路存在，一个顶点被访问之后又可能沿回路回到该顶点，为了避免对同一个顶点多次访问，在遍历过程中必须记下已经访问过的顶点，通常利用一维辅助数组记录顶点被访问的情况。六、对本实验过程及方法、手段的改进建议：报告评分：指导教师签字：批阅日期：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -