健指算法（二）模拟网络连通检查（按秩归并&路径压缩）

本来打算写多线程ThreadLocal的源码的，为什么突然转来写一篇关于并查集的日志，因为最近在改自己以前写的代码时，发现很多地方可以改写得更好，对于我来说，平时除了开发自己喜欢的软件外，最大的乐趣就是优化以前写过的代码，这次就来总结下当初写的并查集的两种优化算法：按秩归并和路径压缩。

例子是模拟网络连通检查，是这样一个问题，假设网络中分布着各个结点，这些结点可以是主机或是路由器，它们之间有的可以互相通信，有的还没有建立连接，无法通信。我们要写出一个程序，输入两个结点信息，判断它们是否能够通信，如果可以，则输出提示，否则让它们之间建立连接。因为是网络上的结点，它们有传递特性，即如果结点A和结点B连接，结点B和结点C连接，那么结点A和结点C也就建立了连接。如果结点A和结点B连接后，这对结点合并成一个连通分量，当结点B和结点C连接后，结点ABC三个也合并成了一个连通分量。

      这些结点的存储结构用树来表示，那么这个网络就是一片森林。为什么要用树来存储这些结点，因为我们来看看互连网络：

一个路由器可连接多个交换机，一个交换机能连接多台主机，所以用树来作为存储结构能很形象地表示出网络。树结点保存着与该结点相连的另外一个结点的名称，用这种关系来表示它们的连接状态，这样我们就可以从一个结点得到与其相连的下一个结点，由此我们可以一直寻找某一个连通分量中所含有的结点，直到最后找到根结点，即结点中标识符等于自己的结点，我们可以利用连通分量的根结点来判断两个结点是否相连，如果两个结点已连接，那么它们的根结点一定是相同的。接下来，根据问题的解决过程来设计API：

1. 第一步查找两个结点所在的连通分量，如果两个结点处在同一个连通分量中，那么它们就是已连接的：初始时假设这个网络中所有结点都是互不相连的，各自都是一个连通分量，当两个结点的父结点相同时，就认为它们是相连的网络，处在同一个连通分量中：

//查找网络n所在的连通分量标识符(用其根结点标识这个网络)
	public int Search(int networkAddress) {
		while(networkAddress != networkID[networkAddress]) {
			networkAddress = networkID[networkAddress]; //往上寻找它的根结点
		}
		return networkID[networkAddress];
	}

Search方法就是用来寻找一个结点的根结点，初始时所有结点都未相连，所以结点标识符都是等于自己，当两个结点例如A和B连接后，B结点的标识符就等于A了，所以可以从networkAddress[ B ] = A得到B与A连接，再从networkAddress[ A ] = A得到结点A是根结点，A就是这个连通分量的标识符，当结点C与结点B连接后，networkAddress[ C ] = B，由此可得C与B连接，再从networkAddress[ B ] = A找到A结点，所以结点C的根结点也是A，所以，结点ABC都拥有共同的根结点A，即表示这三个结点已建立连接。

1. 判断两个结点（或连通分量也行，有可能是一个连通分量中有多个结点，另一个连通分量中只有初始的一个结点）的连接状态：

//判断两个网络分量的连接状态
	public boolean ConnectionState(int networkAddress1, int networkAddress2) {
		return (Search(networkAddress1) == Search(networkAddress2));
	}

就是调用Search（）方法查找两个结点所在连通分量的根结点（标识符），判断它们是否相等，作为是否要将它们连接的依据。

1. 如果两个连通分量未连接，则为它们建立连接：建立连接前先获得两个连通分量的标识符，判断不相等后便把其中一个连通分量链接到另一个连通分量上，最后把记录网络中连通分量的变量componentCount--。

来看下运行结果：

 

用这样的方法可以解决问题了，不过方法不能应用于实际中的大数据处理，为什么呢？不是说方法错误，而是它的性能不够好，当处理的数据量很大时，它可能要运行很久很久，为什么会出现这种情况，因为我们是用树结构来实现的，它的运行过程是这样：

假设有两个网络（连通分量）要连接，当我们把树B的根结点连接到树A上，连接后的树变成这样：

