prim 算法

prim算法就是从一个点开始，这个点访问过了就标记一下，然后从这个点出发找出跟他连接的最近的一个点，再将那个点放入数组中，

#include <iostream>

using namespace std;

int map[100][100];
int n;
int tree[100]={0};//表示最小生成树的数组
int v[100]={0};//对每个点有个相应的距离（权值）
int visited[100]={0};//判断是否访问
int cont;
int sum=0;//距离和
void prim()
{
    tree[cont]=1;
    visited[cont]=1;
    for(int i=1;i<=n;i++)
    {
        if(map[1][i]==-1)
            continue;
        v[i]=map[1][i];
        //cout<<i<<"&"<<endl;
    }

    cont++;
    //cout<<v[2]<<endl;//对第一个点的操作
    for(int i=2;i<=n;i++)//遍历每个最近的点
    {
        int num;
        int MAX=1000000;
        for(int j=1;j<=n;j++)
        {
            if(visited[j]==1)//首先，那个点要没有访问
                continue;
            if(v[j]<MAX)//找距离最近的点
            {
                MAX=v[j];
                num=j;
            }
        }
        sum+=v[num];
        //cout<<num<<"@"<<endl;
        visited[num]=1;//这个点访问了
        tree[cont]=num;//最小生成树数组更新
        cont++;
        for(int j=1;j<=n;j++)//更新所有与目前这个树的距离
        {
            if(visited[j]==1)
                continue;
            if(map[num][j]<v[j]&&map[num][j]!=-1)
            {
                v[j]=map[num][j];
                //cout<<"!"<<j<<endl;
            }

        }
        //cout<<endl;
        //cout<<v[2]<<endl;
    }
}
int main()
{

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>map[i][j];
        }
    }//读取地图
    for(int i=1;i<100;i++)
    {
        v[i]=100000;
    }
    cont=1;
    prim();
    for(int i=1;i<=n;i++)
    {
        cout<<tree[i]<<endl;
    }

    cout<<sum<<endl;
    return 0;
}