Question

图的最小生成树

如图所示
采用图形化形式显示原图（其中一个测试用例采用上图），并采用动画效果一步一步的显示Kruskal算法求得的最小生成树
不论C++，C，JAVA都可，请各位高手帮帮忙
可将答案发到我的邮箱youjits@126.com,谢谢了

Answer 1

Kruskal算法：每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
程序如下：
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct
{
int x, y;
int w;
}
edge;
edge e[MAX];
int rank[MAX];
int father[MAX];
int sum;
int cmp(const void *a, const void *b)
{ if ((*(edge *)a).w == (*(edge *)b).w)
{
return (*(edge *)a).x - (*(edge *)b).x;
}
return (*(edge *)a).w - (*(edge *)b).w;
}
void Make_Set(int x)
{
father[x] = x; rank[x] = 0;
}
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]);
}
return father[x];
}
void Union(int x, int y, int w)
{
if (x == y) return;
if (rank[x] > rank[y]) //将秩较小的树连接到秩较大的树后
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
sum += w;
}
int main() // 主函数
{ int i, n;
int x, y;
char chx, chy;
printf("图的边数为：\n");
scanf("%d", &n);
getchar();
printf("每条边和权值分别为：\n");
for (i = 0; i < n; i++)
{
scanf("%c-%c %d", &chx, &chy, &e[i].w); //1-2 6 这是你需要输入的
getchar();
e[i].x = chx - 'A';
e[i].y = chy - 'A';
Make_Set(i);
}
qsort(e, n, sizeof(edge), cmp);
sum = 0;
for (i = 0; i < n; i++)
{
x = Find_Set(e[i].x);
y = Find_Set(e[i].y);
if (x != y)
{
printf("边%c-%c 权值: %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w);
Union(x, y, e[i].w);
}
}
printf("最小生成树权值之和:%d\n", sum);
return 0;
}

在VC6.0上运行测试成功，希望可以帮到你，祝你好运！

Answer 2

你是UESTC的。。？我写好了。。但如果你是UESTC的就不行了。。因为我也是。

Answer 3

50分？有难度 这个几分钟搞不定