连通问题

　　写一段程序以实现“给出两点，判断其是否连通”。

　　这个题目可以应用于很多实际问题，如：两个城市间是否有铁路相连，两个电子元件是否有电路相连，两个终端是否有网络相连……此算法仅仅判断是否连通，如果还要求给出连通的具体路径，难度将陡然增加，并且会把问题引入另一个领域——图。

我的第一感觉是把所有节点用一个二维数组存储。在草纸上稍加勾画后便会发现几个问题：

　　1) 对于N个节点，需要N * N 个空间存储，当连通较少时大量的空间将会闲置，无论任何时候，浪费都是一种罪过；

　　2) 实现困难，不信的话就自己试试吧；

　　3) 这毫无疑问是最糟糕的方法。

　　其实稍加思考可以将空间减少指数级：用一维数组构造连通器，如果节点p、q连通，则令id[p] == id[q]。

　　下面是代码片段：

 1 public abstract class Arithmetic {  
 2   
 3     protected int id[] = new int[Constant.N];  
 4       
 5     public Arithmetic() {  
 6         init();  
 7     }  
 8       
 9     private void init() {  
10         for(int i = 0; i < Constant.N; i++) {  
11             id[i] = i;  
12         }  
13     }  
14   
15     public abstract void createConnect(int p, int q);  
16       
17     public abstract boolean isConnect(int p, int q);  
18 }  
19 
20 public class Arithmetic_1 extends Arithmetic {  
21   
22     public Arithmetic_1() {  
23         super();  
24     }  
25   
26     @Override  
27     public void createConnect(int p, int q) {  
28         int t = id[p];  
29         for(int i = 0; i < Constant.N; i++) {  
30             if(id[i] == t)  
31                 id[i] = id[q];  
32         }  
33     }  
34       
35     @Override  
36     public boolean isConnect(int p, int q) {  
37         return id[p] == id[q];  
38     }  
39 }

　　上面的代码可以解决一下小问题。当我试着对10,000个顺序自然数构随机构造10,000次连通时，它花了我一杯咖啡的时间！估计再增加一个0，想要得到结果就得等到“中国老百姓看病最不难”那天真正来临。

　　分析一下效率就知道，对N个数的M次连通，每次构造连通器都会花费N次循环，效率是N*M。如果看成一棵树的话，每次构造连通都将把整棵树毁掉，然后重新打造；如果把两个棵树合并，则需要同时毁掉两棵树，这可真够呛！

　　把两棵树合并的最简方法就是直接把树根合并，按照这个思路改进的代码如下：

 1 public void createConnect(int p, int q) {  
 2   
 3     int i,j;  
 4     for(i = p; i != id[i]; i = id[i]);  
 5     for(j = q; j != id[j]; j = id[j]);  
 6               
 7     if(i != j)  
 8         id[i] = j;  
 9 }  
10   
11 public boolean isConnect(int p, int q) {  
12           
13     int i,j;  
14     for(i = p; i != id[i]; i = id[i]);  
15     for(j = q; j != id[j]; j = id[j]);  
16           
17     return i == j;  
18 }

　　通过指针追溯的方式回答两点是否连通。

　　同样对10,000个顺序自然数构随机构造10,000次连通的测试，虽然可以马上产生连通器，但是在判断是否连通时花费了一些时间，对于大数据的实践，这个算法同样不适用。

　　方法二的结果似乎严重依赖输入，它通常枝繁叶茂，但有可能变得比摩天大楼还高，而且营养不良，正是这点严重影响了isConnect的效率。

　　如果你的方法可以改进，那么它通常可以进一步改进。接下来要做的就是使摩天大楼变成古老的中式建筑群。很简单，在方法二的基础上为树加权，使用另外一个数组sz[]来维护每棵连通树的节点个数，每次合并都会将较小的树连接到较大的树上。

 1 private int sz[] = new int[Constant.N];  
 2       
 3     public Arithmetic_3() {  
 4         super();  
 5           
 6         for(int i = 0; i < Constant.N; i++)  
 7             sz[i] = 1;  
 8     }  
 9   
10     @Override  
11     public void createConnect(int p, int q) {  
12   
13         int i,j;  
14         for(i = p; i != id[i]; i = id[i]);  
15         for(j = q; j != id[j]; j = id[j]);  
16           
17         if(i != j) {  
18             //将较小的树连接到较大的树上  
19             if(sz[i] < sz[j]) {  
20                 id[i] = j;  
21                 sz[j] += sz[i];  
22             }  
23             else {  
24                 id[j] = i;  
25                 sz[i] += sz[j];  
26             }  
27         }  
28     }

　　这次我甚至可以轻松的对1,000,000个顺序自然数构随机构造1,000,000次连通并很快得到两点是否连通的答案。

　　作者：我是8位的

　　出处：http://www.cnblogs.com/bigmonkey

　　本文以学习、研究和分享为主，如需转载，请联系本人，标明作者和出处，非商业用途！