树的最大高度就由原来的4变成了5，随着树高的增加，我们的Search方法查找某一结点的根结点这一动作就会越来越慢。那么优化的方法，就是想办法让树不要越长越高，虽然随着数据量的增大，树的规模不断增大，树高不可避免的也会跟着增高，但是我们有办法让树的增高速度降下来，也就是让归并后的树高尽可能矮，什么意思呢？我们来看下，上面我们是把树B连接到树A上，完成两个连通分量的连接，我们也可以把树A连接到树B上，同样能完成两个连通分量的链接：

而且这样做的好处是，把一个较矮的树连接到较高的树上后，整体树高并不会发生改变，最大树高还是等于4。

      实现这一优化，就是要每次连接两个连通分量时，先判断谁更“高”，也就是说在连通分量中我们要开辟一个新的存储结构或变量来存储每一个连通分量的“高度”，这就要额外的空间：

public class RankMergeDemo {
	int[] networkID; //存放网络地址的网络号
	int[] treeHeight; //存放每一个连通分量的树高
	int componentCount; //记录当前网络中连通分量的数量
	
	//构造函数初始化
	RankMergeDemo(int componentCount) {
		networkID = new int[componentCount];
		treeHeight = new int[componentCount];
		
		for(int i=1; i<componentCount; i++) {
			networkID[i] = i; //初始化每一个网络都各自是一个分量
			treeHeight[i] = 1; //初始化每一个连通分量的初始树高都是1
		}
		this.componentCount = componentCount; 
	}

我们额外开辟一个数组来存放每一个连通分量的高度，因为数组的下标 标识的是某一个结点，所以treeHeight[ ]数组也可以一一对应每一个结点，结点的值存放以该结点为根的树的高度。17行初始化时每一个结点的树高都是1。

//把两个未连接的网络分量连接
	public boolean ConnectToNetwork(int networkAddress1, int networkAddress2) {
		int network1_Root, network2_Root;
		network1_Root = Search(networkAddress1);
		network2_Root = Search(networkAddress2);
		//如果两个网络的根结点标识符不同,表明它们不在同一个连通分量,把它们连通
		if(network1_Root != network2_Root) {
			if(treeHeight[network2_Root] < treeHeight[network1_Root]) {
				networkID[network2_Root] = network1_Root; //把network2_Root接到network1_Root上
				treeHeight[network1_Root] += treeHeight[network2_Root]; //更新归并后的树高
			} else if(networkID[network2_Root] > networkID[network1_Root]) {
				networkID[network1_Root] = network2_Root;
				treeHeight[network2_Root] += treeHeight[network1_Root];
			} else {
				//两棵树等高
				networkID[network2_Root] = network1_Root;
				networkID[network1_Root]++; //树高增高一层
			}
			componentCount--; //连接后,网络中的连通分量-1
			return true;
		} else {
			return false;
		}
	}

在模拟网络连接方法中，第47行，先比较两个根结点的树的高度，然后把较矮的树的根结点设置成较高的树的根结点，如果能把较矮的树归并到较高的树上，那么归并后的整体树高不需要加一，当然还有一种情况就是，当要归并的两棵树的高度是一样的，那么无论哪棵树归并到哪棵树上，最后整体树高都要++。

      这样虽然实现了连接时的优化，但是我们用了一个额外的，且大小一样的数组来存放每一个连通分量的“高度”，面对庞大的数据量时，是不是一样感觉得不偿失呢？其实我们可以不用额外的空间来存放树的高度，在我们初始化连通分量标识符数组时，每一个初始值和它的下标一样，这是不是一个看似多余的动作呢？因为我们的数组下标已经标识了一个结点了。其实，我们可以这样做，对于每一个结点，我们仍然在结点中存放它们连接结点的标识符，但是对于根结点，我们用它来保存自己的树高，可是根结点用来保存树高后，怎么标识它自己是个根结点呢？可以把它设置成一个负数，只要值为负的，就表示它是森林中某一棵树的根结点，负数的值就标识这棵树的树高：

这样，当我们连接两个树（连通分量）时，先比较哪一棵树更高，注意这里树高用负值标识，所以数值越更大的那棵树树高更矮。比较完后，同样将较矮的树接到较高的树根结点上就行了：

实现这个方法，代码部分只要我们初始化时，把树中每一个值初始化为-1，因为一开始所有结点各自都是一个连通分量，所以它们都是根结点。

public class RankMergeDemo2 {
	int[] networkID; //存放网络地址的网络号和其相连的结点标识符
	int componentCount; //记录当前网络中连通分量的数量
	
