实验三树和图应用一、实验目的光纤管道铺设施工问题问题描述设计校园内有N个教学楼及办公楼，要铺设校园光纤网，如何设计施工方案使得工程总的造价为最省。

二、实验要求设计校园光纤网铺设的最小生成树模拟程序。

1)采用邻接表或邻接矩阵存储结构。

2)分别采用普利姆算法和克鲁斯卡尔算法实现。

输入形式对应的教学楼、办公楼数目n，各边权值即每栋楼之间的距离输出形式最小生成树，即总路程最小的路程序功能设计校园光纤网铺设的最小生成树模拟程序三、设计概要流程图抽象数据类型的定义class prims{private:int n; //节点的个数int graph_edge[99][4]; //图的边int g; //图中边的个数int tree_edge[99][4]; //树的边int t; //树的边的个数int s; //源节点int T1[50],t1; // 第一部分int T2[50],t2; //第二部分public:void input();int findset(int);void algorithm();void output();};各程序模块之间的调用关系四、详细设计定义prims类private中进行对图的创建public:void input();int findset(int);void algorithm();void output();开始界面实现prims类中图的初始化分别输入图中的顶点个数、图的边及其权值算法构造t=0;//初始化边的个数为0t1=1;T1[1]=1; //资源节点t2=n-1;int i;for(i=1;i<=n-1;i++)T2[i]=i+1;cout<<"\n\n*****运算开始*****\n\n\n";while(g!=0 && t!=n-1){int min=99;int p;int u,v,w;for(i=1;i<=g;i++){if(findset(graph_edge[i][1])!=findset(graph_edge[i][2])) //如果u和v在不同的部分{if(min>graph_edge[i][3]){min=graph_edge[i][3];u=graph_edge[i][1];v=graph_edge[i][2];w=graph_edge[i][3];p=i;}}}for(int l=p;l<g;l++){graph_edge[l][1]=graph_edge[l+1][1];graph_edge[l][2]=graph_edge[l+1][2];graph_edge[l][3]=graph_edge[l+1][3];}t++;tree_edge[t][1]=u;tree_edge[t][2]=v;tree_edge[t][3]=w;}运算结果的输出cout<<"挑选出的边及其对应的权值::\n";for(int i=1;i<=t;i++)cout<<"<"<<tree_edge[i][1]<<","<<tree_edge[i][2]<<"> ::"<<tree_edge[i][3]<<endl;五、调试分析所遇问题的解决方法及分析开始时，我并不知道应该要怎样建立图和最小生成树之间的关系，而这个问题如若无法解决，那么普利姆算法就无从提起了。

因此，在查阅了资料后，我将图和最小生成树放在一个类中，这样，通过函数操作就会容易很多。

算法的时空分析及改进设想O(n^2)经验和体会通过此次程序的编译过程，我更深刻的了解到有一个清晰的思路对于编程的重要性。

在编程之前需要经过充分的构思，就像写作先列提纲一样，只有拥有一个清晰的思路，编程序时才能一气呵成，否则只能是编到哪里是哪里，很容易卡壳，耽误时间是一方面，而且会使编出的程序没有连贯性。

六、使用说明1、输入图的边数2、输入各边的权值3、程序打印出图中顶点可建立的关系网4、程序开始运算5、程序打印出最小生成树及其各边的权值七、测试结果（截屏）八、附录#include<iostream>using namespace std;class prims{private:int n; //节点的个数int graph_edge[99][4]; //图的边int g; //图中边的个数int tree_edge[99][4]; //树的边int t; //树的边的个数int s; //源节点//把图分成两个部分int T1[50],t1; // 第一部分int T2[50],t2; //第二部分public:void input();int findset(int);void algorithm();void output();};void prims::input(){cout<<"***********************************\n"<<endl;cout<<"************欢迎使用****************"<<endl;cout<<"********普里姆算法运算*********\n";cout<<"****************************************\n";cout<<"输入顶点的个数::";cin>>n;g=0;//图中边的个数初始值为0cout<<"输入边的权值::\n";for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){cout<<"<"<<i<<" , "<<j<<"> ::";int w;cin>>w;if(w!=0){g++;graph_edge[g][1]=i;//定义图的顶点igraph_edge[g][2]=j;//定义图的顶点jgraph_edge[g][3]=w;//定义边的权值w}}}//输出图的边cout<<"\n\n图中顶点可以建立的关系网::\n";for(int i=1;i<=g;i++)cout<<"<"<<graph_edge[i][1]<<" , "<<graph_edge[i][2]<<">"<<endl; }int prims::findset(int x)for(int i=1;i<=t1;i++)if(x==T1[i])return 1;for(int i=1;i<t2;i++)if(x==T2[i])return 2;return -1;}void prims::algorithm()//构造算法{t=0;//初始化边的个数为0t1=1;T1[1]=1; //资源节点t2=n-1;int i;for(i=1;i<=n-1;i++)T2[i]=i+1;cout<<"\n\n*****运算开始*****\n\n\n";while(g!=0 && t!=n-1){// 找出最短路径int min=99;int p;int u,v,w;for(i=1;i<=g;i++){if(findset(graph_edge[i][1])!=findset(graph_edge[i][2]))//如果u和v在不同的部分{if(min>graph_edge[i][3]){min=graph_edge[i][3];u=graph_edge[i][1];v=graph_edge[i][2];w=graph_edge[i][3];p=i;}}//删除图的边for(int l=p;l<g;l++){graph_edge[l][1]=graph_edge[l+1][1];graph_edge[l][2]=graph_edge[l+1][2];graph_edge[l][3]=graph_edge[l+1][3];}//增加树的边t++;tree_edge[t][1]=u;tree_edge[t][2]=v;tree_edge[t][3]=w;}}void prims::output(){cout<<"挑选出的边及其对应的权值::\n";for(int i=1;i<=t;i++)cout<<"<"<<tree_edge[i][1]<<","<<tree_edge[i][2]<<"> ::"<<tree_edge[i][3]<<endl; }int main(){prims obj;obj.input();obj.algorithm();obj.output();return 0;}。