# 最小生成树的两种算法

By | 2011/08/13

MST（Minimum Spanning Tree）已经培训了整整三天啦，真是接近崩溃的边缘呀，不过还是熬过来啦。为此，是该写点东西的时候啦，关于MST，无非就两种方法，Prim&&Kruskal，关于这两个算法，在下面我们来好好的讨论一下：

PRIM

接下来先讨论Prim算法，此算法需要建立辅助数组，来存放U和V-U之间的边，数组按如图所示的方式变化：棕色虚线表示的边是数组中的边，实线表示的边是要加入到最小生成树中的边，该边即将在数组中被删除。

Swordfish

 Time Limit: 1000MS
 Memory Limit: 32768K 64bit IO Format: %lld & %llu

[Submit]   [Go Back]   [Status]

Description

There exists a world within our world
A world beneath what we call cyberspace.
A world protected by firewalls,
security systems.
In this world we hide
our deepest secrets,
our most incriminating information,
and of course, a shole lot of money.
This is the world of Swordfish.

We all remember that in the movie Swordfish, Gabriel broke into the World Bank Investors Group in West Los Angeles, to rob \$9.5 billion. And he needed Stanley, the best hacker in the world, to help him break into the password protecting the bank system. Stanley's lovely daughter Holly was seized by Gabriel, so he had to work for him. But at the last moment, Stanley made some little trick in his hacker mission: he injected a trojan horse in the bank system, so the money would jump from one account to another account every 60 seconds, and would continue jumping in the next 10 years. Only Stanley knew when and where to get the money. If Gabriel killed Stanley, he would never get a single dollar. Stanley wanted Gabriel to release all these hostages and he would help him to find the money back.
You who has watched the movie know that Gabriel at last got the money by threatening to hang Ginger to death. Why not Gabriel go get the money himself? Because these money keep jumping, and these accounts are scattered in different cities. In order to gather up these money Gabriel would need to build money transfering tunnels to connect all these cities. Surely it will be really expensive to construct such a transfering tunnel, so Gabriel wants to find out the minimal total length of the tunnel required to connect all these cites. Now he asks you to write a computer program to find out the minimal length. Since Gabriel will get caught at the end of it anyway, so you can go ahead and write the program without feeling guilty about helping a criminal.

Input:
The input contains several test cases. Each test case begins with a line contains only one integer N (0 <= N <=100), which indicates the number of cities you have to connect. The next N lines each contains two real numbers X and Y(-10000 <= X,Y <= 10000), which are the citie's Cartesian coordinates (to make the problem simple, we can assume that we live in a flat world). The input is terminated by a case with N=0 and you must not print any output for this case.

Output:
You need to help Gabriel calculate the minimal length of tunnel needed to connect all these cites. You can saftly assume that such a tunnel can be built directly from one city to another. For each of the input cases, the output shall consist of two lines: the first line contains "Case #n:", where n is the case number (starting from 1); and the next line contains "The minimal distance is: d", where d is the minimal distance, rounded to 2 decimal places. Output a blank line between two test cases.

Sample Input:

```5
0 0
0 1
1 1
1 0
0.5 0.5
0
```

Sample Output:

```Case #1:
The minimal distance is: 2.83
```

#include<stdio.h>
#include<math.h>
#include<string.h>                                     /*要用到memset,数组的初始化*/

