【算法小总结】Prim算法与Kruskal算法探索

  1. 云栖社区>
  2. 博客>
  3. 正文

【算法小总结】Prim算法与Kruskal算法探索

光仔december 2014-08-02 11:14:00 浏览765 评论0

摘要: 以前以为自己用的生成最小生成树的方法是Prim算法,今天自己拜读了《数据结构与算法分析》之后才知道自己有多愚蠢,原来以前一直用的是KrusKal算法。。。。。。 今天好好说道说道这两个算法: KrusKal算法用于稀疏图,贪心策略,连续的按照最小的权值选择边。

以前以为自己用的生成最小生成树的方法是Prim算法,今天自己拜读了《数据结构与算法分析》之后才知道自己有多愚蠢,原来以前一直用的是KrusKal算法。。。。。。

今天好好说道说道这两个算法:

KrusKal算法用于稀疏图,贪心策略,连续的按照最小的权值选择边。

Prim算法用于稠密图,也是贪心策略,每次取离小生成树最近的点作为生成树的心点,并入生成树内生成新的小生成树,知道所有节点均被纳入生成树后结束。

 

这两种方法均可得到点点之间路径最短的联通图。

 

例如这个例子:

 

Prim算法的过程:

KrusKal算法的过程:

 

 

 

下面我编码来实现Prim算法:

(测试数据均是图一)

#include<stdio.h>
#include<string.h>
#define INF 0x11111110
int map[2010][2010],Tree[2010];
int closeset[2010];//节点依附的点(就是与生成树里那个点链接)
int lowcost[2010];//节点到生成树的最短距离 
int sum=0;
void Prim(int n)
{
     int i,j,k;
     int min;
     Tree[1]=1;//先把 1放在生成树里 
     for(i=1;i<=n;i++)
     {  
         lowcost[i]=map[i][1];//所有节点与生成树的最短距离初始化 
         closeset[i]=1;//i依附于谁 (初始化都依附于1) 
     }
     for(j=1;j<=n-1;j++)//n个节点有n-1条边
     {
         min=INF;
         //找到离生成树最近的点 
         for(i=1;i<=n;i++)
         {
            if(!Tree[i]&&lowcost[i]<min)
            {
               min=lowcost[i];
               k=i;
            } 
         }
         printf("链接%d %d 距离为%d\n",k,closeset[k],min); 
         sum+=min;
         Tree[k]=1; //把 k并入生成树 
         //找到离新加入的点最近的点,更新那个点距生成树的距离 
         for(i=1;i<=n;i++)
         {
            if(!Tree[i]&&map[k][i]<lowcost[i])  
            {
               lowcost[i]=map[k][i];//更新最小值
               closeset[i]=k;//记录新的依附点 
            } 
         } 
     } 
     
}
int main()
{
    int i,j,n,m,x,y,z;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
       memset(Tree,0,sizeof(Tree));//用来记录节点是否在生成树中 
       memset(map,INF,sizeof(map));
       for(i=0;i<m;i++)
       {
          scanf("%d %d %d",&x,&y,&z);
          map[x][y]=z;
          map[y][x]=z;
       }
       printf("生成树的合成顺序:\n"); 
       Prim(n);
       printf("生成树的最短距离:%d\n",sum); 
    }
    return 0;
}

 

输入:

7 12

1 4 1

1 2 2

1 3 4

2 4 3

2 5 10

3 4 2

3 5 6

6 4 8

6 7 1

5 4 7

5 7 6

7 4 4

输出:

生成树的合成顺序:

链接4 1 距离为1

链接2 1 距离为2

链接3 4 距离为2

链接7 4 距离为4

链接6 7 距离为1

链接5 3 距离为6

生成树的最短距离:16

 

 

下面我编码来实现KrusKal算法:

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
   int a,b;
   int len;
}per[5000];
int cmp(node x,node y)
{
    if(x.len!=y.len) return x.len<y.len;
}
int main()
{
    int i,sum,n,m,num;
    int flag[200];
    while(scanf("%d %d",&n,&m),n!=0)
    {
       for(i=0;i<m;i++)
       {
          scanf("%d%d%d",&per[i].a,&per[i].b,&per[i].len);
       }
       sort(per,per+m,cmp);
       for(i=1;i<=n;i++) flag[i]=1;
       flag[per[0].a]=0;
       sum=0;
       for(i=0;i<m;i++)
       {
          num=flag[per[i].a]+flag[per[i].b];
          if(num==1)
          {
             printf("链接%d %d 长度%d\n",per[i].a,per[i].b,per[i].len);
             sum+=per[i].len;
             flag[per[i].a]=flag[per[i].b]=0;
             i=0;
          }
       }
       printf("生成树路径总和%d\n",sum);
    }
    return 0;
}

 

 输入

7 12

1 4 1

1 2 2

1 3 4

2 4 3

2 5 10

3 4 2

3 5 6

6 4 8

6 7 1

5 4 7

5 7 6

7 4 4

输出:

链接6 7 长度1

链接7 4 长度4

链接1 4 长度1

链接3 4 长度2

链接1 2 长度2

链接5 7 长度6

生成树路径总和16

 

 

区别一目了然........

 

【云栖快讯】一站式开发者服务,海量学习资源免费学  详情请点击

网友评论