第1章导论

缺乏、安全感 2022-06-07 11:23 284阅读 0赞

这系列博客主要记录自己学习《算法：c语言实现》的过程。  
学习方法有二：  
1、Robert Sedgewick普林斯顿大学公开课，[课程链接见B站，带有中文字幕高大上][B]  
2、阅读课本：《算法：C语言实现第1-4部分》、《算法：C语言实现第5部分》

# 连通性问题描述： #

假如一个整数对序列，其中整数代表某种类型的一个对象（如计算机中的网络接口），序列连通性可以代表网络接口是否连通，这种问题在实际中应用很广。并且连通是可以传递的，例如1和2连通，2和3连通，那么1-2-3都连通。现在写一个程序，需要解释连通性问题，输入序列对，假如集合中已经连通了，那么不输出任何东西；假如没有连通，那么输出序列，并将序列解释为连通更新集合。  
最后处理的问题，可能就是集合非常大，当输入一个序列之后，可以给出序列是否连通以及连通的路径。

![这里写图片描述][SouthEast]  
首先集合中有三个连通域，输入2,5，由于在集合中没有连通，那么将2,5在集合中解释为连通，并更新集合，最后连通域变为2个。

# 快速查找 #

可以从集合中快速查找输入序列是否连通（connected操作），但是更新集合（union操作）比较慢。

*  选用的数据结构是数组  
    ![这里写图片描述][SouthEast 1]
 *  p和q连通，id\[p\] = id\[q\]。
 *  Connected操作：检查id\[p\]是否等于id\[q\]，这里因为只需要一条语句，所以叫快速查找
 *  Union操作：为了合并p和q，需要把所有与id\[p\]相等（这些本来连通）的数值改为id\[q\]。  
    ![这里写图片描述][SouthEast 2]

代码：

#include <stdio.h>
    #include <stdlib.h>
    #define N 10//仅仅考虑0-10以内的序列
    int p,q;//输入序列
    int id[N];//记录合并问题
    void Dispaly(int *a , int count);
    bool Connected(int p , int q);
    void Union(int p , int q);
    int main(void)
    {
        for(int i = 0 ; i < N ; ++i)
            id[i] = i;//初始化，表示各个序列都不连通
        Dispaly(id , N);
        while(scanf("%d %d" , &p,&q) == 2){
       //读取数值
            if( !Connected(p,q) ){
                Union(p,q);
                Dispaly(id , N);//显示合并之后的集合
            }
        }
        return 0;
    }
    
    void Dispaly(int *a , int count)
    {
        for(int i = 0 ; i < count ; ++i)
            printf("%d " , a[i]);
        printf("\n");
    }
    bool Connected(int p , int q)
    {
        return (id[p] == id[q]);
    }
    void Union(int p , int q)
    {
        int pid = id[p];
        int qid = id[q];
        for(int i = 0; i<N ; ++i){
            if(id[i] == pid)//连通，将与pid相等的数值全部修改为qid。
                id[i] = qid;
        }
    }

![这里写图片描述][SouthEast 3]

# 快速合并 #

快速查找中合并太消耗时间，所以需要寻找快速合并的方法。为了缩短合并遍历数组，这里采用树，因为树分叉所以可以减少遍历。  
数组每一项数值则表示其在树中的父节点，这样判断每一个索引对应的根节点是否一样就可以判断他们是否在一个连通域。

数据结构：

*  数组id\[N\]。
 *  id\[i\]里面存放i的父节点。
 *  i的根是id\[ id\[ …id\[i\]… \] \]，持续寻找直到父节点不再变化也就是找到根。  
    ![这里写图片描述][SouthEast 4]
 *  Connected操作：检查p和q有相同的根。
 *  Union操作：为了合并p和q，把p的根id设置成q的根id，也就是将含有p的小树变成含有q树的子树。这里查找需要遍历对应的树，而合并仅仅需要一句话（所以叫快速合并算法），那就是将含有p的树根设置成q树根的子树。  
    ![这里写图片描述][SouthEast 5]

