实验十一图的应用实验.doc

实验报告十一 图的应用实验班级： 姓名： 学号： 专业： 一、 实验目的：1、掌握图的存储结构及创建算法。2、掌握图的最小生成树prime算法.3、掌握图的最短路径Dijkstra、Floyd算法。二、 实验内容： 实现提示 （同时可参见教材及ppt上的算法）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义及类的定义：#includeusing namespace std;const int MaxSize=12; const int INFINITY=65535;template class Mgraphpublic: Mgraph(T a,int n,int e); void PGraph();void Prim(int n);private: T vertexMaxSize; int aMaxSize;int arcMaxSizeMaxSize; int vertexNum,arcNum; void createUG(T a,int n,int e); void createUW(T a,int n,int e); void createHG(T a,int n,int e); void createHW(T a,int n,int e); ;struct bian int nearvex;1、邻接矩阵存储结构类定义与实现。自定义如下：template void Mgraph:createUG(T a,int n,int e) vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=0; for (k=0; karcNum; k+) cout请输入第k+1ij; arcij=1; arcji=1; template void Mgraph:createUW(T a,int n,int e) int w; vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=INFINITY; for (k=0; karcNum; k+) cout请输入第k+1ijw; arcij=w; arcji=w; templatevoid Mgraph:createHG(T a,int n,int e) vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=0; for (k=0; karcNum; k+) cout请输入第k+1ij; arcij=1; templatevoid Mgraph:createHW(T a,int n,int e) int w; vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=INFINITY; for (k=0; karcNum; k+) cout请输入第k+1ijw; arcij=w; template void Mgraph:PGraph()int i,j;for(i=0;ivertexNum;i+)for(j=0;jvertexNum;j+)coutarcijends;coutendl;templateMgraph:Mgraph(T a,int n,int e) int i; couti; switch(i) case 1: createUW(a,n,e);break; case 2: createUG(a,n,e);break; case 3: createHW(a,n,e);break; case 4: createHG(a,n,e);break; 2、最小生成树prime算法 实现提示 （同时可参见教材p175页算法）库函数和常量定义：templatevoid Mgraph:Prim(int n) float min; int v,i,j; int bMaxSize; bian *line=new biann; for(i=1;in;i+) bi=arc0i; linei.nearvex=0; for(i=1;in;i+) coutbiendl; b0=0; line0.nearvex=-1; for(i=1;in;i+) min=INFINITY; v=0; for(j=0;jn;j+) if(bj!=0&bjmin) v=j; min=bj; if(v) av=bv; bv=0; for(j=0;jn;j+) if(bj!=0&arcvjbj) bj=arcvj;linej.nearvex=v; for(j=1;jn;j+) cout从j到linej.nearvex距离为ajendl;int main() int a5=1,2,3,4,5; Mgraph picture(a,5,8); int b5=0,0,0,0,0; picture.Prim(5); return 0;（1）图的储结构定义：自定义如下：（可自已定义）（2）prime算法测试结果粘贴如下：3、最短路径算法 实现提示 （同时可参见教材p187-192页算法）库函数和常量定义：#includeusing namespace std;const int MaxSize=12; const int INFINITY=65535;template class Mgraphpublic: Mgraph(T a,int n,int e); void PGraph();void ShortestPath(int n,int v);private: T vertexMaxSize; int arcMaxSizeMaxSize; int vertexNum,arcNum; void createUG(T a,int n,int e); void createUW(T a,int n,int e); void createHG(T a,int n,int e); void createHW(T a,int n,int e);float *dist;int *path;int *s; ;template void Mgraph:createUG(T a,int n,int e) vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=0; for (k=0; karcNum; k+) cout请输入第k+1ij; arcij=1; arcji=1; template void Mgraph:createUW(T a,int n,int e) int w; vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=INFINITY; for (k=0; karcNum; k+) cout请输入第k+1ijw; arcij=w; arcji=w; templatevoid Mgraph:createHG(T a,int n,int e) vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=0; for (k=0; karcNum; k+) cout请输入第k+1ij; arcij=1; templatevoid Mgraph:createHW(T a,int n,int e) int w; vertexNum=n; arcNum=e; int i,j,k; for (i=0; ivertexNum; i+) vertexi=ai; for (i=0; ivertexNum; i+) for (j=0; jvertexNum; j+) arcij=INFINITY; for (k=0; karcNum; k+) cout请输入第k+1ijw; arcij=w; template void Mgraph:PGraph()int i,j;for(i=0;ivertexNum;i+)for(j=0;jvertexNum;j+)coutarcijends;coutendl;templateMgraph:Mgraph(T a,int n,int e) int i; couti; switch(i) case 1: createUW(a,n,e);break; case 2: createUG(a,n,e);break; case 3: createHW(a,n,e);break; case 4: createHG(a,n,e);break; （1）从某个源点到其余各顶点的最短路径（Dijkstra）templatevoid Mgraph:ShortestPath(int n,int v) float min; int u; dist=new floatn; s=new intn; path=new intn; for(int i=0;in;i+) disti=arciv; si=0; if(i!=v&distiINFINITY) pathi=v; else pathi=-1; sv=1; for(int j=0;jn-1;j+) min=INFINITY; u=v; if(!sj&distjmin) u=j; min=distj; su=1; for(int w=0;wn;w+) if(!sw&distu+arcuwdistw) distw=distu+arcuw; pathw=u; for(i=0;in;i+) if(disti!=INFINITY) j=i; coutv到i的最短距离为distiendl; cout最短路程为; while(j!=1) coutpathj; j=pathj; coutendl; 测试结果粘贴如下：（2）每一对顶点之间的最短路径templatevoid Mgraph:Floyd(int n) int aMaxSizeMaxSize; for(int i=0;in;i+) for(int j=0;jn;j+) aij=arcij; if(i!=j&aijINFINITY) pat