算法练习(95):quick-find分析(1.5.8)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• quick-find分析

题目

1.5.8 用一个反例证明 quick-find 算法中的 union() 方法的以下直观实现是错误的。

---

1.5.8 Give a counterexample that shows why this intuitive implementation of union() for quick-find is not correct:

public void union(int p, int q)
{
   if (connected(p, q)) return;
   // Rename p’s component to q’s name.
   for (int i = 0; i < id.length; i++)
       if (id[i] == id[p]) id[i] = id[q];
    count--; 
}

分析

我们这里先贴出原来的union方法

public void union(int p, int q) {  // Put p and q into the same component.
    int pID = find(p);
    int qID = find(q);
    // Nothing to do if p and q are already in the same component.
    if (pID == qID) return;
    // Rename p’s component to q’s name.
    for (int i = 0; i < id.length; i++)
        if (id[i] == pID) id[i] = qID;
    count--;
}

我们可以看到主要的区别点在于for循环下面的这句话：

if (id[i] == pID) id[i] = qID;

我们知道，这里的pID和qID都是整形值，是固定的，但题目中给的

if (id[i] == id[p]) id[i] = id[q];

的id[p]和id[q]的值不一定固定。
在if后如果id[p]发生了改变，那么这个等式就可能出问题

答案

id 0 0 0 0 0 5 5 5 5 5
输入 0, 5
i = 0 时，id[i] == id[p]，此时 id[i] = id[q]。
数组变为 5 0 0 0 0 5 5 5 5 5
i = 1 时，id[i] != id[p]，算法出现错误。
如果在 id[p] 之后还有需要修改的元素，那么这个算法就会出现错误。