学习打卡 JavaScript并查集

前些日子写课设的时候发现要用到并查集这个算法，之前是生搬硬套，也不懂其原理，今天研究了下一位大佬的博文——，自己写了个案例，顺便试着整理一下其具体的运作过程；

1. 基本思路

我们在开始算法前进行这样的规定： （1）所有的节点作为单个元素形成的树，进行数组存储，值统一为-1；

（2）当某个节点连接到另外一个节点上时（例如，此处要把 1 连接到 2 上边），则 该节点（此处为 1 ） 的值 改为被连接节点的索引（此处为 2 ），而被连接节点的值则为现存的值加上另外一个节点的值 （此处 2 节点 的值则为 -1 + -1 = -2）

（3）以此类推… 为防止断层，需要确保连接的两个节点值为负数，即 两个节点均为根节点，若相连的两个节点不全为根节点，则找到它们各自的根节点再进行相连；（【注】此时每个根节点值的绝对值即为其所在树的节点数）

（4）当把根节点进行相连时，遵循：谁的节点个数多，就做连接以后的根节点（本例中，4 节点值为 -3, 6 节点值为 -2，所以把6节点连接到4节点上）； 用这样的步骤推演下去，所有节点都能连接到一棵树上。

2. JavaScript代码具体实现：

（1）初始化： 每个节点值设定为 -1 ；

//图方便，就对6个节点进行操作了
var N = 7;
var tree = new Array();

for(var i=1;i<N;i++){
          
   
	tree[i] = -1;
}

（2）传入一个节点，通过该节点找到所在树的根节点：

//搜索元素的根节点
function search(a){
          
   
	//如果不是根节点,进行递归
	if(tree[a]>0){
          
   
		return search(tree[a]);
	}
	else{
          
   
		return a;
	}
}

（3）将两个节点进行合并（连接）：

//合并根节点
function union(a,b){
          
   
	//先去找到两个节点各自的根节点
	var ar = search(a);
	var br = search(b);
	
	//如果根节点相同，则a,b已经在一棵树上了，此时相连将形成一个封闭的环
	if(ar == br){
          
   
		console.log("这两个元素已经在一棵树上了，一个环成功形成");
	}
	
	//当ar为根的树 节点更多时:
	else if(-tree[ar]>-tree[br]){
          
   
		tree[ar] += tree[br];
		tree[br] = ar;
	}
	//当br为根的树 节点更多时:
	else{
          
   
		tree[br] += tree[ar];
		tree[ar] = br;
	}
}

（4）获得节点所在树的节点个数：

//获得某棵树的节点个数
function getTreeValue(a){
          
   
	if(tree[a]>0){
          
   
		return getTreeValue(tree[a]);
	}
	else{
          
   
		return -tree[a];
	}
}

（5）按照图示进行代码测试 先将 1,2 3,4 5,6相连，再将 2,4 6,4相连，形成如下一棵树： 代码实现：

union(1,2);
union(3,4);
union(5,6);
union(2,4);
union(6,4);

console.log(tree);            //(6)[2, 4, 4, -6, 6, 4]
console.log(search(2));       //4
console.log(getTreeValue(4)); //6
console.log(union(1,6));      //这两个元素已经在一棵树上了，一个环成功形成

测试结果没啥问题就~确实如大佬所说，并查集算法的具体代码实现还是比较方便的。

并查集算法用途还是比较广泛的，最经典的莫过于生成随机迷宫问题了 —— 一想到用这种算法生成迷宫的本质是一次又一次把原来挡路的墙给撞破…突然觉得优雅如Disjoint Sets也不是那么美好了~ ————————————————————————————————— END ————————————————————