鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 操作系统维护 > 其它 > >

最小生成树

来源:互联网 作者:佚名 时间:2017-09-06 09:22
Prim 算法:Prim 集,已添加至 Prim 树中顶点集,在每个迭代中加入边 (u, v) ,u 是 Prim 集中点, v 是集外点(最小边),将边加入,将 v 纳入 Prim 集中 Kruskal 算法:加入最小树边,不形成回路,伪代码 Prim, Kruskal算法求组成树的边最小 void Kruskal(

Prim 算法:Prim 集,已添加至 Prim 树中顶点集,在每个迭代中加入边 (u, v) ,u 是 Prim 集中点, v 是集外点(最小边),将边加入,将 v 纳入 Prim 集中

Kruskal 算法:加入最小树边,不形成回路,伪代码

Prim, Kruskal算法求组成树的边最小

void Kruskal(Graph G) {
    int EdgesAccepted;
    DisjSet S;
    PriorityQueue H;
    Vertex U, V;
    SetType Uset, Vset;
    Edge E;

    Initialize(S);
    ReadGraphIntoHeapArray(G, H);
    BuildHeap(H);

    EdgesAccepted = 0;
    while (EdgesAccepted < NumVertex -1) {
        E = DeleteMin(H);
        Uset = Find(U, S);
        Vset = Find(V, S);

        if (Uset != Vset) {
            EdgesAccepted++;
            SetUnion(S, Uset, Vset);
        }
    }
}

 

网友评论
<