目录

• 　最小生成树
  • Prim 算法

---

　最小生成树

Prim 算法

• 简介：类似 kruskal 算法

st=>start: test
cen=>operation: center
e=>end
st->cen->e

//直接调用　prim()
int m,n;
int mp[100][100];
int low[100];
int pre[100];
void prim()
{
    for(int i=2; i<=n; i++)
    {
        pre[i]=1;
        low[i]=mp[1][i];
    }
    low[1]=0;
    for(int j=2; j<=n; j++)
    {
        int idx,minm=INF ;
        for(int i=2; i<=n; i++)
        {
            if(low[i]&&low[i]<minm)
            {
                idx=i;
                minm=low[i];
            }
        }
        low[idx]=0;
        cout<<pre[idx]<<"    "<<idx<<endl;
        for(int i=2; i<=n; i++)
        {

            if(mp[i][idx]&&mp[i][idx]<low[i])
            {

                pre[i]=idx;
                low[i]=mp[i][idx];
            }
        }
    }
}