yuanyuelang

常用链接

统计

最新评论

最小生成树之Prim算法

最小生成树是图论的一个重要部分，解决这个问题的算法主要有Kruskal算法和Prim算法。

最小生成树:顾名思义是一棵树，该树是图中权值和最小的。

这篇文章介绍Prim算法，Kruskal算法请参阅最小生成树之Kruskal算法。

Prim算法的主要思路：
1.图G={V,E},V表示节点集，E表示边集，初始时将V0从V中拿出，放入空集合U中，U={V0}，T(E)空
2.选择和集合U有连接的且最近的点Vx（在V中），放入U，U={V0,Vx},并将边加入到T(E)中。
3.重复第二步，直到U=V
很明显需要n-1步，n为图的节点数。

现在我们就是要如何把它变成代码的问题了。
1.存储问题，我们需要一个二元数组graph下标存放节点，数组值存放权值。比如(1,2)有边，权值为3，则graph[1][2]=3,同时graph[2][1]=3，没有边的点用INF（无穷大）表示咯。
2.如何判断和最近的点，由于每一次进来都会改变情况，所以每次都要更新，我们用一个一元数组opt[n]来表示，数组下标表示节点号，值表示该节点到U的最短距离。记住，加入到U集合的点是不用再管它的了，所以，我们还要设置一个数组flag[n]，来设置标志位，看是否已经加入到U集合了。
3.这样的话大功也就告成了，一般就会写了吧。如果要保存各个边的话，还要添加一个数组line[n]来表示节点到U的最短距离到底是连接U中哪一个节点的。

看看代码，分析分析吧。。记住很重要的，自己举个例子看看。最后一定要熟练掌握其原理，并且快速的写出代码。
#define MAXN 100
#define INF 0xfffffff

int result_s[MAXN],result_e[MAXN];//保存边

void prim(int graph[MAXN][MAXN],int opt[],int n)
{
  int i,j,min,vertex，line[n];
  bool flag[n];
 
  for(i=0;i<n;i++){ //初始化
    opt[i]=graph[0][i];
    line[i]=0;
    flag[i]=false;
   }
  flag[0]=true;
  for(i=1;i<n;i++){
    min=INF;
    for(j=1;j<n;j++){
      if(!flag[j]&&opt[j]<min){//选择最优点
        min=opt[j];
        vertex=j;
      }
    }
    flag[vertex]=true; //加入到U集合
    result_s[i]=line[vertex];//保存
    result_e[i]=vertex;
    for(j=1;j<n;j++){//更新
      if(!flag[j]&&graph[vertex][j]<opt[j])
         opt[j]=graph[vertex][j];
         line[j]=vertex;
    }
  }
}
因为代码是自己当场写出来，写出来和原来正确代码相比较了，如果读者发现有错，还望指正。
我想我们就是要锻炼这种写代码的能力，不能太依靠模板，不然忘得快。
注意：最后结果都知道了，opt[]保存的是最小生成树的选入的各个边的权值，result_s[]和result_e保存了到底是哪些点组成的最小生成树。

posted on 2009-09-14 18:47 原语饿狼 阅读(503) 评论(0)  编辑 收藏 引用 所属分类: 图论


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理