权重最小生成树的思想与Kruskal算法

时间：2021-03-11 16:29:49

本文有更新，请移步我的个人博客：https://blog.andyqiao.top/article/9/

晚上做携程的笔试题，附加题考到了权重最小生成树。OMG，就在开考之前，我还又看过一遍这内容，可因为时间太紧，也从来没有写过代码，就GG了。又吃了眼高手低的亏。这不，就好好总结一下，亡羊补牢。

权重最小生成树问题是指在一棵无向全连接图中找到一个无环子集T，既能将所有的结点连接起来，又具有最小的权重和。

    解决问题的核心是每次找到一条安全边加入到边集合A中，使得A仍然是某棵最小生成树的子集。

    Kruskal找到安全边的方法是：在所有连接森林中两棵不同树的边里面，找到权重最小的边（u，v），（1）如果u和v位于不同的子树，则该边就是一个安全边，将u和v位于的子树合并起来；（2）如果u和v位于相同子树，则该边不是一个安全边，如果将两棵子树连接起来，就会形成一个环。

我用详细注释的代码说明问题：

//合并节点a和b所属的两棵子树

void Union(int a, int b, int V,vector<int>& root)

{

    int root_a = root[a],root_b = root[b];

    //把b所在树的所有顶点都移植过去给a...  

    for (int i = ; i < V; i++)

        if (root[i] == root_b)

            root[i] = root_a;

}

//sort的比较函数

bool compare(const CEdge &a, const CEdge &b)

{

    return  a.weight < b.weight;

}

//Kruskal最小生成树算法

void Kruskal(int V, int E, vector<CEdge> &e,vector<int>& root)

{

    //以权重为参考值，排序所有边

    sort(e.begin(), e.end(), compare);

    int cnt = ;

    for (int i = ; i < E; i++)

        if (root[e[i].u]!=root[e[i].v]) //如果e[i].u和e[i].v不属于同一棵子树

        {

            cout << e[i].u << "---" << e[i].v << " "<<e[i].weight<<endl;//加入该边

            Union(e[i].u, e[i].v, V,root);           //合并两棵子树

            //易知最小生成树拥有V-1条边

            //如果已经组成最小生成树，就退出循环

            ++cnt;

            if (cnt >= V - )

                break;

        }

}

int main()

{

    int V = ;

    vector<CEdge> edges;

    edges.push_back({ , ,  });

    edges.push_back({ , ,  });

    edges.push_back({ , ,  });

    edges.push_back({ , ,  });

    edges.push_back({ , ,  });

    edges.push_back({ , ,  });

    //使用一个vector来表示各个子树（即集合A），

    //root[i]=j，表示节点i与节点j位于同一子树上，并且所有位于此树的节点k，都有root[k]=j;

    //初始化root[i]=i，表示每棵子树只是一个节点

    vector<int> root(V, );

    for (int i = ; i < V; ++i)

        root[i] = i;

    //执行算法

    Kruskal(V, edges.size(), edges, root);

    while ();

    return ;

}

程序输出：

0---1 1
0---2 2
2---3 2

相关文章