805
汽车大全
【算法小总结】Prim算法与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
区别一目了然........
最后更新：2017-04-03 05:39:37