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

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