来自普林斯顿的算法课程

一道有趣的面试题

Social network connectivity. Given a social network containing n members and a log file containing m timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e., every member is a friend of a friend of a friend ... of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be mlogn or better and use extra space proportional to n.
这道题目大致的意思是：

{   
       "2017-08-01":"张三 李四";   
       "2017-08-02":"王五 马六";    
       "2017-08-02":"张三 刘八";    
       "2017-08-02":"赵二 王五";   
       "2017-08-03":"蛤蛤 西方记者";    
       "2017-08-04":"西方记者 李四";  
               ...    
       "2017-08-11":"苟利 刘八";
}

文件记录了 m,n 建立关系的时间。关系是对等的：0,1建立关系、1,2 建立关系，则 0,2也建立了关系。日志已按时间排序。需要找到日志中所有人都建立关系的最早时间。
看看怎么解决这个问题。

Quick Find

可以将人名转换成数字，再用数组表示这些人。假如共有N个人，则这N个人分别对应数字0~N-1。

var person=[];
for(let i=0;i<N;i++){
     person[i]=i;
}

preson

用person数组表示这N个人，第一个人是person[0]第二个人是person[1]...
当两个人 p,q 建立关系的时候，让person[q]==person[p]。
当两个人x,z建立关系的时候，让person[z]==person[x]。

person[5]==person[3]&&person[9]==person[6]

[3],[5],[9],[6]均相等

function connected(p,q){
    return person[p]==person[q];
}

当两个人p,q建立关系时,也只需要将值等于q的所有人的值均修改成p的值即可。

function union(p,q){
    if(!connected(p,q){//p,q未建立关系
        for(let i=0;i<person.length;i++){
        if(person[i]==person[q]{
            person[i]=person[p];//将数组中所有值等于q的人都修改为值等于p
        }
    }
}

那怎么判断是否所有人都建立了关系呢？
人与人之间的关系就像是集合，有关系的人在同一个集合里。
{p,q,x,z},{w,s,t}¹
最开始N个人都没有关系，共有N个集合。当所有人都建立了关系的时候，就只有一个集合了。所以用一个变量count记录集合个数，当count==1的时候，说明所有人都建立了关系。输出此时的时间即可。
quick find 逻辑简单，一目了然。但是性能不够，N个人的union操作，有N²次数组的读取和写入。

Quick Union

quick find 时间复杂度为n²是因为当p,q未建立关系，属于两个不同集合
{q,w,e,r,t,y},{p,o,i,u}时,需要遍历整个数组以确定和q在一个集合中的所有人q,w,e,r,t,y，并将这些人依次和p建立关系。相当于将逻辑上的一次union操作进行了拆分。所以要找到一种方法，保存q,w,e,r,t,y的关系,做到一次union操作就能合并两个集合。

tree

function root(q){
    while(person[q]!=q){
    q=person[q];
    }
    return q;
}
function connected(p,q){
    return root(p)==root(q);
}

tree unioned.png

function union(p,q){
    let pid = root(p);
    let qid = root(q);
    person[pid]=qid;
}

quick union 算法的好处是避免了quick find 中union的循环，效率更高了。但是quick union 找寻找根节点的时候有循环操作，当一棵树变高了的时候，寻找根节点会消耗不少时间。

Weighted quick union

在quick union 算法中，union操作是直接让 p 所在的树成为 q 所在树的一个分支。这就会出现下图中的情况：

quick union tree.png

如果我们记下树的大小，让小树挂在大树根上，大部分情况下，树的高不会增加。

weighted quick union tree.png

function union(p,q){
    let pid = root(p);
    let qid = root(q);
    if(sz[qid]<sz[pid]){//sz数组记录每一棵树的节点个数
        person[qid]=pid;
        sz[pid]+=sz[qid];
    }else{
        person[pid]=qid;
        sz[qid]+=sz[pid];
    }
}

到这里就结束了吗？不，我们还可以让树的高度变得更低一点。

Weighted quick-union with path compression

直接看代码：

function root(q){
    while(person[q]!=[q]){
    person[q]=person[person[q]];
    q=person[q];
    }
return q;
}

让被查询过根节点的点直接挂在根节点上，使得树的高度进一步降低。

普林斯顿的算法课，是《算法》一书作者Robert Sedgewick在讲，深入浅出，非常值得学习。