《C语言每日一练》|《画解数据结构》(3 - 4)- 最小生成树

本文已收录于专栏 画解数据结构

文章目录

    • 前言
    • 一、概念
      • 1、生成树
      • 2、最小生成树
    • 二、算法
      • 1、Prim
        • 1)算法描述
        • 2)源码剖析
        • 3)动图详解
        • 4)时间复杂度
      • 2、Kruscal
        • 1)算法描述
        • 2)源码剖析
        • 3)动图详解
        • 4)时间复杂度
      • 3、Boruvka
        • 1)算法描述
        • 2)源码剖析
          • 2.1)数据结构
          • 2.2)插入
          • 2.3)查询
          • 2.4)分治
        • 3)时间复杂度

前言
??好久没有写图论相关的文章了,趁着今天月黑风高,夜深人静,今天介绍一个利用贪心思想求解的算法,即图论中非常重要的概念,它就是:


「 最小生成树 」
一、概念 1、生成树
????一个连通图,它的 极小连通子图 就是生成树。它含有图中所有的n n n 个结点,并且只有能够构成树的n ? 1 n-1 n?1 条边。如图所示的红色边就是其中一个生成树。
《C语言每日一练》|《画解数据结构》(3 - 4)- 最小生成树
文章图片

2、最小生成树
【《C语言每日一练》|《画解数据结构》(3 - 4)- 最小生成树】????当图上的边有权值时,我们把构造这个 极小连通子图 的最小总代价生成树称为 最小生成树。如下图所示的红色线段组成的生成树就是最小生成树。
《C语言每日一练》|《画解数据结构》(3 - 4)- 最小生成树
文章图片

二、算法 ????找最小生成树的常用算法主要有三种:Prim、Kruscal、Boruvka。
1、Prim
1)算法描述
????Prim 算法是基于贪心的,算法描述如下:
????a. 利用邻接矩阵存储dist[i][j]两点i i i 和j j j 之间的距离;
????b. 用cost[i]来表示 最小生成树集合 和 非最小生成树 中的点i i i 的最小距离,当cost[i] = 0代表i i i 就是 最小生成树 集合中的顶点。
????c. 由于是生成树,所以顶点0 0 0 一定在树上,初始化cost[i]就是0 0 0 和i i i 的距离(因为 最小生成树集合 目前只有0)。
????d. 从cost[i]中寻找一个值不为零(因为值为零表示是最小生成树集合中的点)且最小的顶点u,那么 cost[u]一定是 最小生成树上的边。于是,u也成了 最小生成树上的点。
????e. 然后,继续用u去更新cost[i],即更新 最小生成树集合 和 非最小生成树的点 之间的距离,回到 d 继续迭代计算。
2)源码剖析
int minSpanningTree(int n, int dist[maxn][maxn]) { int i, u, ret, dis; int cost[maxn]; for(i = 0; i < n; ++i) { cost[i] = (i == 0) ? 0 : dist[0][i]; // (1) } ret = 0; // (2) while(1) { dis = inf; for(i = 0; i < n; ++i) {// (3) if(cost[i] && lessthan(cost[i], dis) ) { dis = cost[i]; u = i; } } if(dis == inf) { return ret; // (4) } ret += cost[u]; // (5) cost[u] = 0; // (6) for(i = 0; i < n; ++i) {// (7) if(cost[i] && lessthan(dist[u][i], cost[i])) { cost[i] = dist[u][i]; } } }return inf; }

  • ( 1 ) (1) (1) cost[i]表示 当前最小生成树集合 和 当前非最小生成树 中的点i i i 的最小距离,当cost[i] = 0代表i i i 就是 当前最小生成树 集合中的顶点;
  • ( 2 ) (2) (2) ret用来存储最小生成树边权之和,初始化为 0;
  • ( 3 ) (3) (3) 从cost[i]中寻找一个值不为零(因为值为零表示是最小生成树集合中的点)且最小的顶点u,那么 cost[u]一定是 最小生成树上的边。于是,u也成了 最小生成树上的点;
  • ( 4 ) (4) (4) 整个查找过程完成,直接返回最小生成树的边权总和;
  • ( 5 ) (5) (5) 将当前边cost[u]加入最小生成树;
  • ( 6 ) (6) (6) 将当前点u加入最小生成树;
  • ( 7 ) (7) (7) 继续用u去更新cost[i],即更新 最小生成树集合 和 非最小生成树的点 之间的距离;
3)动图详解 《C语言每日一练》|《画解数据结构》(3 - 4)- 最小生成树
文章图片

4)时间复杂度 ????当有n n n 个结点的时候,每个结点第一次被加入 最小生成树集合 的时候,都要更新其它结点的距离,一共n n n 个结点,所以时间复杂度为O ( n 2 ) O(n^2) O(n2)。
2、Kruscal
????前置算法:夜深人静写算法(五)- 并查集
1)算法描述
????Kruscal 算法也是基于贪心,并且采用 并查集 实现,算法描述如下:
????a. 将图中所有的边按照三元组( u , v , w ) (u, v, w) (u,v,w) 来存储。
????b. 然后按照第三关键字w w w 将所有边进行递增排序;
????c. 顺序取边,并且判断当前边( u , v ) (u, v) (u,v) 的两个顶点u u u 和v v v 是否在同一个集合。如果不在,则这条边就是 最小生成树 上的边,权值累加,合并两个点;如果在,则这条边舍去;
????d. 反复迭代取边,直到总共取了n ? 1 n-1 n?1 条边,则算法结束。
2)源码剖析
#define maxn 1010int pre[maxn]; void unionfind_init(int n) {// (1) for(int i = 0; i < n; ++i) { pre[i] = i; } }int unionfind_find(int x) {// (2) return pre[x] == x ? (x) : (pre[x] = unionfind_find(pre[x])); }bool unionfind_union(int x, int y) {// (3) int px = unionfind_find(x); int py = unionfind_find(y); if(px == py) { return false; } pre[px] = py; return true; }struct KEdge {// (4) int u, v, w; }E[maxn * maxn]; int cmp(const void* a, const void* b) {// (5) struct KEdge *pa = (struct KEdge *)a; struct KEdge *pb = (struct KEdge *)b; return pa->w - pb->w; }// 点的个数 n,边的个数 m int Kruscal(int n, int m, struct KEdge* edges) { int i, ret = 0; int edgeCnt = 0; qsort(edges, m, sizeof(struct KEdge), cmp); // (6) unionfind_init(n); // (7) for(i = 0; i < m; ++i) { if( unionfind_union( edges[i].u, edges[i].v ) ) { ret += edges[i].w; // (8) if(++edgeCnt == n-1) {// (9) return ret; } } } return 0; }

  • ( 1 ) (1) (1) 并查集的初始化;
  • ( 2 ) (2) (2) 带路径压缩的并查集查找操作;
  • ( 3 ) (3) (3) 并查集的合并操作;
  • ( 4 ) (4) (4) 定义边三元组;
  • ( 5 ) (5) (5) 按照边权从小到大排序的回调函数;
  • ( 6 ) (6) (6) 对所有边进行排序;
  • ( 7 ) (7) (7) 初始化所有结点的并查集信息;
  • ( 8 ) (8) (8) 将当前边加入到最小生成树中;
  • ( 9 ) (9) (9) 如果边数等于n ? 1 n-1 n?1 则找到解,直接返回;
