个人总结，欢迎拍砖~

Prim

算法思想

1. 将带权图G顶点分成两个集合A和B，初始时A中只有一个点；
2. 取最小的交叉边(x,y)，x∈A，y∈B；
3. 将y加入A；
4. 直至若集合A中包含所有点。

过程演示

Code

int n;int g[NUM][NUM];bool vis[NUM];int lowc[NUM];int Prim()//点是0~n-1{    int ans=0;    memset(vis,false,sizeof(vis));    for(int i=1; i
     
      lowc[j])            {                Min=lowc[j];                k=j;            }        }        if(Min==INF)return -1;//原图不连通        ans+=Min;        vis[k]=true;        for(int j=0;j
      
       g[k][j])                lowc[j]=g[k][j];        }    }    return ans;}
      
     

版权声明：本文为博主原创文章，未经博主允许不得转载。