求连通分量个数

分量个数"/>

求连通分量个数

如图所示：

要求该图中连通分量个数，该图可以简化为两个节点之间的连线（整数对 p , q ）

quick-find算法(O(N^2))，也是一般人最容易想到的算法

1. 用一个id数组来确定两个节点之间是否存在于相同的连通分量中 ， 保证同一个连通分量的所有节点的在id数组中的值全部相同（id数组记录的是p点所在连通分量的标号）

2. 先用 find函数 判断p , q是否在同一个相同分量，如果是，则不做任何操作，如果不在，将p , q所在的连通分量用  union 函数连接起来

int count = id.length;        //记录连通分量个数public int find(int p)
{return id[p];
}public void union (int p,int q)  //将p，q归并到相同的分量
{int pID = find(p);int qID = find(q);if(pID == qID)   //如果已经是在同一个分量，不做任何操作return;  for(int i = 0; i < id.length; i++)if(id[i] == pID)id[i] = qID;count--;    //分量个数减1    
}

但是上述算法必须每次扫描原来的id数组，再改变 p , q的对应id值，这样太过于复杂，所以有了下面算法

quick-union算法（O(N^2)）

为了提高union函数的速度，可以在实现find方法时，从给定的节点开始，由它的链接得到另一个节点(id数组不再是记录p点所在的连通分量标号，而是记录p点的上一个节点，类似于链表)，一直下去，直到找到根节点，将两个根节点直接连接在一起即可

int count = id.length;             //  记录连通分量个数for(int i = 0; i < id.length; i++)      //  初始化所有节点的根节点为自身
{id[i] = i;
}int find(int p)              //  类似链表，直到找到根节点为止
{while(p != id[p])p = id[p];return p;
}void union(int p, int q)
{int pRoot = find(p);int qRoot = find(q);if(pRoot == qRoot)return ;id[pRoot] = qRoot;       //  将两个根节点连接count--;                 //  连通分量个数减1
}

quick-union算法看上去比quick-find算法快，因为它不需要对每个输入都遍历id数组，在最好的情况下，find()只需要访问一次数组即可找到根节点，但是最坏情况下需要访问2*N + 1次，所以需要的复杂度也是O(N^2) , 但是比quick-find要快

union-find(加权quick-union算法  , O(n * logn) , 目前较好的算法)

在quick-union算法中，较坏情况下是在一条较长的链中寻找根节点，所以在该算法中，手动将较小的链加到较大的链中，而不是像上面算法一样无脑的连接起来，以达到平衡每个树的节点个数尽可能相等

public class WeightedQuickUnionUF
{private int [] id;          //  记录该节点的根节点信息private int [] sz;          //  记录各个节点所对应的分量大小，即每条链的节点数private int count;public WeightedQuickUnionUF(int N){count = N;id = new int [N];for(int i = 0; i < N; i++)       //  初始化节点的根节点为自身id[i] = i;for(int i = 0; i < N; i++)       //  初始化每个链的节点个数为1sz[i] = 1;}public int find(int p){while(p != id[p])p = id[p];return p;}public void union(int p,int q){int i = find(p);int j = find(q);if(i == j)return;if(sz[i] < sz[j]){id[i] = j;            //  将较小的链连接到较大的链上(更新小链的根节点的id值为//  较大链的根节点)sz[j] += sz[i];       //  更新链的长度，即节点个数}else{id[j] = i;sz[i] += sz[j];}count--;                  //  连通分量个数减1}
}

带路径压缩的加权quick-union算法（O(n*logn) , 目前最优的算法）

基于上述加权quick-union算法 ， 在理想情况下，我们希望每个节点都直接连接到它的根节点，但是又不像quick-find算法那样通过修改大量连接达到该目的，所以只需在find()方法中添加一个循环，让在路径上遇到的所有节点的id值变成所在链的根节点，这样得到的一棵树是一颗几乎完全扁平化的树

public int find(int p)
{int root = id[p];while(root != id[root])root = id[root];while(p != root){int q = id[p];id[p] = root;p = q;}return root;
}