2 zq741552720 ZQ741552720 于 2015.06.24 18:07 提问

kruscal 求最小树 问题求大神

图片说明
对图中的图 求出她所有的最小二叉树图中有2棵最小树 要求用kruscal 算法

我想到的是 要在排序函数中产生2 组排序 1 2 3 4 4 * 5
1 2 3 4* 4 5 我用的是选择排序 但没弄出来 求大神给指导下 谢谢
void kruskal(mgraph g)
{
int i,j;
int k;
int u1,v1,sn1,sn2;
edge e1[MS]; //边权值列表
int vset[MS]; //顶点链接判断列表

k=0;
for(i=0;i<g.d;i++)     //边权值列表初始化  
{
   for(j=0;j<g.d;j++)
   if(g.edges[i][j]!=0&&g.edges[i][j]!=inf)
   {
    e1[k].q=i; e1[k].z=j; e1[k].w=g.edges[i][j];
    k++; 
   }
} 

 //对 edga 进行排序 (从小到大) 
 sort(e1,k);

 for(i=0;i<g.d;i++)     //初始化辅助数组 
    vset[i]=i;

 k=1;      
 j=0;
 while(k<g.d)
 {
    u1=e1[j].q; v1=e1[j].z;
    sn1=vset[u1]; sn2=vset[v1];

    if(sn1!=sn2)
    {
        printf("边(%d,%d)权为:%d \n",sn1,sn2,e1[j].w);
        k++;
        for(i=0;i<g.d;i++)     //归 sn1 和 sn2 与一个数组  
           if(vset[i]==sn2)
              vset[i]=sn1;
    }
    j++;
 } 

}

//选择排序
void sort(edge e1[MS],int b)
{
int i,j;
int k;
edge tomp;

for(i=0;i<b;i++)
{
    k=i;
    for(j=i;j<b;j++)
    {
        if(e1[k].w>e1[j].w)
        k=j;
    }
    tomp=e1[k];
    e1[k]=e1[i];
    e1[i]=tomp;
}

}
求大哥大姐 帮帮忙 看下要怎样改!!!!!

3个回答

ZQ741552720
ZQ741552720   2015.06.24 18:18

图片说明

ZQ741552720
ZQ741552720   2015.06.24 19:13

有人没 哪位给说下啊

u011877621
u011877621   2015.06.25 00:10
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
求最小树的Kruskal算法
该算法就是贪心算法,基本思想就是从图G(有n个顶点)的边集中选取n-1条权值尽量小的边,并且不构成回路。 有一个图G,该图的边集用E表示 Step1:把图的边集按权值的大小进行排列(e1,e2,e3 ........),并且置S=ф,i=0,j=1 (S代表点集) Step2:若|S|=i=n-1,则停止,这时G[S] = T即为所求;否则,转向Step3 Step3:若G[ S U {e
kruskal 生成最小树
kruskal 算法在排序上最费时,生成树过程复杂度是线性的,所以最终复杂度为o(|E|log|V|)。 可以对比一下prim算法 传送门》》题目链接#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int cos
浅谈:狄克斯特拉算法Dijkstra找最小树问题
6.3.1狄克斯特拉算法(Dijkstra  algorithm, 1959)          计算两节点之间或一个节点到所有节点之间的最短路 •对每个节点,用两种标号:T和P,表示从始点到该节点的距离,P是最短距离(权),为永久标号,T是目前路径的距离,是临时标号。 •通过不断改进T值,当其最小时,将其改为P标号。 •开始时,令始点有P=0的P标号
最小生成树与最短路的区别
最小生成树:是要把所要的点都chuan
图-最小树
如果一个图中所有点都是联通的,求最小树可以将图遍历完成,这里的最小是指边最少,跟边长没有关系。 算法利用深度优先遍历,记载每个遍历过的节点,将节点按照遍历顺序记录下来就是所谓的最小树。 关于深度优先遍历请参见深度优先遍历。 不过这里奇怪的是: 假如所有节点之间是双向联通的,只用生成一个数组,装入所有的节点,例如{'a','b','c','d','d'} 然后每两个点之
Codeforces 592D Super M 【求解包含若干个点的最小树 + 树的直径】
D. Super M time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Ari the monster is not an ordinary monster. She
最小生成树--matlab实现
最小生成树--matlab实现 此篇文章为我的一位学长(Hong Yilin)整理,我非原创,只是代为发之,只为学习而用。 关于最小生成树,学过图论的都懂,这里就不做介绍。 下面是一个例题,附有Kruskal算法和Prim算法。 题目:假设某电力公司计划在七个村庄之间假设电线,各村庄之间的距离如下图所示, 试求出使电线总长度最小的架线方案。(要求:从村
最小树
求城 市之 间的 最 小树 已经代码 画图
(poj 2377)Kruskal算法 最大生成树
这道题只是一道模板题,感到唯一的坑点就是n,m容易打错,一定要注意结构体要开到Max(M)+n; 之前便是因为这个地方Runtime Error了两次;顺便注意最后输出的答案 为long long型题目**Description Bessie has been hired to build a cheap internet network among Farmer John’s N (2 <= N
最小树Prime算法
普利姆(Prime)算法(只与顶点相关) 算法描述: 普利姆算法求最小生成树时候,和边数无关,只和定点的数量相关,所以适合求稠密网的最小生成树,时间复杂度为O(n*n)。 在一给定的无向图 G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即 ),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集(即 )且为无循环图,使得