图的最小生成树,prime算法

算法的复杂度与节点数量有关,而与边无关。适用于稠密图。

  1.首先选出节点x,更新它与其他节点的边权值。

  2.将其自身的边权值设为-1,表示节点已被使用,或者说已经加入了U。

  3.找出相连边中最小权值的点v0,将它加入U(置为-1),并更新U中节点的所有边值。

  4.重复3,直到所有节点均加入U。

 

struct CloseEdge
{
    VerTextType adjvex; //最小边在u中的顶点
    ArcType lowcost;    //最小边权值
};



int minEdge(CloseEdge* closeEdge, int m) {
    int min = INT_MAX;
    int u = -1;
    for(int i = 0;i < m;++i) {
        if(closeEdge[i].lowcost  != -1 && closeEdge[i].lowcost < min) {
            min = closeEdge[i].lowcost;
            u = i;
        }
    }
    return u;
}

//G为二维数组,存储边
void minSpanTree(vector<vector<int> > G) {
    int m = G.size();
    if(m == 0) return;
    //以顶点0为起点,求最小生成树
    int u = 0;
    CloseEdge closeEdge[m];
    memset(closeEdge,-1,sizeof(CloseEdge)*m);
    for(int i = 1;i<m;i++){
        closeEdge[i] = {u, G[u][i]};
    }
    //此时已经知道了u周围的边中的最小边。
    closeEdge[0] = {0,-1};

    for(int i = 1;i<m;i++) {
        //v0是其最小边的一个顶点
        int v0 = minEdge(closeEdge, m);
        int u0 = closeEdge[v0].adjvex;
        cout<<u0<<v0<<endl;
        for(int j=0;j<m;++j) {
            //更新与v0相连的最边,选择小的。
            // G[v0][j] < closeEdge[j].lowcost ,一方面加入小的边,
            //另一面,closeEdge[j].lowcost 为-1可以防止u的图变成连通图。(默认边权值大于0,否则加数组used)
            if( j != v0 && G[v0][j] < closeEdge[j].lowcost) {
                closeEdge[j] = {v0, G[v0][j]};
            }
        }
        closeEdge[v0].lowcost = -1;
    }
}

  "心结如果真的打不开,你就给它系成个花样儿,其实生活就需要这样。"

上一篇:图-克鲁斯卡尔算法


下一篇:第六章学习小结