	//构造函数初始化
	RankMergeDemo2(int componentCount) {
		networkID = new int[componentCount];
		for(int i=1; i<componentCount; i++) {
			networkID[i] = -1; //初始化每一个网络都各自是一个分量
		}
		this.componentCount = componentCount; 
	}

归并过程：

//把两个未连接的网络分量连接(按照连通分量树的高度来归并)
	public boolean RankMergeConnectToNetwork(int networkAddress1, int networkAddress2) {
		int network1_Root, network2_Root;
		network1_Root = Search(networkAddress1);
		network2_Root = Search(networkAddress2);
		//如果两个网络的根结点标识符不同,表明它们不在同一个连通分量,把它们连通
		if(network1_Root != network2_Root) {
			if(networkID[network2_Root] < networkID[network1_Root]) {
				networkID[network1_Root] = network2_Root; //把network2_Root接到network1_Root上
			} else if (networkID[network2_Root] > networkID[network1_Root]) {
				networkID[network2_Root] = network1_Root;
			} else {
				//两棵树等高
				networkID[network2_Root] = network1_Root;
				networkID[network1_Root]--;
			}
			componentCount--; //连接后,网络中的连通分量-1
			return true;
		} else {
			return false;
		}
	}

注意树高是负数就可以了，第42，43行，获得两个连通分量的根结点下标后，比较两个树高，如果连通分量2比连通分量1小，即连通分量2的树高更大，就把连通分量1连接到连通分量2的根结点上，即把连通分量2的根结点下标赋值给连通分量1的根结点，整体树高不发生改变。第50行，特殊情况处理，如果要连接的两棵树等高，那么两者合并树高必定会增加，所以随便两者谁接到谁的根结点上都可以，注意更新树高即可，因为是记录树高的值是负数，所以树高加一即树高--。

      按树高来归并两棵树是一种方法，还有另一种方法，更贴近于实际的网络中，就是按规模来归并，意思是我们把规模小的连通分量归并到规模大的连通分量上。使用这种方式的话，根结点保存的就不是树的高度，而是树的结点数，初始化时一样大家都是-1，表示大家都是只有自己一个结点，来看看按连通分量规模来归并要怎么做：

//把两个未连接的网络分量连接(按照连通分量树的规模来归并)
	public boolean HeightRankMergeConnectToNetwork(int networkAddress1, int networkAddress2) {
		int network1_Root, network2_Root;
		network1_Root = PathCompressionSearch(networkAddress1);
		network2_Root = PathCompressionSearch(networkAddress2);
		//如果两个网络的根结点标识符不同,表明它们不在同一个连通分量,把它们连通
		if(network1_Root != network2_Root) {
			if(networkID[network2_Root] < networkID[network1_Root]) {
				networkID[network1_Root] = network2_Root; //把network2_Root接到network1_Root上
				networkID[network2_Root] += networkID[network1_Root]; //更新树的规模
			} else if (networkID[network2_Root] > networkID[network1_Root]) {
				networkID[network2_Root] = network1_Root;
				networkID[network1_Root] += networkID[network2_Root];
			} 
			componentCount--; //连接后,网络中的连通分量-1
			return true;
		} else {
			return false;
		}
	}

既然根结点保存的是连通分量中的所有结点的数量，那么在归并时，像比较树高一样，比较谁更大谁更小，然后把规模较小的连通分量连接到规模较大的连通分量的根结点上就可以了，唯一不同的是，不论如何连接，最后都要更新新树的根结点的值，因为每一次归并后，整棵树的结点数一定增加了，所以把根结点的值加上连接的树的根结点的值就可以了。

