首页 > 代码库 > 权重最小生成树的思想与Kruskal算法

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

    晚上做携程的笔试题,附加题考到了权重最小生成树。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 = 0; 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 = 0;    for (int i = 0; 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 - 1)                break;        }}int main(){    int V = 4;    vector<CEdge> edges;    edges.push_back({ 0, 1, 1 });    edges.push_back({ 0, 2, 2 });    edges.push_back({ 0, 3, 3 });    edges.push_back({ 1, 2, 4 });    edges.push_back({ 1, 3, 5 });    edges.push_back({ 2, 3, 2 });        //使用一个vector来表示各个子树(即集合A),    //root[i]=j,表示节点i与节点j位于同一子树上,并且所有位于此树的节点k,都有root[k]=j;    //初始化root[i]=i,表示每棵子树只是一个节点    vector<int> root(V, 0);    for (int i = 0; i < V; ++i)        root[i] = i;    //执行算法    Kruskal(V, edges.size(), edges, root);    while (1);    return 0;}

程序输出:

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

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