3)动图详解 《C语言每日一练》|《画解数据结构》(3 - 4)- 最小生成树
文章图片

4)时间复杂度 ????由于对边进行了一次排序,所以当边数为m m m 时,时间复杂度为O ( m l o g m ) O(mlog_m) O(mlogm?)。
3、Boruvka
????前置算法:夜深人静写算法(七)- 字典树
1)算法描述
????Boruvka 解决的问题较为特殊,求的是异或的最小生成树。具体问题为:给定n ( n ≤ 200000 ) n (n \le 200000) n(n≤200000) 个点完全图,给定点权值a i ( a i ≤ 2 30 ) a_i(a_i \le 2^{30}) ai?(ai?≤230),每条边的权值为边的两点的异或值,原题见:codeforces/contest888/G。
????这个算法实现采用的是字典树。
????a. 将所有数按照递增排序;
????b. 将所有排好序的数字,按照顺序,从高位到低位,插入到高度固定的 01-字典树 中;
????c. 分治求解,对于一棵子树,如果只有左子树,那么最小生成树就一定在左子树上;如果只有右子树,那么最小生成树一定在右子树上;否则就应该是 左子树 的情况 + 右子树的情况,再加上左子树中选出一个点,右子树中选出一个点,连边,并且取最小值。
2)源码剖析 2.1)数据结构
#include #include #include #include #include #include using namespace std; #define maxn 200010 #define maxb 31 #define maxnodes (maxn*maxb)#define UNDEF -1 #define ROOT 0struct TrieNode { int nodes[2]; // (1) int l, r; // (2) }T[maxnodes]; int TrieNodes; // (3)int a[200010]; void Init() {// (4) memset(T, UNDEF, sizeof(T)); TrieNodes = 1; }int GetTrieNode() {// (5) return TrieNodes++; }

  • ( 1 ) (1) (1) 字典树结点的两个子结点(0 和 1);
  • ( 2 ) (2) (2)[ l , r ] [l, r] [l,r] 代表以当前结点为根的子树,管辖的 原数组a [ ] a[ ] a[] 的区间范围;
  • ( 3 ) (3) (3) TrieNodes本次样例计算中,字典树结点的总个数;
  • ( 4 ) (4) (4) 对字典树结点进行初始化;
  • ( 5 ) (5) (5) 生成一个新的字典树结点;
2.2)插入 ????首先,把所有的数字先映射到一棵 01 字典树 上。如图所示,代表的是一个至多三位的集合组成的字典树。其中集合中的元素可重复,分别为{ ( 001 ) 2 , ( 011 ) 2 , ( 011 ) 2 , ( 100 ) 2 } \{ (001)_2, (011)_2, (011)_2, (100)_2\} {(001)2?,(011)2?,(011)2?,(100)2?}。
《C语言每日一练》|《画解数据结构》(3 - 4)- 最小生成树
文章图片