double dis(double x1,double y1,double x2,double y2)    /*用到sqrt,要求是double型*/
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
int i,j,n,z,cas=0,yes;
double x[101],y[101],a[101][101],v[101],sum,min;
while(scanf("%d",&n)&&n)
{
cas++;                                      /*为Cas计数*/
memset(a,0,sizeof(a));              /*初始化数组a为0，特别是多维数组的时候比较好用,但是记住括号里的初始值只能为0*/
for(i=1;i<=n;i++)                     /*读入n组点坐标*/
scanf("%lf%lf",&x[i],&y[i]);
for(i=1;i<=n;i++)                              /*依次计算各点之间的权值，这里相当于形成了一个邻接矩阵，其实求出来的邻接矩阵是对称的（自己到自己距离为0）*/
{
for(j=1;j<=n;j++)
a[i][j]=dis(x[i],y[i],x[j],y[j]);   /*计算权值只要每次调用一下函数就可以了，很方便哦*/
}
for(i=1;i<=n;i++)                /*首先把第一个点到其他点的距离存放于V数组，对其进行初始化*/
v[i]=a[1][i];    /*prim算法中首先把第一个点单独划分为一个集合（设为M），其它点在集合（设为N）*/
sum=0;
for(i=1;;i++)
{
yes=0;
min=1000000;                 /*先初始化为无穷大*/
for(j=1;j<=n;j++)
{
if(v[j]&&v[j]<min)    /*找出点集合M到N最短距离放到min里面这里v[j]!=0表示除去自己到自己的距离（0）*/
{
min=v[j];
z=j;
yes=1;
}
}
if(yes==0)break;            /*当v数组全为0时（可以理解为当N集合的点全部归入M集合的时候），退出整个循环*/
sum+=min;                     /*将最短路径累加*/
v[z]=0;                           /*以此作为标记把点z从集合N归入到集合M中去*/
for(j=1;j<=n;j++)
{
if(a[z][j]<v[j]&&a[z][j])     /*每当新归入一个新的点后，要改变M集合点到N集合各点的权值，选出较小的。*/
v[j]=a[z][j];
}
}
if(cas!=1)printf("\n");            /*此方法值得借鉴哦*/
printf("Case #%d:\n",cas);
printf("The minimal distance is: %.2lf\n",sum);
}
return 0;
}

KRUSKAL

（图 1）                                                                          （图 2）
（图 3）                                                                   （图 4）

（图 5）

………….

Networking

 Time Limit: 1000MS Memory Limit: 10000K 64bit IO Format: %I64d & %I64u

[Submit]   [Go Back]   [Status]

Description

You are assigned to design network connections between certain points in a wide area. You are given a set of points in the area, and a set of possible routes for the cables that may connect pairs of points. For each possible route between two points, you are given the length of the cable that is needed to connect the points over that route. Note that there may exist many possible routes between two given points. It is assumed that the given possible routes connect (directly or indirectly) each two points in the area.
Your task is to design the network for the area, so that there is a connection (direct or indirect) between every two points (i.e., all the points are interconnected, but not necessarily by a direct cable), and that the total length of the used cable is minimal.

Input

The input file consists of a number of data sets. Each data set defines one required network. The first line of the set contains two integers: the first defines the number P of the given points, and the second the number R of given routes between the points. The following R lines define the given routes between the points, each giving three integer numbers: the first two numbers identify the points, and the third gives the length of the route. The numbers are separated with white spaces. A data set giving only one number P=0 denotes the end of the input. The data sets are separated with an empty line.
The maximal number of points is 50. The maximal length of a given route is 100. The number of possible routes is unlimited. The nodes are identified with integers between 1 and P (inclusive). The routes between two points i and j may be given as i j or as j i.

Output

For each data set, print one number on a separate line that gives the total length of the cable used for the entire designed network.

Sample Input

```1 0

2 3
1 2 37
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

0```

Sample Output

```0
17
16
26```

#include<stdio.h>
#define Size1 100     /*顶点数*/
#define Size2 10000   /*边数*/
struct type           /*定义结构体数组，用来存储顶点，和各顶点的权值*/
{
int u,v;
int key;          /*用来存权值*/

}net[Size2],T;        /*T，冒泡排序用到*/

int Ind;
int find(int v)       /*查找祖先的函数,最经典的一种写法,还有其他的,不过这是相当经典的*/
{
return v;
}

//int rank[Size1];
/*

void  uni(int x,int y)
{
if(rank[x]>=rank[y])     //将rank值小的往rank值大的里面合并
{
rank[x]++;
}
else
{
rank[y]++;
}
}
*/

