mark 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];
            }
        }
    }
}
上一篇:【数据结构】 最小生成树(二)——kruskal算法


下一篇:【数据结构】 最小生成树(三)——prim算法