算法学习：算法C语言实现 第一章 引言

起源

笔者从化学润到电信之后宿舍也搬到了东区，在东区图书馆闲逛熟悉环境时偶然在书架上发现了这本大黑砖头，于是借回来仔细研究研究。粗略概览一番，真是不得不感慨书中自有黄金屋。原先在oiwiki上横看竖看看不懂的算法，现在居然如此简单直观。这篇博客主要记录书中的一些算法思路和代码，至于严谨的数学推导证明就略过了。

引言 连通性问题

第一章提出了一个典型问题——连通性问题：

给定整数对序列，其中每个整数代表一个对象，用p-q表示“p连接到q”，而且连通关系可传递，即若p-q且q-r，则p-r。

目标是写一个过滤程序：输入许多个整数对，当输入p-q时，如果从已输入的数据中无法推出p-q，则输出p-q；如果从已输入的数据中可以推理出p-q，则忽略p-q并继续输入下一对。

//示例：
输入 输出 
3 4  3 4
4 9  4 9
8 0  8 0
2 3  2 3
5 6  5 6
2 9     //2 3 4 9
5 9  5 9
7 3  7 3
4 8  4 8
5 6     //5 6
0 2     //0 8 4 3 2
6 1  6 1

连通性问题出现在许多现实应用中，例如计算机网络连接、电路连接、编译器判定变量名等价等问题。在此基础之上，还能在问题中添加更多信息使问题更加复杂，从而解决更多现实问题。

设计算法的思路首先是确定算法执行的基本操作。连通性问题中有两个基本操作：每当得到一个新对时，首先确定它是否属于一个新的连接，然后创建这个新连接或者将这个连接合并到已有的连接中。

这两个任务封装为抽象操作：查找（find）包含给定项的集合，合并（union）两个包含给定项的集合。

算法实现

书上给出了四种算法，每个算法都是前一个版本的改进。在对原始算法一步步改进的过程中，我们可以简单直观地学习到算法设计思路。

快速查找算法（quick find）

思路：数组中每个下标代表一个点，数组下标对应元素的数值表示点的位置。判断两个点是否连通的操作是，判断它们的位置是否相等。输入两个点使这两个点连通的操作是，遍历整个数组使所有连通的点的位置相等。

#include<stdio.h>
#define N 100
int main(void)
{
    int index;
    int p,q;
    int temp;
    int id[N];
    for(index=0;index<N;index++)
    {
        id[index]=index;
    }

    while (scanf("%d %d\n",&p,&q)==2)
    {
        if(id[p]==id[q])
            continue;//若p和q位置相等则跳过
        for(temp=id[p],index=0;index<N;index++)
        {
            if(id[index]==temp)
                id[index]=id[q];//若p和q位置不等则将与p和q位置相等的点位置全部换成q的位置
        }
        printf("%d %d\n",p,q);
    }

    return 0;
}

求解N个对象的连通性问题，如果执行M次合并操作，那么快速查找算法至少执行M*N条指令。

快速合并算法（quick union）

思路：数组每一个下标表示一个点，每个下标所指元素对应的数值表示这个点的父节点对应下标。输入两个点并使其连通的操作是，使这两个点互为父子节点，所有连通的点组成一棵树。判断两个点是否连通的操作是，找到这两个点的根节点，并判断是否为同一个点。

//用这段代码替换快速查找算法中的while循环体
while (scanf("%d %d\n",&p,&q)==2)
    {
        int i,j;
        
        for(i=p;i!=id[i];i=id[i]);//输入一个点p，找到p点的树根节点下标并赋给i
        for(j=q;j!=id[j];j=id[j]);//输入一个点q，找到q点的树根节点下标并赋给j
        if(i==j)
            continue;//两个点在同一棵树上，不输出
        id[i]=j;//使p和q两点的根节点互为父子节点，即连在一棵树上
        printf("%d %d\n",p,q);//若两个点不在同一棵树上则输出
    }

对于M>N，快速合并算法求解N个对象、M个对的连通问题需要执行M*N/2条指令。

加权快速合并算法（weighted quick union）

在快速合并算法基础上再用另一个数组记录树根节点所在树的总节点数，使得合并操作能把较小树连接到较大树上，防止树枝末端叶节点到根节点最长路径的增长。

#include<stdio.h>
#define N 100

int main(void)
{
    int i,j;
    int p,q;
    int id[N],size[N];

    for(i=0;i<N;i++)
    {
        id[i]=i;
        size[i]=1;
    }
    
    while (scanf("%d %d\n",&p,&q)==2)
    {
        for(i=p;i!=id[i];i=id[i]);
        for(j=q;j!=id[j];j=id[j]);
        if(i==j)
            continue;
        if(size[i]<size[j])//把短树的树根作为长树的树根的子节点
        {
            id[i]=j;
            size[j]+=size[i];
        }
        else
        {
            id[j]=i;
            size[i]+=size[j];
        }
        printf("%d %d\n",p,q);
    }
}

对于N个对象，加权快速合并算法判定两个对象是否连通，至多需要遍历2lgN个指针。

路径压缩算法（path compression）

等分路径压缩通过使每条链接跳跃到树中向上的路径的下一个节点实现压缩，等分了遍历的任何路径的长度。经过长序列的合并操作后，树几乎完全扁平。

//用这段代码替换加权快速合并算法的while循环体
while (scanf("%d %d\n",&p,&q)==2)
    {
        for(i=p;i!=id[i];i=id[i])
            id[i]=id[id[i]];//每路过一次叶节点就把这个节点连接到它父节点的父节点，从而使最大路径缩小为二分之一
        for(j=q;j!=id[j];j=id[j])
            id[j]=id[id[j]];
        if(i==j)
            continue;
        if(size[i]<size[j])//把短树的树根作为长树的树根的子节点
        {
            id[i]=j;
            size[j]+=size[i];
        }
        else
        {
            id[j]=i;
            size[i]+=size[j];
        }
        printf("%d %d\n",p,q);
    }

总结

设计算法的主要步骤：

• 确定完整明确的问题陈述以及问题固有的基本抽象操作。
• 仔细设计一个简单算法的简明实现。
• 通过逐步求精的过程开发改进后的实现，经过实验分析、数学分析或二者共同验证改进思想的效率。
• 找出数据结构或者算法操作的高级抽象表示，能够使改进版本的设计高效。
• 尽可能保证最坏情况下的性能，但实际数据可用时接受好的性能。