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,
passwords and the most advanced
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

讨论过Prim算法过后,就该说说Kruskal算法,Kruskal就是先取权值最小的边作为第一个要纳入的边,直到使所有的结点形成一个最小生成树即可,具体如下图所示:

                                           
            (图 1)                                                                          (图 2)                                             
             (图 3)                                                                   (图 4)
   
              (图 5)                                                     

第一步:我们有一张图,有若干点和边,如图1所示;
第二步:我们要做的事情就是将所有的边的长度排序,用排序的结果作为我们选择边的依据。这里再次体现了快速排序算法的思想。排序完成后,我们率先选择了边AD。 这样我们的图就变成了图2所示;
第三步:在剩下的变中寻找。我们找到了CE。这里边的权重也是5,选择CE,如图3所示;
………….
第n-1步:完成之后,变成了如图4所示:
第n步:这一步就是关键了。下面选择那条边呢? BC或者EF吗?都不是,尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了(对于BC可以通过CE,EB来连接,类似的EF可以通过EB, BA, AD, DF来接连)。所以我们不需要选择他们。类似的BD也已经连通了(这里上图的连通线用绿色表示了)。所以我们只要在连接EG即可。

理论上就这样,不过实现代码时还需要有到并查集的知识,至于并查集的知识在这里就不一一讲述了,不明白的可以自己参考相关资料。下面让我们来举一个简单的例子:

                                            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 Link[Size1];      /*并查集将会用到*/  
int find(int v)       /*查找祖先的函数,最经典的一种写法,还有其他的,不过这是相当经典的*/
{
      if(v!=Link[v])
           v=find(Link[v]);
      return v;
}

//int rank[Size1];
/*
此时还要用到一个rank[]数组,Kruskal函数里已经初始化;

void  uni(int x,int y)
{
        if(rank[x]>=rank[y])     //将rank值小的往rank值大的里面合并
        {
              rank[x]++;
              link[y]=x;
         }
        else
       {
              rank[y]++;
              link[x]=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++)            /*初始化祖先为自己*/
     {
           Link[i]=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个结点找完后程序结束*/
                 Link[pos1]=pos2; /*祖先的归并*/
                /* 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;
}

对prim算法与kruskal算法比较和总结:

 

(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 on 2013/08/15 at 09:12 said:

    运行怎么出错啦啊?
    :\软件\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)

发表评论

电子邮件地址不会被公开。

Post Navigation