实验Prim最小生成树算法的实现.doc

计算机与信息学院实验报告系软件工程专业软件工程年级07成绩姓名学号实验室T514机号67实验时间2008年11月3日8：00至9：302008年11月10日8：00至9：30教师签字实验（三） Prim最小生成树算法的实现一、实验目的和要求1. 掌握图的基本操作设计与实现2. 利用Prim算法求网络的最小生成树二、实验内容和原理1. 图的基本操作的实现（第一次实验完成）问题描述：。2. Prim算法的实现（第二次实验完成）三、实验环境1. 硬件环境：PC机2. 软件环境：Turbo C 3.0四、算法描述及实验步骤1. 算法描述（可以用流程图、伪代码或源程序描述）l 图的基本操作 构造图的基本存储结构ypedef char VERTEX;typedef int ADJACENCY_MATRIXMAXNUMMAXNUM;typedef VERTEX VERTEX_ARRAYMAXNUM;typedef struct VERTEX_ARRAY ver;ADJACENCY_MATRIX arc;int vernum, arcnum; AMGRAPH;typedef AMGRAPH GRAPH;/初始化图操作void Init(GRAPH *pG, int vernum) int i, j;pG-vernum=vernum;for(i=1; ivernum; i+)pG-veri=A + i;for(i=1;ivernum;i+)for (j=1;jvernum;j+) pG-arcij=INFINITY;pG-arcji=INFINITY;获取图的顶点VERTEX* GetVertex(GRAPH *pG, int index)if ( index 0 & index vernum )return &(pG-verindex); else printf(The index is not valid (%d)n,index);return NULL;设置图的权值int SetEdge(GRAPH* pG, int from, int to, int weight) if ( ( from0 & fromvernum )& ( to0 & to vernum )& weight = 0 )pG-arcfromto = weight;pG-arctofrom = weight;return 1; else printf(The data is not valid (%d,%d,%d)n,from,to,weight);return 0;删除边的操作int DeleteEdge(GRAPH* pG, int from, int to) if ( ( from 0 & from vernum )& ( to 0 & to vernum ) ) pG-arcfromto=INFINITY;pG-arctofrom=INFINITY;return 1; else printf(The data is not valid (%d,%d)n,from,to);return 0;获取边的操作int GetEdge(GRAPH* pG, int from, int to) if ( ( from0 & fromvernum )& ( to0 & tovernum ) ) return pG-arcfromto;else printf(The data is not valid (%d,%d)n,from,to);return INFINITY;获取图的顶点数int GetVertexNumber(GRAPH *pG) return pG-vernum;删除操作void Destroy(GRAPH *pG) pG-vernum = 0;从顶点vertex出发对图pG深度优先搜索遍历的递归算法void rdfs(GRAPH* pG, int vertexIndex, int visited) int i;visitedvertexIndex=1;printf(%c-,*GetVertex(pG, vertexIndex);for (i=1; i=GetVertexNumber(pG); i+) if ( GetEdge(pG, vertexIndex, i)!=INFINITY & visitedi=0 )rdfs(pG, i, visited);/*对图pG按深度优先搜索遍历*/void dfs(GRAPH *pG) int *visited;int i;visited=(int*)malloc(sizeof(int)*(GetVertexNumber(pG)+1);for (i=1; i=GetVertexNumber(pG); i+) visitedi = 0;printf(nThe output of recursive depth first searh:n);for (i=1; i=GetVertexNumber(pG); i+) if ( visitedi = 0 )rdfs(pG, i, visited);printf(nEnd of the output of recursive depth first searh:n);l Prim算法typedef struct CloseEdge int adjVer;/顶点的序号域int lowCost;/权值 CLOSEEDGE;void Prim(GRAPH* pG, int ver) CLOSEEDGE* closeEdge;int vernum;int i, j, vertex, minWeight, weight;vernum=GetVertexNumber(pG);closeEdge=(CLOSEEDGE*)malloc(sizeof(CLOSEEDGE)*(vernum+1);/*根据开始顶点ver对closeEdge进行初始化*/for(i=1; iarcveri;closeEdgever.lowCost = 0;printf(nPrim Algorithm begin from vertex %dn, ver);for ( i=1; ivernum; i+) /*查找具有最小权值、有且仅有一个顶点在部分已生成最小生成树的边，记录在树外的顶点*/vertex=1;minWeight=INFINITY;for (j=1;j=vernum;j+) if(closeEdgej.lowCost!=0 & closeEdgej.lowCostminWeight)minWeight=closeEdgej.lowCost;vertex=j;/*输出选择的边及其权值*/printf(%d-%dt%dn, closeEdgevertex.adjVer, vertex, minWeight);/*根据新加入的顶点vertex，对closeEdge进行必要的修改*/closeEdgevertex.lowCost = 0;for (j=1; j=vernum; j+) weight = GetEdge(pG, vertex, j);/*获取从顶点vertex到顶点j的权值*/if ( weight!=INFINITY & weightarcvertexj;closeEdgej.adjVer;l 主控程序构造一个带权的无向图网void CreateConnectedNetwork(GRAPH *pG) Init(pG, 7);SetEdge(pG, 1, 2, 3);SetEdge(pG, 1, 3, 2);SetEdge(pG, 1, 4, 4);SetEdge(pG, 1, 6, 6);SetEdge(pG, 2, 3, 1);SetEdge(pG, 2, 5, 4);SetEdge(pG, 3, 4, 1);SetEdge(pG, 3, 5, 3);SetEdge(pG, 4, 5, 5);SetEdge(pG, 4, 6, 3);SetEdge(pG, 4, 7, 5);SetEdge(pG, 5, 7, 7);SetEdge(pG, 6, 7, 6);主函数int main()GRAPH G;CreateConnectedNetwork(&G);Prim(&G, 1);Prim(&G, 3);Prim(&G, 7);return 1;2. 实验步骤l 输入源代码l 进行编译l 进行测试，使用的测试用例：输入：预期输出：五、调试过程1. 编译过程编译后出现如下错误提示。出错原因很隐蔽，只是一个比较简单的错误。只要把int DeleteEdge(GRAPAH* pG, int from, int to)改为int DeleteEdge(GRAPH* pG, int from, int to)就可不用成功，即但却花费了我很长时间进行调试。2. 调试过程输入：在主函数中执行“Prim(&G, 2);Prim(&G, 5);”这两条语句，分别从第二个顶点和第五个顶点进行Prim算法，生成最小生成树。预期输出：实际输出：与预期输出一样。分析：当从第二个顶点开始，以此作为生成树的初始状态，然后找出与其之间权值最小的顶点3，并把顶点3添加到该生成树中，以此类推找出与顶点3之间权值最小的顶点，再把找出的顶点添加到生成树中，直到最后一个顶点添加到生成树上时得到所求的生成数，即最小生成树。从顶点5开始的情况也类似。六、实验结果用与测试用例不同的输入数据运行算法，写出得到的结果，并分析结果是否正确。输入：在主函数中执行“Prim(&G, 1);Prim(&G, 3);Prim(&G, 7);”这三条语句，分别从第一个顶点第三个顶点和第七个顶点进行Prim算法，生成最小生成树。输出结果：结果分析：当从第一个顶点开始，以此作为生成树的初始状态，然后找出与其之间权值最小的顶点2，并把顶点2添加到该生成树中，以此类推找出与顶点2之间权值最小的顶点，再把找出的顶点添加到生成树中，直到最后一个顶点添加到生成树上时得到所求的生成数，即最小生成树。从顶点3和7开始的情况也类似。从这三个顶点开始的个边权值之和都为15，完全满足了最小生成树。七、总结通过本次上机实验我大体上掌握了图的基本操作设计与实现并学会利用Prim算法求网络的最小生成树。虽然本次实验做起来是比较成功的，但我感觉自己花费的时间很多，实验效率很低，很难理解参考代码，所以实验时有一部分用了参考代码。然而我感觉自己还是很有收获的，基本上是读懂了参考代码，领悟了一些编程思想。附录：如果原来的算法中发现了错误，在附录中附上改正后的算法实现。#include #include #include #define INFINITY INT_MAX#define MAXNUM 20typedef char VERTEX;typedef int ADJACENCY_MATRIXMAXNUMMAXNUM;typedef VERTEX VERTEX_ARRAYMAXNUM;typedef struct VERTEX_ARRAY ver;ADJACENCY_MATRIX arc;int vernum, arcnum; AMGRAPH;typedef AMGRAPH GRAPH;/*初始化图操作*/void Init(GRAPH *pG, int vernum) int i, j;pG-vernum=vernum;for(i=1; ivernum; i+)pG-veri=A + i;for(i=1;ivernum;i+)for (j=1;jvernum;j+) pG-arcij=INFINITY;pG-arcji=INFINITY;/*获取图的顶点*/VERTEX* GetVertex(GRAPH *pG, int index)if ( index 0 & index vernum )return &(pG-verindex); else printf(The index is not valid (%d)n,index);return NULL;/*设置图的权值*/int SetEdge(GRAPH* pG, int from, int to, int weight) if ( ( from0 & fromvernum )& ( to0 & to vernum )& weight = 0 )pG-arcfromto = weight;pG-arctofrom = weight;return 1; else printf(The data is not valid (%d,%d,%d)n,from,to,weight);return 0;/*删除边的操作*/int DeleteEdge(GRAPH* pG, int from, int to) if ( ( from 0 & from vernum )& ( to 0 & to vernum ) ) pG-arcfromto=INFINITY;pG-arctofrom=INFINITY;return 1; else printf(The data is not valid (%d,%d)n,from,to);return 0;/*获取边的操作*/int GetEdge(GRAPH* pG, int from, int to) if ( ( from0 & fromvernum )& ( to0 & tovernum ) ) return pG-arcfromto;else printf(The data is not valid (%d,%d)n,from,to);return INFINITY;/*获取图的顶点数*/int GetVertexNumber(GRAPH *pG) return pG-vernum;/*删除操作*/void Destroy(GRAPH *pG) pG-vernum = 0;/*从顶点vertex出发对图pG深度优先搜索遍历的递归算法*/void rdfs(GRAPH* pG, int vertexIndex, int visited) int i;visitedvertexIndex=1;printf(%c-,*GetVertex(pG, vertexIndex);for (i=1; i=GetVertexNumber(pG); i+) if ( GetEdge(pG, vertexIndex, i)!=INFINITY & visitedi=0 )rdfs(pG, i, visited);/对尚未被访问过的顶点递归调用rdfs深度优先搜索/*对图pG按深度优先搜索遍历*/void dfs(GRAPH *pG) int *visited;int i;visited=(int*)malloc(sizeof(int)*(GetVertexNumber(pG)+1);for (i=1; i=GetVertexNumber(pG); i+) visitedi = 0;printf(nThe output of recursive depth first searh:n);for (i=1; i=GetVertexNumber(pG); i+) if ( visitedi = 0 )rdfs(pG, i, visited);printf(nEnd of the output of recursive depth first searh:n);/* 构造一个带权的无向图网*/void CreateConnectedNetwork(GRAPH *pG) Init(pG, 7);SetEdge(pG, 1, 2, 3);SetEdge(pG, 1, 3, 2);SetEdge(pG, 1, 4, 4);SetEdge(pG, 1, 6, 6);SetEdge(pG, 2, 3, 1);SetEdge(pG, 2, 5, 4);SetEdge(pG, 3, 4, 1);SetEdge(pG, 3, 5, 3);SetEdge(pG, 4, 5, 5);SetEdge(pG, 4, 6, 3);SetEdge(pG, 4, 7, 5);SetEdge(pG, 5, 7, 7);SetEdge(pG, 6, 7, 6);typedef struct CloseEdge int adjVer;/顶点的序号域int lowCost;/权 CLOSEEDGE;void Prim(GRAPH* pG, int ver) CLOSEEDGE* closeEdge;int vernum;int i, j, vertex, minWeight, weight;vernum=Get