最小生成树prim算法

Prim算法

设G=(V,E)是连通图，V={1,2,......,n}

构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就坐如下的贪心选择：

选取满足条件i属于S，j属于V-S,且c[i][j]最小边，并将顶点j添加到S中。这个过程一直进行到S=V时为止

#include<iostream>
using namespace std;
#define max 100
float c[max][max];//存放i,j的权值
float  lowcost[max];//lowcost[v]存放未放入生成树的一个顶点v到生成树所有顶点的最短边 
int  adjves[max];// 表示该顶点v最短边在生成树中的顶点 

void prim(int n){
    int s[max];//记录节点放入生成树的状态，0为未放入，1为已放入
    s[1]=1;//开始选择第一个节点放入生成树中 ，标记状态为1 
    
    
    //找到与第一个节点最小距离的节点 
    for(int i=2;i<=n;i++){ 
        lowcost[i]=c[1][i];//第i个节点到1节点的权值
        adjves[i]=1;//第i节点一生成树项链的顶点是1
        s[i]=0;//第i节点未放入生成树中 
    }
    
    for(int i=1;i<n;i++){
        float min=1000;//记录最最小权值的边
        int j=1;
        for(int k=2;k<=n;k++)
            if(lowcost[k]<min&&(s[k]!=1))
               {
                 min=lowcost[k];
                 j=k;//记录最短边的节点 
                }
        cout<<j<<" "<<adjves[j]<<endl;//打印加入生成树的节点j,并把j连接生成树的顶点输入
        s[j]=1;//节点j标记为已加入生成树
        for(int k=2;k<=n;k++)//找出与顶点j相邻的最短边的顶点 
           if(c[j][k]<lowcost[k]&&(s[k]!=1)){
                lowcost[k]=c[j][k];
                adjves[k]=j;
           } 
    } 
}
int main(){
    int n;//顶点的个数 
    int x,y;//相连的两个顶点 
    float value;//相邻两顶点的边权值 
    cout<<"请输入顶点的个数:"<<endl;
    cin>>n;
    for(int i=0;i<=n;i++)//初始化C二维数组 
       for(int j=0;j<=n;j++)
          c[i][j]=1000;//表示两顶点不相邻 
    cout<<"请输入顶点i与顶点j和它们之间的权值value(输入-1结束):"<<endl;
    cin>>x;
    while(x!=-1){//ctrl+z键结束 
        cin>>y>>value;
        c[x][y]=value;
        c[y][x]=value;
        cin>>x;
    }
    cout<<"最小生成树各节点的链接情况："<<endl;
    prim(n);
    return 0;
}