int kruskal(int N,int M)
{
int z=0;
int i,j,pos1,pos2,k;
for(i=0;i<M-1;i++)   /*从小到大排序,冒泡排序,这题要求不高，一般排序即可，也可以用快排等高效率排序方法*/
for(j=i+1;j<M;j++)
if(net[i].key>net[j].key)
{
T=net[i];
net[i]=net[j];
net[j]=T;
}
for(i=0;i<N;i++)            /*初始化祖先为自己*/
{
// rank[i]=0;
}
i=0;
for(k=1;k<N;)
{
pos1=find(net[i].u);  /*分别查找各自的祖先,不一样就要和并祖先,否则继续找下一条最短路径*/
pos2=find(net[i].v);
if(pos1!=pos2)        /*如果祖先不相同，证明不是一个集合的，可以合并在一起*/
{
z+=net[i].key;        /*统计最短路径之和*/
k++;                /*相当于找到一个,就少一个结点,N个结点找完后程序结束*/
/* uni(pos1,pos2);    也可以这样，只是合并的要经典一点，就是合并时层数要少一点，附加被调函数*/
}
i++;
}
return z;                   /*返回最小生成树权之和*/
}

int main()
{
int n,m,i;
int a,b,c;
while(scanf("%d",&n)&&n)
{
scanf("%d",&m);
Ind=0;
for(i=0;i<m;i++)  /*读取已知数据,也可以不用这样，直接输入结构体即可*/
{
scanf("%d%d%d",&a,&b,&c);
net[Ind].u=a;
net[Ind].v=b;
net[Ind++].key=c;
}
printf("%d\n",kruskal(n,m));  /*直接调用函数,输出结果*/
}
return 0;
}

（1 ）Prim and Kruskal 算法的空间比较：数据给的情况不同空间有所不同当点少边多的时候如1000个点500000条边这样BT的数据用prim做就要开一个1000*1000的二维数组，而用kruskal做只须开一个500000的数组，恐怖吧500000跟1000*1000比较相差一半。当点多边少的时候如1000000个点2000条边像这中BT数据就是为卡内存而存在的，如果用prim做你想开一个1000000*1000000的二维数组没门内存绝对爆挂你。而像这种情况用kruskal只须开一个2000的数组绝对赚到了。

（2）Prim and Kruskal and   Kruskal+快排 算法的时间比较prim 在跟普通的kruskal比较空间是肯定没有普通的kruskal来的好。但时间方面的话prim就比普通kruskal来的更恐怖一些，用prim时间比普通的kruskal快20倍。在这时我就想如那数据变态的很用普通的kruskal绝对超时，用prim搞爆内存那就掺了。这时惟有改进prim算法从中砍内存，怎么砍，换一个超大内存的电脑，你去那找啊。拿刀砍，开玩笑。方法一放弃。方法二在改进kruskal算法从中砍时间，经过反复的折腾最后，想到了普通的kruskal在选择感染了的边的时候还要进行搜索其所有被感染了的边中值最小的边，每一次都要在此处进行重复的搜索觉的很费时，索性事先派好序。所以改进后变为kruskal+快排，结果时间跟prim相差无几，而且有省内存。这就是王道啊。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

## One thought on “最小生成树的两种算法”

1. wangsi

运行怎么出错啦啊？
:\软件\c语言\myprojects\最小生成树cruskal\cr.c(16) : error C2065: ‘rank’ : undeclared identifier
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(16) : error C2109: subscript requires array or pointer type
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(16) : error C2109: subscript requires array or pointer type
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(17) : error C2109: subscript requires array or pointer type
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(17) : error C2105: ‘++’ needs l-value
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(18) : error C2065: ‘link’ : undeclared identifier
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(18) : error C2109: subscript requires array or pointer type
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(18) : error C2106: ‘=’ : left operand must be l-value
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(19) : error C2109: subscript requires array or pointer type
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(19) : error C2105: ‘++’ needs l-value
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(20) : error C2109: subscript requires array or pointer type
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(20) : error C2106: ‘=’ : left operand must be l-value
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(22) : warning C4138: ‘*/’ found outside of comment
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(22) : error C2059: syntax error : ‘/’
d:\软件\c语言\myprojects\最小生成树cruskal\cr.c(62) : warning C4013: ‘kruskal’ undefined; assuming extern returning int
执行 cl.exe 时出错.

cr.exe – 1 error(s), 0 warning(s)