????绿色 代表字典树边权;
????红色 代表集合中的十进制数转换成二进制以后,映射到字典树的情况;
????蓝色 代表字典树根结点到当前结点的边路径组成的二进制序列;
????橙色 代表这个数字在集合中出现的次数。
void TrieInsert(int x, int idx) {// (1) int now = ROOT; // (2) for(int i = maxb-1; i >= 0; --i) { int bit = ((x>>i)&1); // (3) if(T[now].nodes[bit] == UNDEF) {// (4) T[now].nodes[bit] = GetTrieNode(); }if( T[now].l == UNDEF ) {// (5) T[now].l = idx; } T[now].r = idx; // (6) now = T[now].nodes[bit]; // (7) } }

  • ( 1 ) (1) (1) void TrieInsert(int x, int idx)代表将 x = a[idx]按照从高到低位插入到字典树中,idx代表排序后数组a的下标;
  • ( 2 ) (2) (2) 从根结点开始;
  • ( 3 ) (3) (3) 计算x x x 的第i i i 位,存储到bit中;
  • ( 4 ) (4) (4) 如果对应子树不存在,则创建一个新的字典树结点;
  • ( 5 ) (5) (5) 如果对应原数组左区间不存在,则置为当前下标;
  • ( 6 ) (6) (6) 枚举到当前下标,则右区间一定是当前下标;
  • ( 7 ) (7) (7) 迭代枚举子树;
2.3)查询 ????查询就是给定 一棵子树 和 一个值x x x,要求在 给定子树 上找到和x x x 异或最小的值;
long long TrieQuery(int now, int depth, int x) { long long ret = 0; for(int i = depth; i >= 0; --i) {// (1) int bit = ((x>>i)&1); if(T[now].nodes[bit] != UNDEF) {// (2) now = T[now].nodes[bit]; }else { now = T[now].nodes[bit^1]; // (3) ret += (1<

  • ( 1 ) (1) (1) 从当前深度往下迭代;
  • ( 2 ) (2) (2) 如果有和x x x 一样的位,则尽量取一样,这样第i i i 位异或得到的值为 0,一定更优;
  • ( 3 ) (3) (3) 反之,只能走另一棵子树,异或的值为 1<,累加到结果中;
  • ( 4 ) (4) (4) 最后,返回所有的累加和;
2.4)分治 ????分治是在字典树上求解。
????原理就是左子树看成是一个连通块,右子树看成是一个连通块,那么只需要枚举左子树中的任意点,并且在右子树中找到最小的异或值,这样就能把左右子树进行连通,形成生成树。
long long Boruvka(int now, int depth) { if(now == UNDEF) { return 0; // (1) } long long l = Boruvka(T[now].nodes[0], depth-1); // (2) long long r = Boruvka(T[now].nodes[1], depth-1); // (3) long long ans = l + r; if(T[now].nodes[0] != UNDEF && T[now].nodes[1] != UNDEF) { int x = T[now].nodes[0], y = T[now].nodes[1]; // (4) long long ret = 1e9; ret *= ret; for(int i = T[x].l; i <= T[x].r; ++i) {// (5) ret = min(ret,TrieQuery(y, depth-1, a[i]) + (1<

  • ( 1 ) (1) (1) 如果点集是空集,则最小生成树的值一定是 0,直接返回;
  • ( 2 ) (2) (2) 求左边集合(左子树)构成的连通图的最小生成树;
  • ( 3 ) (3) (3) 求右边集合(右子树)构成的连通图的最小生成树;
  • ( 4 ) (4) (4) 对于左子树x和右子树y
  • ( 5 ) (5) (5) 枚举左子树中所有的元素,并且快速去右子树中查找和它异或的最小值,从而将左右子树变成连通的。由于在d e p t h depth depth 深度进行的分叉,所以这里异或一定多了一部分2 d e p t h 2^{depth} 2depth 出来,需要累加上去。
  • ( 6 ) (6) (6) 任何一个集合的最小生成树,就是左边连通图的最小生成树,和右边连通图的最小生成树,加上两个集合中最小的那条边,就是答案了。
3)时间复杂度
  • ( 1 ) (1) (1) 插入:总共n n n 个数,每个数插入都是31 31 31 次,所以时间复杂度为O ( n c ) O(nc) O(nc),其中c = 31 c = 31 c=31;
  • ( 2 ) (2) (2) 查找:由于采用的是分治,每个结点都会遍历一次,每次遍历到非叶子结点,都需要去对方的集合中进行 31 次查找,均摊下来也是O ( n c ) O(nc) O(nc)。
??有关 最小生成树 的的内容到这里就完全结束了,如果还有什么疑问,可以添加作者微信咨询。
??有关画解数据结构的源码均开源,链接如下:《画解数据结构》
添加 博主 获取付费专栏优惠券

    推荐阅读