最小生成树之普里姆（prim）法求最小生成树

prim

基本思想

 设G是具有n(u1,u2,u3.....un)个顶点,m个边的连通无向图，T是G的最小生成树， T的初始状态为U={u1}，value={}，
 记一个数组d[i],,表示当前最小生成树中的顶点到i的最小值;
 d的初始状态为d[i]=d[1][i];

#include<bits/stdc++.h>
using namespace std;
int a[10010][10010],d[100010];
int main()
{
    int n,m,i,u,v,w,j,mmin,temp,s=0;
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++) a[i][j]=1000000000;
    }

    for(i=1; i<=m; i++)
    {
        cin>>u>>v>>w;
        a[v][u]=w;
        a[u][v]=w;
    }

    for(i=2; i<=n; i++) d[i]=a[1][i]; // 初始化d数组

    for(i=2; i<=n; i++) // 遍历n-1次(向T中加入n-1个点)
    {
        mmin=1000000000;
        temp=0;
        for(j=2; j<=n; j++)  //找出当前 没在T中的点到T的最小距离 
        {
            if(d[j]<mmin&&d[j]!=0)
            {
                mmin=d[j];
                temp=j;
            }
        }
        s+=mmin;
        d[temp]=0;  // 表示点temp在T中
        for(j=2; j<=n; j++)
        {
            if(a[temp][j]<d[j])  // 改变d数组
            {
                d[j]=a[temp][j];
            }
        }
    }
    printf("%d",s);
    return 0;
}