【重拾算法】并查集

一、什么是并查集

并查集是图论中的一种算法

集就是集合,因此可以看出并查集与集合操作有关

并查集内有两个重要的操作:合并(union),查询(find)

合并操作是用来将不同的集合合并为一个集合,查询操作用来查询某个元素所属的集合

二、举个栗子

1. 栗子

假设现在有六个元素,代号分别为1、2、3、4、5、6

他们的集合关系如下,{1, 2}, {1, 5}, {3, 4}, {6, 2},在同一花括号内表示处在同一集合中

问元素[1, 3],元素[2, 5]是否在同一集合内

思路:根据提供的集合关系,将同一集合内的元素连在一起,每个集合选取一个根节点作为集合的代表,若两个元素所处集合的根节点相同,则表示这两个元素在同一集合内

逐步建立他们的集合关系如下

初始时,每个元素都是一个集合,他们的根节点都是自己,例如:parent[1] = 1

【重拾算法】并查集

合并元素1和元素2,此时根节点分别为1,2,任意选取元素1作为合并后集合的根节点

【重拾算法】并查集

将元素5与元素1合并到一个集合中,根节点分别为1,5,任意选取元素5作为合并后集合的根节点

【重拾算法】并查集

 合并元素3和元素4,根节点分别为3,4,任意选取元素3作为合并后集合的根节点

【重拾算法】并查集

合并元素2和元素6,根节点分别为5,6,任意选取元素6作为合并后集合的根节点

【重拾算法】并查集

集合关系就建立完毕啦!

这时候开始判断元素所属集合是否相同

[1, 3]

元素1所处集合的根节点是6,元素3所处集合的根节点是3,因此他们属于不同的集合

[2, 5]

元素5所处集合的根节点是6,元素2所处集合的根节点也是6,因此他们在同一集合内

2. 检测环的存在

并查集还可以用来判断是否有环的存在

例如,我们在原有集合的基础上,再添加一条关联关系{1, 6}

元素1所在集合的根节点是6,元素6所在集合的根节点也是6,他们在同一集合中,因此若继续添加关联关系则会导致的产生

【重拾算法】并查集

3. 代码实现

直接用golang实现

// 初始化
func initArray(parent []int) {
	for i := 0; i < len(parent); i++ {
		parent[i] = -1
	}
}

// 查找根节点
func find(node int, parent []int) int {
	if parent[node] == -1 {
		return node
	}

	return find(parent[node], parent)
}

// 合并集合
func union(x, y int, parent) bool {
	xRoot := find(x, parent)
	yRoot := find(y, parent)

	if xRoot == yRoot {    // 根节点相同表示存在环
		return false
	}

	parent[xRoot] = yRoot
	return true
}

func TestDisjointSet(t *testing.T) {
	elementCount, relationCount, questionCount := 6, 4, 2
	var relations = [][]int{
		{1, 2}, {1, 5}, {3, 4}, {6, 2},
	}
	var P = [][]int{
		{1, 3}, {2, 5},
	}

	// 1. 初始化
	parent := make([]int, elementCount+1)
	initArray(parent)

	// 2. 合并集合
	for i := 0; i < relationCount; i++ {
		union(relations[i][0], relations[i][1], parent)
	}

	// 3. 判断是否为同一集合
	for i := 0; i < questionCount; i++ {
		aRoot := find(P[i][0], parent)
		bRoot := find(P[i][1], parent)
		if aRoot == bRoot {
			t.Log(true)
			continue
		}
		t.Log(false)
	}
}

执行结果

【重拾算法】并查集

三、路径压缩

1. 路径优化

上述的步骤中,左侧的集合极端情况下需要遍历全链表,因此需要考虑用路径压缩做优化

还以上面的元素举例,初始状态仍是六个集合,要建立的关联关系如下:{1, 2}, {1, 5}, {3, 4}, {6, 2}

最初为每个集合赋予基础深度rank为0(这里初始赋值为几并不重要,它只用来做大小比较,只要每个元素的初始值相同即可)

【重拾算法】并查集 

整合元素1和元素2,根节点分别为1,2,此时他们的集合内元素的数量相等,因此可以随意指定一个根节点,这里最终选定的根节点的rank要加一,表示树深度的增加

【重拾算法】并查集 

整合元素1和元素5,根节点分别为1,5,而rank[1] > rank[5],因此选择元素1作为最终的根节点,保证树的深度尽可能的小,这也是路径压缩的目的,这里树的深度没有增加,因此rank[1]不用自增

【重拾算法】并查集

整合元素3和元素4,根节点分别为3,4,rank[3] == rank[4],因此可以任意选择一个根节点,且rank[root]++

【重拾算法】并查集

整合元素6和元素2,根节点分别为1,6,rank[1] > rank[6],选择让元素1作为最终的根节点

【重拾算法】并查集

这里最终生成树的层级比上面的层级更小,遍历起来也更快,这就是路径压缩,让生成树的深度尽可能的小,减少需要遍历的节点

路径压缩的基本思想就是将深度更小的树挂载到深度更大的树上,保证最终的树深度尽可能小

2. 代码实现

// 初始化
func initArray(parent, rank []int) {
	for i := 0; i < len(parent); i++ {
		parent[i] = -1
		rank[i] = 0
	}
}

// 查找根节点
func find(node int, parent []int) int {
	if parent[node] == -1 {
		return node
	}

	return find(parent[node], parent)
}

// 合并集合
func union(x, y int, parent, rank []int) bool {
	xRoot := find(x, parent)
	yRoot := find(y, parent)

	if xRoot == yRoot {
		return false
	}

	if rank[xRoot] > rank[yRoot] {
		parent[yRoot] = xRoot
	} else if rank[xRoot] < rank[yRoot] {
		parent[xRoot] = yRoot
	} else {
		parent[xRoot] = yRoot // 这里随便选哪个节点都可以
		rank[yRoot]++
	}

	return true
}

func TestDisjointSet(t *testing.T) {
	elementCount, relationCount, questionCount := 6, 4, 2
	var relations = [][]int{
		{1, 2}, {1, 5}, {3, 4}, {6, 2},
	}
	var P = [][]int{
		{1, 3}, {2, 5},
	}

	// 1. 初始化
	parent := make([]int, elementCount+1)
	rank := make([]int, elementCount+1)
	initArray(parent, rank)

	// 2. 合并集合
	for i := 0; i < relationCount; i++ {
		union(relations[i][0], relations[i][1], parent, rank)
	}

	// 3. 判断是否为同一集合
	for i := 0; i < questionCount; i++ {
		aRoot := find(P[i][0], parent)
		bRoot := find(P[i][1], parent)
		if aRoot == bRoot {
			t.Log(true)
			continue
		}
		t.Log(false)
	}
}

执行结果

【重拾算法】并查集

 

上一篇:经典TOPN问题


下一篇:寻找一串字符中,最长不重复的子串的长度