logo资料库

算法设计-无向连通图最小生成树.docx

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.01M 资料格式：docx 举报 版权申诉
第1页 / 共4页
第2页 / 共4页
第3页 / 共4页
第4页 / 共4页
资料共4页，全文预览结束
    1006: 无向连通图最小生成树 时间限制: 1 Sec 内存限制: 8 MB 提交次数: 794 通过次数: 330 提交 题目描述 请输出无向连通图最小生成树权重之和。 输入 第一行是 2 个整数,分别表示顶点个数 n 和边数 m。接下来的 m 行中,每一行第一个整数表示 边的开始顶点，第二个表示边的结束顶点，第三个表示这条边的权重。 ( 测试数据中保证图是连通图； 没有自环； 两个顶点之间只有一条边； 0<权重<100(可以相等)；n<=50; m<=1000； ) 输出 输出无向连通图最小生成树权重之和。 样例输入 6 10 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2
    5 6 6 样例输出 15 源代码 #include using namespace std; int n,e,countweight=0; int*set; int**matrix;//邻接矩阵存储两条边间的权重，111 表示不相连 //按权重从小到大排序的节点相应的信息，其中 edgweight 表示边的权重，startnode 表示 这条边连接的一个节点，endnode 表示连接的另一个节点 int *edgeweight,*startnode,*endnode; void unionset(int x,int y);//连接两个连通分支 int find(int x);//查找节点 x 属于哪一个连通分支 int main(){ int row,col,weight;//邻接矩阵行列号和边的权重 int a=0; cin>>n>>e;//输入节点数和边数 set=new int[n]; edgeweight=new int[e]; startnode=new int[e]; endnode=new int[e]; matrix=new int*[n]; for(int i=0;i>row>>col>>weight; matrix[row-1][col-1]=weight; set[i]=i; } //将边的权重和节点信息放到数组里面 for(int i=0;i
    a++; } } } //按照边的权重进行冒泡排序 for(int i=0;iedgeweight[j+1]){ int tempw=edgeweight[j]; int temps=startnode[j]; int tempe=endnode[j]; edgeweight[j]=edgeweight[j+1]; startnode[j]=startnode[j+1]; endnode[j]=endnode[j+1]; edgeweight[j+1]=tempw; startnode[j+1]=temps; endnode[j+1]=tempe; } } } //从权重最小的边开始，如果这条边连接的两个节点不在同一个分支上就连接这两个节 点到同一个分支，如果已经 在同一个分支上就跳过这个节点， for(int i=0;i
    //data 6 10 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2 5 6 6 输出 15
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料