数据结构实验十图的应用实验.doc

实验报告十一 图的应用实验 班级： 姓名： 学号： 专业： 实验目的： 1、掌握图的存储结构及创建算法。 2、掌握图的最小生成树prime算法. 3、掌握图的最短路径Dijkstra、Floyd算法。 4、 实验内容： [实现提示] （同时可参见教材算法）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。 #include using namespace std; const int MaxSize 12; const int INFINITY 65535; template class Mgraph public: Mgraph T a[],int n,int e ; void PGraph ; void Prim int n ; private: T vertex[MaxSize]; int a[MaxSize]; int arc[MaxSize][MaxSize]; 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; i vertexNum; i++ vertex[i] a[i]; for i 0; i vertexNum; i++ for j 0; j vertexNum; j++ arc[i][j] 0; for k 0; k arcNum; k++ cout 请输入第 k+1 条边 格式：顶点1 顶点2 :; cin i j; arc[i][j] 1; arc[j][i] 1; template void Mgraph ::createUW T a[],int n,int e int w; vertexNum n; arcNum e; int i,j,k; for i 0; i vertexNum; i++ vertex[i] a[i]; for i 0; i vertexNum; i++ for j 0; j vertexNum; j++ arc[i][j] INFINITY; for k 0; k arcNum; k++ cout 请输入第 k+1 条边 格式：顶点1 顶点2 权值 :; cin i j w; arc[i][j] w; arc[j][i] w; template void Mgraph ::createHG T a[],int n,int e vertexNum n; arcNum e; int i,j,k; for i 0; i vertexNum; i++ vertex[i] a[i]; for i 0; i vertexNum; i++ for j 0; j vertexNum; j++ arc[i][j] 0; for k 0; k arcNum; k++ cout 请输入第 k+1 条边 格式：顶点1 顶点2 :; cin i j; arc[i][j] 1; template void Mgraph ::createHW T a[],int n,int e int w; vertexNum n; arcNum e; int i,j,k; for i 0; i vertexNum; i++ vertex[i] a[i]; for i 0; i vertexNum; i++ for j 0; j vertexNum; j++ arc[i][j] INFINITY; for k 0; k arcNum; k++ cout 请输入第 k+1 条边 格式：顶点1 顶点2 权值 :; cin i j w; arc[i][j] w; template void Mgraph ::PGraph int i,j; for i 0;i vertexNum;i++ for j 0;j vertexNum;j++ cout arc[i][j] ends; cout endl; template Mgraph ::Mgraph T a[],int n,int e int i; cout 若创建无