• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

数据结构与算法之最好学的最小生成树

开发技术 开发技术 4周前 (09-28) 24次浏览

 

数缺形时少直观,形缺数时难入微。

——华罗庚

最小生成树问题是我在各项图论问题中最先理解与解决的,其目的就是在连通图中选择出:

使得各点构成联通的最小边权的边集

其中用到的数据结构与算法也是相对很好理解的并查集Kruskal算法,我在我之前的文章小话数据结构-图 (聚焦与于实现的理解)也有提到过,现在再来系统的阐述一下这问题的解决思路。

并查集

并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题

并查集是一个写法简单,经常使用到的数据结构,主要操作有以下三种

初始化操作

int p[N]; //存储每个点的祖宗节点
for (int i = 1; i <= n; i ++ ) 
        p[i] = i;// 初始化,节点编号是1~n

 

查找函数

int find( int x ){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];//返回的是x的祖宗节点
    }

 

合并操作

p[find(a)] = find(b);//将a加入b的祖宗的集合

 

并查集还可以维护每一个子集的大小、或是自子集到祖宗节点的距离,给出以下代码,只是使用Kruskal算法只需要使用朴素的并查集就可以了。

    int p[N], size[N];//p[]存储每个点的祖宗节点, size[]表示祖宗节点所在集合中的点的数量
int find(int x){
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
​
    for (int i = 1; i <= n; i ++ ){// 初始化,节点编号是1~n
        p[i] = i;
        size[i] = 1;
    }
​
    // 合并a和b所在的两个集合并储存集合中元素个数:
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

 

    
int p[N], d[N];//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
int find(int x){
        if (p[x] != x){
            int u = find(p[x]);
            d[x] += d[p[x]];//继承偏移量
            p[x] = u;
        }
        return p[x];
    }
​
    for (int i = 1; i <= n; i ++ ){// 初始化,节点编号是1~n
        p[i] = i;
        d[i] = 0;
    }
​
    // 合并a和b所在的两个集合:
    p[find(a)] = find(b);
    d[find(a)] = distance; // 初始化find(a)的偏移量

 

Kruskal算法【O(mlogm)】

这个顶着一个高端名字的针对解决最小生成树的算法,也就是一个彻头彻尾的贪心思想算法,基本的步骤如下

①:将所有边按照权值从小到大排序

②:将所有边依次放入图中,如果没有连入新的点,则丢弃不要。

③:当整个图联通时,返回结果

这里给一张别人博客里非常直观的动图

数据结构与算法之最好学的最小生成树

在②步骤中,并查集就可以发挥出其作用,快速的判定出当前选择的边的点是否在一个集合中,从而方便的实现算法

那我们直接用代码来实现:

int n, m;
int p[N];
​
struct Edge{
    int a, b, w;
}edges[M];
​
int find(int x){
    if (p[x] != x) 
        p[x] = find(p[x]);
    return p[x];
}
​
int kruskal(){
    sort(edges, edges + m);//排序
    for (int i = 1; i <= n; i ++ ) 
        p[i] = i;
    int res = 0, cnt = 0;//res记录权值,cnt记录已选择的边数
    for (int i = 0; i < m; i ++ ){
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
​
        a = find(a), b = find(b);
        if (a != b) {//将选择的边并入图中
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }
​
    if (cnt < n - 1) return INF;//若结束后不能使整个图联通,则无法求出结果
    return res;
}

 

至此,kruskal算法就成功实现了,可以根据实际情况改变部分参数,从而获得需要求解的部分。

希望我的抛砖引玉能引起更多的思考😄!


喜欢 (0)