      完成按秩归并后，网络中的连通分量无论规模还是树高，都会尽可能的小，所以理论上说，查找起来速度会更快了。按秩归并是对归并操作（也就是连接两个连通分量的操作）的优化，那么对于查找操作，查找两个网络是否连接的Search操作，能不能也做些优化，让它变得更快呢？答案是有的，路径压缩，具体做法，一边看代码一边解释：

//路径压缩查找网络n所在的连通分量标识符(用其根结点标识这个网络)
	public int PathCompressionSearch(int networkAddress) {
		if(networkID[networkAddress] < 0) {
			return networkAddress;
		} else {
			networkID[networkAddress] = PathCompressionSearch(networkID[networkAddress]);
			return networkID[networkAddress];
		}
	}

先解释代码，再用图片来表达它的过程。当我们查找一个连通分量的根结点时，先判断它是不是一个负数，如果是，证明它是根结点，就直接返回，如果不是，我们就用递归的方式继续往下查找，假设下一个结点，即寻找networkAddress的父结点的根结点，找到后，就把这个根结点一层一层返回，并沿路这个根结点设置成路径上结点的父结点。讲的不清楚- -、直接来看图：

假设我们要寻找途中最底下的红色的结点的根结点，首先找到它的父结点，即红色箭头所指的结点，它的值肯定不是负数，即它不是根结点，所以递归继续寻找：

往上寻找，还不是根结点，继续递归：

我们就找到了根结点，找到后就把它返回，返回到了上一层，并把这个根结点设置成这一层结点的父结点，当然倒数第二层的父结点本来就是这个根结点，于是继续，把倒数第二层的父结点返回到倒数第三层，即把这个父结点设置成倒数第三层结点的父结点：

然后倒数第三层结点的父结点继续返回给最后这个红色结点，也就是把它的父结点（变成了根结点）赋值给红色结点的父结点，最后让这个红色结点也指向了根结点：

最后最外层的查找返回出去的是这个红色结点的父结点的下标，也就是找到了根结点的下标，就完成了查找这个连通分量根结点的操作。可以看到，路径压缩是从要查找的结点开始，一路往下寻找它所在连通分量（也就是树）的根结点，找到根结点后，原路返回，并在每一层返回后都把上一层的父结点赋值给当前层的结点的父结点。

      可能你会觉得，路径压缩使用了递归，如果一个连通分量很大很大时，使用递归的话，可能会使系统栈爆掉。没错，虽让路径压缩能让下一次查找操作变得更快，但是如果递归方法带来了潜在的危险。但是我们还可以改进这个递归，不过这个改进不是所有语言都可以的（例如Java就不支持），那就是把递归改成尾递归（尾递归即深度为1的递归调用）：

//C实现路径压缩查找网络n所在的连通分量标识符
int PathCompressionSearch(networkList network, int networkAddress) 
{
	if(network->networkID[networkAddress] < 0) {
		return networkAddress;
	} else {
		return network->networkID[networkAddress] = PathCompressionSearch(network, network->networkID[networkAddress]);
	}
}

为什么尾递归就不会出现栈爆掉的情况呢？因为递归是在函数的最后一部，递归函数返回上一层后，上一层的递归函数调用也是在最后一步，继续向上返回即可，不需要保存任何信息变量，直接一路返回，所以其中的函数调用栈是不断同一层覆盖的，这里我表示不清楚- -、，引用一下我看到的一个或许比较易懂的解释：“函数调用时，会开辟一个栈保存局部变量，这些变量在整个函数内随时可能用到，如果函数在代码中间递归调用了自身，那么这个栈里的局部变量是不能破坏的，因为其后还有代码。而尾递归由于发生在函数代码的最后一行，也就意味着后面没有其他代码了，局部变量不可能再被用到哦了，那么就可以被清理掉了，这就是尾递归的优化原理。”

上面实现的所有完整代码已上传GitHub。

https://github.com/justinzengtm/Algorithms/tree/master/Aggregate/RankMerge&PathCompression