数据结构实验报告-最小生成树

ex)malloc(sizeof(TpVex)*7);Р?for(i = 0;i < 20;++i)Р?{Р fscanf(pfile , "%d\t%d\t%d\n" , &a, &b, &c);Р G->EdgeList[i].vhead=a;Р G->EdgeList[i].vtail=b;Р G->EdgeList[i].wght=c;Р printf("%d\t%d\t%d\n", a, b, c);Р vexlist[k]=a;Р k++;Р for (m=0;m<k; m++) {Р if (vexlist[m]==vexlist[k-1])Р k--;Р }Р vexlist[k]=b;Р k++;Р for (m=0;m<k; m++) {Р if (vexlist[m]==vexlist[k-1])Р k--;Р }Р }Р?for (j=0;j<6;j++)Р G->VexList[j].vex=j+1;Р?Р?G->nedge=20;Р?G->nvex=j;Р}Рint main()Р{Р char *filename="/Users/pro/Desktop/实验/数据结构实验3/graph.txt";Р TGraph G;Р int Edges[20][3] = {0};Р read_file(filename,Edges,&G);Р begin(&G);Р create(&G);Р return 0;Р}Р九、程序运行结果:Р运行程序:Р实验成功。Р十、实验结论:Р 克鲁斯卡尔算法是一种能够体现“贪心”的精髓的贪心算法,它所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。Р十一、总结及心得体会:Р 克鲁斯卡尔算法的时间复杂度为O(eloge),因此它相对于普里姆算法而言,适合于求边稀疏的网的最小生成树。