算法与数据结构实验报告实验六.doc

算法与数据结构实验报告实验六 实验名称： 图的应用 姓名： 卢丽娟 学号： 211006289 专业： 软件工程 班级： 二班 指导教师： 陈亦萍 日期: 2012年6月2日 一、 实验目的本实验是要根据图的性质，利用图的应用，来求解海盗建造的最少费用二、 实验内容与实验步骤实验内容：有N个海岛(标号为1N)分散在一片的海域上，每个海岛之间没有联系。对于任意2个岛，它们之间必须直接或间接可以到达。使用最少的钱数，来完成对这些岛屿的连接。实验步骤：定义一个Find函数，查找各个顶点在图中的位置int Find(int i)/查找顶点在图中的位置/判断是否查找成功if(fi = i)return i; else fi = Find( fi );return fi;再在主函数中调用Find函数，实现对边的求最小权值int main()printf(输入顶点数和边数:n);scanf(%d %d,&n,&m);int i;printf(输入边连接的两个顶点和边的权值:n);for(i = 1; i = m; i+) scanf(%d%d%d,&gi.s,&gi.t,&gi.v);/输入边依附的顶点及权值 sort(g+1,g+m+1);/将其按照升序排列 for(i = 1; i = m; i+) fi = i;report= cnt = 0;int cur = 1; for(i = 1; i = m; i+) int a = Find(gi.s);/其在图中位置 int b = Find(gi.t);/其在图中位置 if(a != b) report+= gi.v; fa = b;cnt+; /求最小costint sumcost = cnt = n-1? report:-1;printf(结果为:n);printf(sumcost=%dn,sumcost);printf(n); return 0;三、 实验环境操作系统winXP，开发平台Microsoft Visual C+6.0四、 实验过程与分析在调试过程中出现很多错误，有些没有定义，还有就是变量没有设好，大小写问题也出现不少，多括号还有少括号，不然就是漏了分号等，很多细节的错误经过慢慢调试被改正。五、 实验结论测试的数据和输出的结果如下：六、 附录#include #include #include using namespace std;#define N 100100struct G/定义图的各变量 int s,t,v;/定义图的顶点和边 bool operator (const G &b) const return v b.v;/对运算符的重载，const g &b是对类g的引用&b,vb.v是对类中的成员v的比较大小，并返回bool型的值;G gN;int fN;int n,m;int report;int cnt;/定义各变量int Find(int i)/查找顶点在图中的位置/判断是否查找成功 if(fi = i)return i;else fi = Find( fi );return fi;/图的遍历int main()printf(输入顶点数和边数:n);scanf(%d %d,&n,&m);int i;printf(输入边连接的两个顶点和边的权值:n);for(i = 1; i = m; i+) scanf(%d%d%d,&gi.s,&gi.t,&gi.v);/输入边依附的顶点及权值 sort(g+1,g+m+1);/将其按照升序排列 for(i = 1; i = m; i+) fi = i; report= cnt = 0; int cur = 1; for(i = 1; i = m; i+)int a = Find(gi.s); int b = Find(gi.t);/其在图中位置 if(a != b) report+= gi.v; fa = b; cnt+; int sumcost = cnt