欢迎来到天天文库
浏览记录
ID:61041393
大小:292.05 KB
页数:28页
时间:2021-01-20
《测绘软件实习报告.docx》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、实验一图的创建、遍历、及其MST的构建实验目的ö图的创建。ö基于深度优先的图的遍历算法的设计与实现。ö基于广度优先的图的遍历算法的设计与实现。ö基于Prim算法的最小生成树的构建。ö基于Kruskal算法的最小生成树的构建。实验过程#include#include”KJL_Queue.h”usingnamespacestd;//定义为prim服务的辅助结点structprimnode{public:charbegvex;//开始结点charendvex;//结束结点intlowcost;//中间权值};classKJL_Graphmtx//图的邻接矩阵定义{public:
2、KJL_Graphmtx(intsz=DefaultVertices);//构造函数~KJL_Graphmtx()//析构函数{delete[]VerticesList;delete[]Edge;}boolGraphEmpty()//判断图是否为空{if(numEdges==0)returntrue;elsereturnfalse;}boolGraphFull()//判断图是否为满{if(numVertices==maxVertices
3、
4、numEdges==maxVertices*(maxVertices-1)/2)returntrue;elsereturnfalse;}intNumber
5、OfVertices()//返回当前顶点数{returnnumVertices;}intNumberOfEdges()//返回当前边数{returnnumEdges;}chargetValue(inti)//取顶点i的值,i不合理返回0{returni>=0&&i<=numVertices?VerticesList[i]:NULL;}intgetWeight(intv1,intv2)//取边(v1,v2)上的权值{returnv1!=-1&&v2!=-1?Edge[v1][v2]:0;}intgetFirstNeighbor(intv);//取顶点v的第一个邻接顶点intgetNextNei
6、ghbor(intv,intw);//取v的邻接顶点w的下一邻接顶点boolinsertVertex(charvertex);//插入顶点vertexboolinsertEdge(intv1,intv2,intweight);//插入边(v1,v2),权为weightboolremoveVertex(intv);//删去顶点v和所有与它相关联的边boolremoveEdge(intv1,intv2);//在图中删去边(v1,v2)intgetVertexPos(charvertex)//给出顶点vertex的位置,如果该顶点不在图内则返回-1{for(inti=0;i7、;i++)if(VerticesList[i]==vertex)returni;return-1;}intmini();//求图中所有边的最小权值boolinput();//输入函数booloutput();//输出函数voidkruskal();//kruskal算法voidprim();//prim算法protected:intmaxVertices;//图中最大顶点数intnumEdges;//图中当前边数intnumVertices;//图中当前顶点数private:char*VerticesList;//顶点表int**Edge;//邻接矩阵intvisit[50];//便利时的辅8、助工具primnodecloseedge[50];//为实现prim函数的辅助结点};KJL_Graphmtx::KJL_Graphmtx(intsz)//构造函数{maxVertices=sz;numVertices=0;numEdges=0;inti,j;VerticesList=newchar[maxVertices];//创建顶点表数组Edge=(int**)newint*[maxVertices];//创建邻接矩阵数组for(i=0;i9、接矩阵初始化for(j=0;j0&&Edge[v][i]
7、;i++)if(VerticesList[i]==vertex)returni;return-1;}intmini();//求图中所有边的最小权值boolinput();//输入函数booloutput();//输出函数voidkruskal();//kruskal算法voidprim();//prim算法protected:intmaxVertices;//图中最大顶点数intnumEdges;//图中当前边数intnumVertices;//图中当前顶点数private:char*VerticesList;//顶点表int**Edge;//邻接矩阵intvisit[50];//便利时的辅
8、助工具primnodecloseedge[50];//为实现prim函数的辅助结点};KJL_Graphmtx::KJL_Graphmtx(intsz)//构造函数{maxVertices=sz;numVertices=0;numEdges=0;inti,j;VerticesList=newchar[maxVertices];//创建顶点表数组Edge=(int**)newint*[maxVertices];//创建邻接矩阵数组for(i=0;i9、接矩阵初始化for(j=0;j0&&Edge[v][i]
9、接矩阵初始化for(j=0;j0&&Edge[v][i]
此文档下载收益归作者所有