这是我在阅读<<算法1-4（C++实现）——基础，数据结构，排序和搜索（第三版）>>
([美]Robert Sedgewick 著， 张铭泽 赵剑云 梁勇等 译 中国电力出版社)
时整理的读书笔记,现在贴出来,希望能给初学者一些启发.
/*
Name: 连通问题
Copyright:
Author:
Date: 25-11-06 21:59
Description: 连通问题
假设有一个整数对的序列，每个整数代表某个类型的一个对象，p-q对表示"p连接到q"，
即p和q之间连通。假设连通关系具有传递性--如果p与q连通，q与r连通，那么p与r连通。
我们的目标是写一个过滤出那些不在集合中的对的程序：输入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
1-2 不输出 1-6-5-9-4-3-2
*/
/*
连通问题
该程序读入一组介于0和N之间（包含0，但不包含N）的非负整数对，p-q对表示p和q连通，
输出那些目前尚未连通的输入对。它使用了数组id，每个对象在数组中都有一项，
当且仅当p与q连通时id[p]和id[q]相等。为简化问题，我们定义N为编译时常量，
当然也可以通过输入确定N，再动态地分配id数组。
*/
#include <iostream>
using namespace std;
const int N = 9000;
bool IsConnected_1(int id[], int p, int q);
bool IsConnected_2(int id[], int p, int q);
bool IsConnected_3(int id[], int p, int q);
bool IsConnected_4(int id[], int p, int q);
bool IsConnected_5(int id[], int p, int q);
bool IsConnected_6(int id[], int p, int q);
int main()
{
int id[N];
for (int i=0; i<N; i++)
id[i] = i;
int p, q;
//////////此部分由用户输入数据测试代码/////////////////
// while (cin >> p >> q)
// {
// if (!IsConnected_6(id, p, q))
// cout << p << "-" << q << endl;
//
// for (int i=0; i<N; i++)
// cout << id[i] << " ";
// cout << endl;
// }
///////////////////////////////////////////////
/////////此部分由计算机产生大量随机数测试代码//////////////////
const int max = 80000;
int i = 0;
while (i < max)
{
p = rand() % N;
q = rand() % N;
if (p == q)
continue;
// cout << p << "-" << q << " : ";
if (!IsConnected_6(id, p, q));
// cout << p << "--" << q << endl;
// else
// cout << endl;
i++;
}
cout << clock() << endl;
/////////////////////////////////////
getchar();
return 0;
}
/*
经过大量数据的测试得知：
IsConnected_1受N的影响较大，而受max的影响很小。
IsConnected_2和IsConnected_3的时间复杂度在各种情况下均相当，均受max的影响较大，而受N的影响很小。
IsConnected_4，IsConnected_5和IsConnected_6的时间复杂度相当，其中IsConnected_4最好，
IsConnected_5其次，IsConnected_6较差，但它们都比前三者要快很多。三者均受max的影响较大，而受N的影响很小。
IsConnected_4与IsConnected_5的比较说明路径被压缩以后，每棵树的高度都很小，没有必要花费精力去记录权值。
带权的压缩路径算法 因为要增加部分代码和一个保存节点计数的数组，反而变慢了。
IsConnected_4与IsConnected_6的比较说明在压缩路径时，没有必要把所有的节点都指向根节点，
这样虽然实现了快速查找，但合并的时间增多。
所以 等分路径压缩的快速合并算法 是一种较为合理的算法。
*/
/*
连通问题的快速查找（慢速合并）算法
该算法设置一个临时变量t以存储id[p]的值，然后遍历数组，把所有等于t的数组元素全部设置为id[q]，
这样所有连通的点就都具有相同的值id[q]了 。该算法的查找两个点是否连通花费常数时间，
但合并两个对象时需要遍历数组，所以称之为快速查找（慢速合并）算法。
总结：对于N个对象的连通问题，如果要执行M次合并操作，那么快速查找算法将执行至少M*N条指令。
*/
bool IsConnected_1(int id[], int p, int q)
{
if (id[p] == id[q]) //已经连通
return true;
int t = id[p]; //此处为何要设置一个临时变量？
for (int i=0; i<N; i++)
{
if (id[i] == t) //想想如果把此处的t改成id[p]，结果会如何？id[p]的值发生变化，p之后的元素将不能被合并
id[i] = id[q];
}
return false;
}
/*
下面要介绍的是快速查找算法的互补算法--快速合并算法。它使用的数据结构也是数组，
数组的索引（下标）是对象的名字，初始时数组元素的值就等于其索引的值（指向自己），
但经过合并操作后，数组元素则有可能存储了相同集合中另一个对象的值（指向其他对象）。
要判断两个对象是否属于同一个集合，只需跟随每个对象的指针，直到到达一个指向自己的对象（我们称之为根）。
当且仅当经过上述过程得到同一个对象时，两个对象在同一个集合中，即二者已经连通。
如果二者不在同一个集合中，那么最终得到的一定是不同的对象（每个对象都指向自己）。
合并操作只需要将其中的一个链接到另一个即可，因此称之为"快速合并"算法。
快速合并算法相对于快速查找算法有所改进，但快速合并算法仍有它的局限性
--我们并不能保证在每种情况下它都比快速查找算法快，因为输入数据可能使查找操作变慢。
总结：对于N个对象的连通问题，如果输入了M对，且M>N，那么快速合并算法将执行至少M*N/2条指令。
*/
bool IsConnected_2(int id[], int p, int q)
{
int i, j;
for (i=p; i!=id[i]; i=id[i]) //寻找p所属集合的根
;
for (j=q; j!=id[j]; j=id[j]) //寻找q所属集合的根
;
if (i == j) //已经连通
return true;
id[i] = j; //合并p，q，即二者指向同一个根
return false;
}
/*
当输入的数据不理想时，快速合并算法的操作数要远远大于M*N/2。幸运的是，
我们对算法做一个简单地修改就可以保证这样的最坏情况不出现。
具体做法就是在进行合并操作时，不是简单地将第二棵树连接到第一棵，
而是对每棵树保持一个节点计数，并且总是将小的树连接到大的树上。
这一修改需要增加部分代码和一个保存节点计数的数组，但它提高了效率。
我们称这个算法为"带权的快速合并算法"。
总结：在确定N个对象的两个对象是否连通时，带权的快速合并算法将执行至少顺着指针走lgN步。
在N个对象M个连接的情况下，带权的快速合并算法最多执行M*lgN条指令。
而快速查找（慢速合并）算法的大多数情况（快速合并算法的少数情况）至少要执行M*N/2条指令，
二者形成鲜明对比。可见，使用带权的快速合并算法，可以保证在合理的时间内解决大多数实际问题。
*/
bool IsConnected_3(int id[], int p, int q)
{
static int sz[N] = {0};
int i, j;
for (i=p; i!=id[i]; i=id[i]) //寻找p所属集合的根
;
for (j=q; j!=id[j]; j=id[j]) //寻找q所属集合的根
;
if (i == j) //已经连通
return true;
if ( sz[i] > sz[j]) //合并p，q，即二者指向同一个根，并且总是将小的树连接到大的树上
{
id[j] = i;
sz[i] += sz[j];
}
else
{
id[i] = j;
sz[j] += sz[i];
}
return false;
}
/*
下面我们来看是否可以找到能保证线性性能的算法。这确实是一个困扰了研究人员许多年的问题。
进一步改进带权的快速合并算法的简单方法很多。理想情况下，我们希望每个节点都直接指向树的根节点，
但又不希望像快速合并算法那样进行大量的修改指针的操作。
我们可以采用使被测节点指向根节点的方法逼近理想情况。这种方法被称为"路径压缩"，
具体方法是在进行合并操作时，将所经过的节点的id数组项指向根节点，即该节点的值与根节点的值相等。
有很多方法可以实现路径压缩，我们所采用的算法被称为"等分路径压缩的快速合并算法"，
它的特点是通过连接时向上跳一步指向下一节点，采取这种压缩路径的方法显然比全路径压缩更容易实现。
*/
bool IsConnected_4(int id[], int p, int q) //不带权的压缩路径算法
{
int i, j;
for (i=p; i!=id[i]; i=id[i]) //寻找p所属集合的根
id[i] = id[id[i]]; //注意被处理的节点元素向根节点跳了一步，以压缩路径
for (j=q; j!=id[j]; j=id[j]) //寻找q所属集合的根
id[j] = id[id[j]];
if (i == j) //已经连通
return true;
id[i] = j; //合并p，q，即二者指向同一个根
return false;
}
bool IsConnected_5(int id[], int p, int q) //带权的压缩路径算法
{
static int sz[N] = {0};
int i, j;
for (i=p; i!=id[i]; i=id[i]) //寻找p所属集合的根
id[i] = id[id[i]]; //注意被处理的节点元素向根节点跳了一步，以压缩路径
for (j=q; j!=id[j]; j=id[j]) //寻找q所属集合的根
id[j] = id[id[j]];
if (i == j) //已经连通
return true;
if ( sz[i] > sz[j]) //合并p，q，即二者指向同一个根，并且总是将小的树连接到大的树上
{
id[j] = i;
sz[i] += sz[j];
}
else
{
id[i] = j;
sz[j] += sz[i];
}
return false;
}
/*
全路径压缩是指我们在进行每一次合并算法时将所经过的节点均指向新数的节点。
*/
bool IsConnected_6(int id[], int p, int q) //不带权的全路径压缩算法
{
int i, j;
for (i=p; i!=id[i]; i=id[i]) //寻找p所属集合的根
;
for (j=q; j!=id[j]; j=id[j]) //寻找q所属集合的根
;
if (i == j) //已经连通
return true;
int k, t;
for (k=p; k!=i; k=t) //合并时将所经过的节点均指向新数的节点
{
t = id[k];
id[k] = j;
}
for (k=q; k!=j; k=t) //合并时将所经过的节点均指向新数的节点
{
t = id[k];
id[k] = j;
}
id[i] = j; //合并p，q，即二者指向同一个根
return false;
}
评论