代码：

#include <stdio.h>
    #include <stdlib.h>
    #define N 10//仅仅考虑0-10以内的序列
    int p,q;//输入序列
    int id[N];//记录合并问题
    void Dispaly(int *a , int count);
    bool Connected(int p , int q);
    void Union(int p , int q);
    int main(void)
    {
        for(int i = 0 ; i < N ; ++i)
            id[i] = i;//初始化，表示各个序列都不连通
        Dispaly(id , N);
        while(scanf("%d %d" , &p,&q) == 2){
       //读取数值
            if( !Connected(p,q) ){
                Union(p,q);
                Dispaly(id , N);//显示合并之后的集合
            }
        }
        return 0;
    }
    
    void Dispaly(int *a , int count)
    {
        for(int i = 0 ; i < count ; ++i)
            printf("%d " , a[i]);
        printf("\n");
    }
    int root(int i)
    {
        while(i != id[i]) i = id[i];//寻找根，因为开始初始化为根不一样。
        return i;
    }
    bool Connected(int p , int q)
    {
        return (root(p) == root(q));
    }
    void Union(int p , int q)
    {
        int rootp = root(p);
        int rootq = root(q);
        id[rootp] = rootq;//将p树设为q子树
    }

![这里写图片描述][SouthEast 6]

# 加权快速合并 #

前面两种算法虽然可以很容易实现，并且工作，但是都不支持大型动态连接的问题，所以需要改进。  
快速合并中，Connected操作太花时间了，当数据量巨大的时候，树的高度可能会参差不齐，并且某些树会很高，这样导致遍历查找依旧很慢。所以需要想办法避免大树。一种解决方案就是将小树连接到大树上面，以维持树平衡，这就是所谓的加权快速合并算法。下图是两种算法比较。  
![这里写图片描述][SouthEast 7]

数据结构：

*  和快速合并一样
 *  额外需要一个数组sz\[i\]，记录每个树中节点的个数。如sz\[3\]表示3下面子节点的个数。
 *  修改合并，将小树连接到大树上面。

代码：

#include <stdio.h>
    #include <stdlib.h>
    #define N 10//仅仅考虑0-10以内的序列
    int p,q;//输入序列
    int id[N];//记录合并问题
    int sz[N];//记录树的高度
    void Dispaly(int *a , int count);
    bool Connected(int p , int q);
    void Union(int p , int q);
    int main(void)
    {
        for(int i = 0 ; i < N ; ++i){
            id[i] = i;//初始化，表示各个序列都不连通
            sz[i] = 1;//初始化各个节点为独立树，并且高度是1
        }
        printf("id: ");
        Dispaly(id , N);
        printf("sz: ");
        Dispaly(sz , N);
        while(scanf("%d %d" , &p,&q) == 2){
       //读取数值
            if( !Connected(p,q) ){
                Union(p,q);
                printf("id: ");
                Dispaly(id , N);
                printf("sz: ");
                Dispaly(sz , N);
            }
        }
        return 0;
    }
    
    void Dispaly(int *a , int count)
    {
        for(int i = 0 ; i < count ; ++i)
            printf("%d " , a[i]);
        printf("\n");
    }
    int root(int i)
    {
        while(i != id[i]) i = id[i];//寻找根，因为开始初始化为根不一样。
        return i;
    }
    bool Connected(int p , int q)
    {
        return (root(p) == root(q));
    }
    void Union(int p , int q)
    {
        int rootp = root(p);
        int rootq = root(q);
        if(sz[rootp] < sz[rootq] ){
            id[rootp] = rootq;//rootp树小，作为rootq的子树
            sz[rootq] += sz[rootp];//更新rootq高度
        }else{
            id[rootq] = rootp;//rootq树小，作为rootp的子树
            sz[rootp] += sz[rootq];//更新rootp高度
        }
    }

![这里写图片描述][SouthEast 8]

# 对分路径压缩加权快速并集 #

