最近在研究最小生成树的问题,略有心得,整理如下:
        对于一个带权(假定每条边上的权值均为大于0的实数)连通无向图G中的不同生成,其每棵树的所有边上的权值之和也可能不同;图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。
按照生成树的定义,n个顶点的连通图的生成树有n个顶点、n-1条边。因此,构成最小生成树的准则有三条:
      (1)必须只使用该图中的边来构造最小生成树;
      (2)必须使用且仅使用n-1条边来连接图中的n个顶点;
      (3)不能使用产生回路的边。
        求图的最小生成树有很多实际的应用,例如,城市之间交通工程造价最优,设计通信网络最经济的方案等问题,都需要最小生成树的模型。用贪心算法设计策略可以设计出构造最小生成树的有效算法。下面举实例介绍应用贪心算法策略构造最小生成树的Prim算法和Kruskal算法。

 

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

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

一、普里姆算法(Prim)
        普里姆算法是一种构造性算法。假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则由G构造最小生成树T的步骤如下:
      (1)初始化U={V}。以V到其他顶点的所有边为候选变;
      (2)重复以下步骤n-1次,使得其他n-1个顶点被加入到U中:
                a>从候选边中挑选权值最小的边输出,设该边在V-U中的顶点是Vk,将Vk加入U中,删除和Vk关联的边;
                b>考察当前V-U中的所有顶点Vj,修改候选边:若(Vk,Vj)的权值小于原来和Vj关联的候选边,则用(Vk,Vj)取代后者作为候选边。

下面附上Prime算法的代码:
 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define maxsize 600
#define max 25767

int map[maxsize][maxsize];
                   //lowcost[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入生成树 
int lowcost[maxsize];
int n;
int sum;

int Prim(){
                //v用来标记结点, 当v[i]=1时表示起点i加入生成树 
      int v[maxsize];
      int i,j,min,mini;
                     //v全赋0,没有一个结点被查找
      memset(v,0,sizeof(v));
      sum = 0; 
             //最短距离初始化为其他节点到1号节点的距离
      for(i=1; i<=n; i++)
             lowcost[i] = map[1][i];
               // 标记1号节点加入生成树
      v[1]=1;
                 // n个节点至少需要n-1条边构成最小生成树 
      for(i=2;i<=n;i++){
             min=max;
                  // 找满足条件的最小权值边的节点mini
             for(j=1;j<=n;j++)
                  //边权值较小且不在生成树中
                   if(!v[j] && lowcost[j]<min){
                         min = lowcost[j];
                          mini = j;
                   }
                   // 累加权值
            sum += min;
                     // 标记节点mini加入生成树 
            v[mini] = 1;
                      // 更新当前节点mini到其他节点的权值 
            for(j=1; j<=n; j++){
                         //发现更小的权值 
                  if(!v[j] && map[mini][j] < lowcost[j]){
                                   //更新权值
                          lowcost[j] = map[mini][j];
                  }
             }
      }
             //返回最小权值和
       return sum;
}

int main(){
      int i,j,m;
      int x,y,w;
               //读取节点和边的数目
      while(scanf("%d",&n) && n){
              scanf("%d",&m);
               //赋初权值为无穷大
              for(i=1;i<=n;i++)
                     for(j=1;j<=n;j++)
                             map[i][j]=max;
                      //输入各结点权值
              for(i=1;i<=m;i++){
                     scanf("%d%d%d",&x,&y,&w);
                     if(w<map[x][y]){
                             map[x][y]=w; 
                             map[y][x]=w;
                     }
             }
              printf("%d\n",Prim());
      }
      return 0;
}

二、克鲁斯卡尔算法(Kruskal)
        克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,TE)是G的最小生成树,则构造最小生成树的步骤如下:
      (1)置U的初值等于V(即包含有G中的全部顶点),TE的初值为空集(即图T中的每一个顶点都构成一个分量)。
      (2)将图G中的边按权值从小到大的顺序依次选取:若选取的边未使生成树T形成回路,则加入TE;否则舍弃,直到TE中包含(n-1)条边为止。

下面附上Kruskal算法

#include<stdio.h>
#include<stdlib.h>

#define maxsize 300
#define max 20000

int map[maxsize][maxsize];
int father[maxsize];
int rank[maxsize];
int sum;
int n;
//开辟结构体,存储关系
struct node{
      int x;
      int y;
      int w;
}edge[maxsize*maxsize/2];
//赋初值
void make_set(){
      int i;
      for(i=1;i<=n;i++){
            father[i]=i;
            rank[i]=1;
      }
}
//查找结点的父结点
int find_set(int x){
      if(x != father[x])
            father[x] = find_set(father[x]);
      return father[x];
}
//查找两结点是否属于同一个集合,若不属于添入生成树
void Union(int a,int b,int w){
      int x,y;
      x=find_set(a);
      y=find_set(b);
      if(x == y)           //同一个集合,舍去
            return ;
      if(rank[x] >= rank[y]){
            father[y]=father[x];
            rank[x] += rank[y];
      }
      else{
            father[x] = father[y];
            rank[y] += rank[x];
      }
      sum += w; //累加权值
}
//对结构体按权值排序
void Sortxy(int k){
      int i,j;
      int cmp;
      for(i=1;i<k;i++)
            for(j=1;j<k;j++)
                  if(edge[i].w < edge[j].w){
                       cmp = edge[i].x;
                       edge[i].x = edge[j].x;
                       edge[j].x = cmp;
                       cmp = edge[i].y;
                       edge[i].y = edge[j].y;
                       edge[j].y = cmp;
                       cmp = edge[i].w;
                       edge[i].w = edge[j].w;
                       edge[j].w = cmp;
              }
}
//Kruskal查找
void Kruskal(int k){
       int i;
       Sortxy(k);
       for(i=1;i<k;i++)
              Union(edge[i].x, edge[i].y, edge[i].w);
}

int main(){
       int i,j,k;
       int x,y,w;
       int m;
       while(scanf("%d",&n) && n){
                scanf("%d",&m);
                sum=0;
                make_set();
                           //把map数组里赋初值无穷大
                for(i=1;i<=n;i++)
                      for(j=1;j<=n;j++)
                             map[i][j] = max;
                for(i=1;i<=m;i++){
                      scanf("%d%d%d",&x,&y,&w);
                         //保留两个结点间小的权值
                       if(map[x][y] > w){
                                map[x][y]=w;
                                map[y][x]=w;
                        }
               }
               k=1;
               for(i=1;i<=n;i++){
                      for(j=1;j<=n;j++){
                              //取左上三角阵上的值
                            if(i<j && map[i][j]<max){
                                   edge[k].x=i;
                                   edge[k].y=j;
                                   edge[k].w=map[i][j];
                                   k++;
                            }
                     }
              }
              Kruskal(k);
              printf("%d\n",sum);
       }
       return 0;
}

         注:POJ上还有1251、1258、1639、1789、1861、2253、2359和ZOJ1203、1406、1586也是最小生成树的题,无论题意怎么变,最精髓的算法不会变,只要这两种方法掌握了,关于最小生成树的题都是可以做出来的。
                                                                                                                                                                                   Day day up!

 

About 硌丹

今天你AC了吗?

One Thought on “最小生成树小结

  1. 正学习这方面内容,谢谢了,有用

发表评论

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

Post Navigation