首页 > 代码库 > 普利姆算法(最小生成树)

普利姆算法(最小生成树)

int prim(){    int minid, i, j;    double mincost;    for(i = 2; i <= n; i ++){        lowcost[i] = map[1][i];    }    lowcost[1] = -1;    for(i = 2; i <= n; i ++){        mincost = INF;        minid = 0;        for(j = 2; j <= n; j ++){            if(lowcost[j] < mincost && lowcost[j] > 0){                mincost =  lowcost[j];                minid = j;            }        }        if(minid == 0){            return 1;        }        weight[i] = mincost;        lowcost[minid] = -1;        for(j = 2; j <= n; j ++){            if(map[minid][j] < lowcost[j]){                lowcost[j] = map[minid][j];            }        }    }    return 0;}
View Code