加权快速合并可能形成的树并没有那么平，这里路径压缩就**是尽量将树压到最平（遍历各数次数最少），达到快速查找的效果**。  
当试图寻找包含给定节点的树的根节点的时候，需要访问从该节点到根节点路径上的每一个节点，于此同时可以将每一个节点都指向根节点（减少遍历）。回溯一次路径找到根节点，然后再回溯以此将树展平，这种做法可以最大限度将树展平。过程如下。  
![这里写图片描述][SouthEast 9]

代码：

#include <stdio.h>
    #include <stdlib.h>
    #define N 10//仅仅考虑0-10以内的序列
    int p,q;//输入序列
    int id[N];//记录合并问题
    int sz[N];//记录树的高度
    void Dispaly(int *a , int count);
    bool Connected(int p , int q);
    void Union(int p , int q);
    int main(void)
    {
        for(int i = 0 ; i < N ; ++i){
            id[i] = i;//初始化，表示各个序列都不连通
            sz[i] = 1;//初始化各个节点为独立树，并且高度是1
        }
        printf("id: ");
        Dispaly(id , N);
        printf("sz: ");
        Dispaly(sz , N);
        while(scanf("%d %d" , &p,&q) == 2){
       //读取数值
            if( !Connected(p,q) ){
                Union(p,q);
                printf("id: ");
                Dispaly(id , N);
                printf("sz: ");
                Dispaly(sz , N);
            }
        }
        return 0;
    }
    
    void Dispaly(int *a , int count)
    {
        for(int i = 0 ; i < count ; ++i)
            printf("%d " , a[i]);
        printf("\n");
    }
    int root(int i)
    {
        while(i != id[i]){
            id[i] = id[id[i]];//将树展平
            i = id[i];//寻找根，因为开始初始化为根不一样。
        }
        return i;//并返回树的根节点
    }
    bool Connected(int p , int q)
    {
        return (root(p) == root(q));
    }
    void Union(int p , int q)
    {
        int rootp = root(p);//第一次寻根已经展平树
        int rootq = root(q);//
        if(sz[rootp] < sz[rootq] ){
            id[rootp] = rootq;//rootp树小，作为rootq的子树
            sz[rootq] += sz[rootp];//更新rootq高度
        }else{
            id[rootq] = rootp;//rootq树小，作为rootp的子树
            sz[rootp] += sz[rootq];//更新rootp高度
        }
    }

注意因为这里寻根过程展平了树，所以大树的总节点数没有变化，但是大树的子树下面的节点发生了变化，没有在sz里面反应。所以这里加权仅仅是将节点比较小的树链接到节点比较多的树上面，起到了加权的效果。这就是这个算法的牛逼之处。这个逻辑有点绕。这个就可以解决大型动态链接性问题了。运用这种算法，假如有10亿个序列，这种方法仅仅需要6s，算法设计使得求解大规模问题成为可能，快的计算机并没有起到什么作用。

# 部分习题 #

[B]: http://www.bilibili.com/video/av8994940/
[SouthEast]: /images/20220607/e9f9621a345040b9b863521d5384b310.png
[SouthEast 1]: /images/20220607/53c5406e4b1d4ea982a1b2671c9f7895.png
[SouthEast 2]: /images/20220607/ad329ed9729b402288b38e056c560da9.png
[SouthEast 3]: /images/20220607/67965cbfe9004a5fb6b5784604198a8b.png
[SouthEast 4]: /images/20220607/fa002ba9176a43a1bd7d324ddb7ea390.png
[SouthEast 5]: /images/20220607/7e0845cfaac345d3948b6f291c28e94d.png
[SouthEast 6]: /images/20220607/95b3c711cf9d4513a641d91223a26c1d.png
[SouthEast 7]: /images/20220607/8d47238902884db4920ad7d04c56b28a.png
[SouthEast 8]: /images/20220607/885bb11f532148128d1687d1d3da78ba.png
[SouthEast 9]: /images/20220607/ea47aea293374de9bf2df06e101b043d.png