资源描述
-实习报告实验名称:基本算法演示程序日期:2017年 7月 7日*:李琛*:20153204班级:信1501-2指导教师:陈娜1实验题目4、Prim 算法 输入:无向图(顶点序列,边序列) 功能要求:输出最小生成树的各组成边及最小生成树的权值 5、Kruskal 算法 输入:无向图(顶点序列,边序列) 功能要求:输出最小生成树的各组成边及最小生成树的权值 6、Floyd 算法 输入:有向图(顶点序列,有向边序列) 功能要求:输出各顶点对间最短路径和路径长度 7、Dijkstra 算法 输入:有向图(顶点序列,有向边序列),起始顶点 功能要求:输出起始顶点到其它各顶点的最短路径和路径长度2需求分析 4、Prim 算法 输入:无向图(顶点序列,边序列) 功能要求:输出最小生成树的各组成边及最小生成树的权值 5、Kruskal 算法 输入:无向图(顶点序列,边序列) 功能要求:输出最小生成树的各组成边及最小生成树的权值 6、Floyd 算法 输入:有向图(顶点序列,有向边序列) 功能要求:输出各顶点对间最短路径和路径长度 7、Dijkstra 算法 输入:有向图(顶点序列,有向边序列),起始顶点 功能要求:输出起始顶点到其它各顶点的最短路径和路径长度3概要设计 4、Prim 算法 structAMGraphpVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;/Prim算法辅助结构体structcloseVerTe*Type adjve*;ArcType lowcost;*defineMa*Int 32767 /极大值*defineMVNum 100 /最大顶点数typedefcharVerTe*Type; /顶点类型为字符型typedefintArcType; /边的权值为整型5、Kruskal 算法 *defineMa*Int 32767 /极大值*defineMVNum 100 /最大顶点数typedefcharVerTe*Type; /顶点类型为字符型typedefintArcType; /边的权值为整型structAMGraphkVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;/kruskal算法辅助结构体structEdgeVerTe*Type Head;VerTe*Type Tail;ArcType lowcost;6、Floyd 算法 *defineMa*Int 32767 /极大值*defineMVNum 100 /最大顶点数typedefcharVerTe*Type; /顶点类型为字符型typedefintArcType; /边的权值为整型int D100100, Path100100;structAMGraphfVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;7、Dijkstra 算法 *defineMa*Int 32767 /极大值*defineMVNum 100 /最大顶点数typedefcharVerTe*Type; /顶点类型为字符型typedefintArcType; /边的权值为整型int S100, D100, min, Path100;structAMGraphdVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;函数曾今调用关系4详细设计 Head.h*pragmaonce*include*includeusingnamespace std;/图的邻接矩阵存储表示*defineMa*Int 32767 /极大值*defineMVNum 100 /最大顶点数typedefcharVerTe*Type; /顶点类型为字符型typedefintArcType; /边的权值为整型void prim();void kruskal();void dijkstra();void floyd();Main.cpp*includehead.hvoid main()int a=1;cout 请输入想要运行的算法序号:endl;cout 1、prim算法endl;cout 2、kruskal算法 endl;cout 3、dijkstra算法 endl;cout 4、floyd算法 endl; while (a != 0)cout a;switch (a)case 1:prim(); break;case 2:kruskal(); break;case 3:dijkstra(); break;case 4:floyd(); break;Prim.cpp*includehead.hstructAMGraphpVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;/Prim算法辅助结构体structcloseVerTe*Type adjve*;ArcType lowcost;int LocateVe*(AMGraphpG, VerTe*Typeu)int i = 0;while (G.ve*si != u) i+;return i;/使用邻接矩阵表示法创建无向图int CreateUDN(AMGraphp &G)int i, j, k,w;char v1, v2;cout G.ve*num G.arum; /输入总顶点数,总边数for (i = 0; i G.ve*num; +i) /依次输入点的信息cout 输入第;cout i+1;cout G.ve*si;for (i = 0; i G.ve*num; +i) /权值初始化为最大值for (j = 0; j G.arum; +j)G.arcsij=Ma*Int;for (k = 0; k G.arum; +k) /构造邻接矩阵cout v1 v2;i = LocateVe*(G, v1);j = LocateVe*(G, v2);cout w;G.arcsij = w;G.arcsji = G.arcsij; return 0;/Prim算法最小生成树的构造void MinispanTree_prim(AMGraphpG, inta, AMGraphp &T)int k = a-1, i, j, m, lowcost;/规定从第a个顶点开始close closedge100;/辅助数组的声明T.ve*num = G.ve*num; /T的初始化for (i = 0; iG.ve*num; i+)T.ve*si = G.ve*si; for (i = 0; iG.ve*num; i+)for (j = 0; jG.ve*num; j+) T.arcsij = -1;for (i = 0; iG.ve*num; i+)closedgei.adjve* = k;closedgei.lowcost = G.arcski;closedgek.lowcost = 0;/把第0个结点并入最小生成树for (m = 1; mG.ve*num; m+)lowcost = Ma*Int; for (i = 1; iclosedgei.lowcost&closedgei.lowcost != 0 & closedgei.lowcost != -1)lowcost = closedgei.lowcost; k = i;T.arcsclosedgek.adjve*k = lowcost;/在T中存最小生成树的边T.arcskclosedgek.adjve* = lowcost;closedgek.lowcost = 0;/把第k个结点并入最小生成树for (i = 1; iG.ve*num; i+)if (G.arcskiclosedgei.lowcost&G.arcski != -1) | closedgei.lowcost = -1)closedgei.lowcost = G.arcski;closedgei.adjve* = k;/邻接矩阵输出void AMGout(AMGraphpT)int i ,j,k;cout 点的信息分别为:endl;for (i = 0; i T.ve*num; i+)cout T.ve*si ;cout endl;cout 邻接矩阵为: endl;for (j = 0; j T.ve*num; j+)for (k = 0; k = 32767 | T.arcsjk0)cout * ;elsecout T.arcsjk ;cout endl;/调用函数void prim()AMGraphp M; AMGraphp N;CreateUDN(M);AMGout(M);int a;cout a;MinispanTree_prim(M, a, N);cout 最小生成树为:endl;AMGout(N);Kruskal.cpp*includehead.hstructAMGraphkVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;/kruskal算法辅助结构体structEdgeVerTe*Type Head;VerTe*Type Tail;ArcType lowcost;/顶点定位int LocateVe*(AMGraphkG, VerTe*Typeu)int i = 0;while (G.ve*si != u) i+;return i;/创建无向图int CreateUD(AMGraphk &G)int i, j, k, w;char v1, v2;cout G.ve*num G.arum; /输入总顶点数,总边数for (i = 0; i G.ve*num; +i) /依次输入点的信息cout 输入第;cout i + 1;cout G.ve*si;for (i = 0; i G.ve*num; +i) /权值初始化为最大值for (j = 0; j G.arum; +j)G.arcsij = Ma*Int;for (k = 0; k G.arum; +k) /构造邻接矩阵cout v1 v2;i = LocateVe*(G, v1);j = LocateVe*(G, v2);cout w;G.arcsij = w;G.arcsji = G.arcsij;return 0;int Ve*setMVNum;void kruskal()Edge a100;AMGraphk G;CreateUD(G);int i, j, k = 0;for (i = 0; i G.arum; i+)for (j = i+1; j 0 & G.arcsijMa*Int)ak.Head = G.ve*si;ak.Tail = G.ve*sj;ak.lowcost = G.arcsij;k+;int v1, v2, vs1, vs2;Edge b;for (i = 0; i G.arum; i+)for (j = i+1; j aj.lowcost)b = ai;ai = aj;aj = b;for (i = 0; i G.ve*num; i+)Ve*seti = i;for (i = 0; i G.arum; i+)v1 = LocateVe*(G, ai.Head);v2 = LocateVe*(G, ai.Tail);vs1 = Ve*setv1;vs2 = Ve*setv2;if (vs1 != vs2)cout ai.Head ai.Tail endl;for (j = 0; j G.ve*num; j+)if (Ve*setj = vs2)Ve*setj = vs1;Dijkstra.cpp*includehead.hint S100, D100, min, Path100;structAMGraphdVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;int LocateVe*(AMGraphdG, VerTe*Typeu)int i = 0;while (G.ve*si != u) i+;return i;int CreateUD(AMGraphd &G)int i, j, k, w;char v1, v2;cout G.ve*num G.arum; /输入总顶点数,总边数for (i = 0; i G.ve*num; +i) /依次输入点的信息cout 输入第;cout i + 1;cout G.ve*si;for (i = 0; i G.ve*num; +i) /权值初始化为最大值for (j = 0; j G.ve*num; +j)G.arcsij = Ma*Int;for (k = 0; k G.arum; +k) /构造邻接矩阵cout v1 v2;i = LocateVe*(G, v1);j = LocateVe*(G, v2);cout w;G.arcsij = w;return 0;void dijkstra()AMGraphd G;CreateUD(G);int i,n, v, v0,w;cout 请输入起始点: v0;v0 = v0 - 1;n = G.ve*num;for (v = 0; v n; v+)Sv = false;Dv = G.arcsv0v;if (Dv Ma*Int) Pathv = 0;elsePathv = -1;Sv0 = true;Dv0 = 0;for (i = 1; i n; i+)min = Ma*Int;for (w = 0; w n; w+)if (!Sw & Dw min)v = w;min = Dw;Sv = true;for (w = 0; w n; w+)if (!Sw & (Dv + G.arcsvw Dw)Dw = Dv + G.arcsvw;Pathw = v;int * = 0;cout 点到各点的最短路径长度 endl;while (S*)cout D* ;*+;cout endl;* = 0;cout 各终点的前驱点 endl;while (S*)cout Path*+1 ;*+;cout endl;Floyd.cpp*includehead.hint D100100, Path100100;structAMGraphfVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;int LocateVe*(AMGraphfG, VerTe*Typeu)int i = 0;while (G.ve*si != u) i+;return i;int CreateUD(AMGraphf &G)int i, j, k, w;char v1, v2;cout G.ve*num G.arum; /输入总顶点数,总边数for (i = 0; i G.ve*num; +i) /依次输入点的信息cout 输入第;cout i + 1;cout G.ve*si;for (i = 0; i G.ve*num; +i) /权值初始化为最大值for (j = 0; j G.arum; +j)G.arcsij = Ma*Int;for (k = 0; k G.arum; +k) /构造邻接矩阵cout v1 v2;i = LocateVe*(G, v1);j = LocateVe*(G, v2);cout w;G.arcsij = w;return 0;void floyd()AMGraphf G;CreateUD(G);int i, j, k;for ( i = 0; i G.ve*num; i+)for ( j = 0; j G.ve*num; j+)Dij = G.arcsij;if (Dij Ma*Int) Pathij = i;else Pathij = -1;for ( k = 0; k G.ve*num; k+)for ( i = 0; i G.ve*num; i+)for ( j = 0; j G.ve*num; j+)if (Dik + Dkj Dij)Dij = Dik + Dkj;Pathij = Pathkj;for (i = 0; i G.ve*num; i+)for ( j = 0; j G.ve*num; j+)if (Dij = Ma*Int)cout * ;elsecout Dij ;cout endl;for (i = 0; i G.ve*num; i+)for (j = 0; j G.ve*num; j+)if (Pathij = -1)cout * ;elsecout Pathij +1 ;cout endl;cout 请输入始终点: a b;cout 中间的路径点为:1)cout Pathab ;b = Pathab;5调试分析调试过程中出现了很比较多的问题,基本是课本上的代码出现的未知函数6使用说明在主菜单中,输入1,2,3,4来选择算法,按照程序的提示来输入等候结果7测试结果. z.
展开阅读全文