Prim算法---最小生成树

最小生成树的Prim算法也是贪心算法的一大经典应用。Prim算法的特点是时刻维护一棵树，算法不断加边，加的过程始终是一棵树。

Prim算法过程：

一条边一条边地加，维护一棵树。

初始 E ＝｛｝空集合， V = ｛任意节点｝

循环（n – 1）次，每次选择一条边（v1,v2），满足：v1属于V , v2不属于V。且（v1,v2）权值最小。

E = E + （v1,v2）
V = V + v2

最终E中的边是一棵最小生成树， V包含了全部节点。

以下图为例介绍Prim算法的执行过程。

Prim算法的过程从A开始 V = {A}, E = {}
Prim算法---最小生成树
选中边AF , V = {A, F}, E = {(A,F)}

选中边FB, V = {A, F, B}, E = {(A,F), (F,B)}

选中边BD, V = {A, B, F, D}, E = {(A,F), (F,B), (B,D)}

选中边DE, V = {A, B, F, D, E}, E = {(A,F), (F,B), (B,D), (D,E)}

选中边BC, V = {A, B, F, D, E, c}, E = {(A,F), (F,B), (B,D), (D,E), (B,C)}, 算法结束。

最后，我们来提供输入输出数据，由你来写一段程序，实现这个算法，只有写出了正确的程序，才能继续后面的课程。

输入

第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000)

第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)

输出

输出最小生成树的所有边的权值之和。

输入示例

输出示例

请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范围，最终结果会造成Int32溢出，这样会输出错误的答案。

不同语言如何处理输入输出，请查看下面的语言说明。

简单的最小生成树，自己写的代码一直过不了

AC代码（prim算法）

#include<iostream>

#include<cstdio>

#include<map>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<vector>

#include<stack>

#include<cstdlib>

#include<cctype>

#include<cstring>

#include<cmath>

using namespace std;

const int inf=0x3f3f3f3f;

int G[1001][1001];//邻接矩阵

int vis[1001],lowc[1001];

int prim(int G[][1001],int n){

    int i,j,p,minc,res=0;

    memset(vis,0,sizeof(vis));

    vis[1]=1;//从1开始访问

    for(i=2;i<=n;i++) lowc[i]=G[1][i];

    for(i=2;i<=n;i++){

        minc=inf; p=-1;

        for(j=1;j<=n;j++){

            if(vis[j]==0&&lowc[j]<minc){

                minc=lowc[j]; p=j;

            }

        }

        //cout<<minc<<endl;

        if(inf==minc) return -1;//原图不联通

        res+=minc; vis[p]=1;

        for(j=1;j<=n;j++){//更新lowc[]

            if(vis[j]==0&&lowc[j]>G[p][j]){

                lowc[j]=G[p][j];

            }

        }

    }

    return res;

}  

int main()

{

    int n,m;

    while(cin>>n>>m){

        int x,y,w;

        memset(G,inf,sizeof(G));//首先记录所有边的权为inf

        for(int i=1;i<=m;i++){

            cin>>x>>y>>w;

            G[x][y]=G[y][x]=w;

            //cout<<G[x][y]<<endl;

        }

        //int res=prim(n);

        cout<<prim(G,n)<<endl;

    }

    return 0;

}

自己写的代码不知道错哪了（kruskal算法）

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

struct tr

{

	int s,e,w;

}p[50000+10];

bool cmp(tr x, tr y)

{

	return x.w < y.w;

}

int n,m;

int f[1000+10];

int i,j;

long long ans;

int find(int x)  //找父亲

{

	int r = x;

	while(f[r] != r)

	r = f[r];

	return r;

	int i = x, j;

	while(i != r)

	{

		j = f[i];

		f[i] = r;

		r = j;

	}

} 

void join(int x, int y)

{

	int fx = find(x);

	int fy = find(y);

	if(fx != fy)

		f[fx] = fy;

} 

int kruskal()

{

	sort(p, p+m, cmp);

	for(i=0; i<n; i++)

	{

		f[i] == i;//初始化 父亲节点

	}

	for(i=0; i<n; i++)

	{

		if(find(p[i].s) != find(p[i].e))

		{

			join(p[i].e, p[i].s);

			ans += p[i].w;

		}

	}

	return ans;

}

int main()

{

	ans=0;

	scanf("%d %d",&n,&m);

	for(i=0; i<m; i++)

	{

		scanf("%d %d %d",&p[i].s, &p[i].e, &p[i].w);

	}

	kruskal();

	printf("%lld\n",ans);

	return 0;

 }

秒客网

Prim算法---最小生成树

相关文章