最小生成树——prime算法

最小生成树的prime算法是以点为核心来进行计算.

原理：从一个点开始遍历它到其他所有点的距离，无法直接到达的距离为INF，记录为mindis数组

如:一共有四个点ABCD 五条边

A——B   2；    A——C   1;        A——D   3;        B——C   4;        C——D   2;

选取A为第一个点，那么mindis数组中的值为0,2,1,3；并将A标记为已经访问过的点；

然后从未访问过的点中找最小的值加入生成树，即此时mindis数组的最小值为1(即A——C的距离最短)，为C点，将C加入生成树(即标记C已经访问)，并将sum加上权值1；

现在生成树中有两个点A和C，更新mindis数组，即看C到各个点的值与原来mindis数组中的值哪一个小，此时C——D的权值为2，mindis中到D的权值为3，所以更新mindis，更新后为0,2,1,2；

重复上述步骤直到访问所有点

下面是代码

#include <iostream>
#include<cstring>
using namespace std;
int ma[5005][5005];
int mindis[5005];
bool vis[5005];
const int INF=0x3f3f3f;
int main()
{
    std::ios::sync_with_stdio(false);
    memset(ma,INF,sizeof(ma));
    int n,m;
    cin>>n>>m;
    int i;
    for(i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        ma[a][b]=ma[b][a]=min(c,min(ma[a][b],ma[b][a]));//输入到各个点的最小值
    }
    for(i=1;i<=n;i++)
    {
        mindis[i]=ma[1][i];//初始化最短距离数组，目前为第一个点到各个能到的点的最短距离，INF表示到不了
    }
    vis[1]=true;//第一个点已经走过
    bool liantong=true;
    long long cost=0;
    for(i=1;i<n;i++)//n-1次循环，保证访问每一个点
    {
        int tempdis=INF;
        int k=-1;
        for(int j=1;j<=n;j++)//找目前的最短距离
        {
            if(!vis[j]&&mindis[j]<tempdis)
            {
                tempdis=mindis[j];
                k=j;//记录距离最近的点
            }
        }
        if(k==-1)//k==-1,即当前没有点可以走，代表不连通
        {
            liantong=false;//看是否连通
            break;
        }
        cost+=tempdis;
        vis[k]=true;//将这个点标记已访问
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&mindis[j]>ma[k][j])//因为加了一个点进来所以更新最短距离数组，最短距离数组是目前到各个点的最短值
                mindis[j]=ma[k][j];
        }
    }
    if(!liantong)
        cout<<"不连通"<<endl;
    else
        cout<<cost<<endl;
    return 0;
}