ThinkerQAQ

NOTE

2.14 UnionFind

Union-Find, Quick Find, Quick Union, and optimizations.

Data Structures & AlgorithmsCreated Updated 1 min readhistorical

This is a historical learning note and may contain outdated or incomplete understanding.

1. What It Is

  • A tree structure. The difference is that children point to parents

2. What It Is Used For

  • Solving connectivity problems (simpler than path problems)

3. Implementation

3.1. API

type IUnionFind interface {
	// Get the number of elements in the union-find
	GetSize() int
	// Whether the elements with ids p and q belong to the same set
	IsConnected(p int, q int) (bool,error)
	// Merge the elements with ids p and q into the same set
	UnionElements(p int, q int) error
}

3.2. Quick Find


import "fmt"

type QuickFind struct {
	// index is the id; value is the set that the id belongs to
	id []int
}

func NewQuickFind(size int) *QuickFind {
	quickFind := &QuickFind{id: make([]int, size)}

	for i := 0; i < len(quickFind.id); i++ {
		quickFind.id[i] = i
	}

	return quickFind
}

func (qf *QuickFind) GetSize() int {
	return len(qf.id)
}

// O（1）
// Check whether the elements with ids p and q belong to the same set
func (qf *QuickFind) IsConnected(p int, q int) (bool, error) {
	setP, err := qf.find(p)
	if err != nil {
		return false, err
	}
	setQ, err := qf.find(q)
	if err != nil {
		return false, err
	}

	return setQ == setP, nil

}

// Find the set corresponding to the element with id p
func (qf *QuickFind) find(p int) (int, error) {
	if p < 0 || p >= len(qf.id) {
		return 0, fmt.Errorf("out of bound")
	}
	return qf.id[p], nil
}

// O（N）
// Merge the elements with ids p and q into the same set
func (qf *QuickFind) UnionElements(p int, q int) error {
	setP, err := qf.find(p)
	if err != nil {
		return err
	}
	setQ, err := qf.find(q)
	if err != nil {
		return err
	}

	if setQ == setP {
		return nil
	}

	for i := 0; i < len(qf.id); i++ {
		if qf.id[i] == setP {
			qf.id[i] = setQ
		}
	}

	return nil
}

3.2.1. Test

func TestQuickFind(t *testing.T) {
	quickFind := NewQuickFind(10)
	fmt.Println(quickFind.GetSize())

	fmt.Println(quickFind.IsConnected(1,2))
	quickFind.UnionElements(1,2)
	fmt.Println(quickFind.IsConnected(1,2))
}

3.3. Quick Union

package unionfind

import "fmt"

type QuickUnion struct {
	parent []int
}

func NewQuickUnion(size int) *QuickUnion {
	quickUnion := &QuickUnion{parent: make([]int, size)}
	for i := 0; i < size; i++ {
		quickUnion.parent[i] = i
	}
	return quickUnion
}

func (qu *QuickUnion) GetSize() int {
	return len(qu.parent)
}

// O(h), where h is the height of the tree
// Find the set corresponding to the element with id p
func (qu *QuickUnion) find(p int) (int, error) {
	if p < 0 || p >= len(qu.parent) {
		return 0, fmt.Errorf("out of bound")
	}

	for p != qu.parent[p] {
		p = qu.parent[p]
	}

	return p, nil
}

// O(h), where h is the height of the tree
// Check whether the elements with ids p and q belong to the same set
func (qu *QuickUnion) IsConnected(p int, q int) (bool, error) {
	setP, err := qu.find(p)
	if err != nil {
		return false, err
	}
	setQ, err := qu.find(q)
	if err != nil {
		return false, err
	}

	return setQ == setP, nil
}
// O(h), where h is the height of the tree
// Merge the elements with ids p and q into the same set
func (qu *QuickUnion) UnionElements(p int, q int) error {
	setP, err := qu.find(p)
	if err != nil {
		return err
	}
	setQ, err := qu.find(q)
	if err != nil {
		return err
	}

	if setQ == setP {
		return nil
	}

	qu.parent[setP] = setQ
	return nil
}

3.3.1. Test

func TestQuickUnion(t *testing.T) {
	quickUnion := NewQuickUnion(10)
	fmt.Println(quickUnion.GetSize())

	fmt.Println(quickUnion.IsConnected(1,2))
	quickUnion.UnionElements(1,2)
	fmt.Println(quickUnion.IsConnected(1,2))
}

3.4. Size-Based Optimization

package unionfind

import "fmt"

type QuickUnion2 struct {
	parent []int
	sz     []int
}

func NewQuickUnion2(size int) *QuickUnion2 {
	quickUnion2 := &QuickUnion2{
		parent: make([]int, size),
		sz:     make([]int, size)}
	for i := 0; i < size; i++ {
		quickUnion2.parent[i] = i
		quickUnion2.sz[i] = 1
	}
	return quickUnion2
}

func (qu *QuickUnion2) GetSize() int {
	return len(qu.parent)
}

// O(h), where h is the height of the tree
// Find the set corresponding to the element with id p
func (qu *QuickUnion2) find(p int) (int, error) {
	if p < 0 || p >= len(qu.parent) {
		return 0, fmt.Errorf("out of bound")
	}

	for p != qu.parent[p] {
		p = qu.parent[p]
	}

	return p, nil
}

// O(h), where h is the height of the tree
// Check whether the elements with ids p and q belong to the same set
func (qu *QuickUnion2) IsConnected(p int, q int) (bool, error) {
	setP, err := qu.find(p)
	if err != nil {
		return false, err
	}
	setQ, err := qu.find(q)
	if err != nil {
		return false, err
	}

	return setQ == setP, nil
}

// O(h), where h is the height of the tree
// Merge the elements with ids p and q into the same set
func (qu *QuickUnion2) UnionElements(p int, q int) error {
	setP, err := qu.find(p)
	if err != nil {
		return err
	}
	setQ, err := qu.find(q)
	if err != nil {
		return err
	}

	if setQ == setP {
		return nil
	}

	// Merge the smaller set into the larger set
	if qu.sz[setP] < qu.sz[setQ] {
		qu.parent[setP] = setQ
		qu.sz[setQ] += qu.sz[setP]
	} else {
		qu.parent[setQ] = setP
		qu.sz[setP] += qu.sz[setQ]
	}

	return nil
}

3.4.1. Test

func TestQuickUnion2(t *testing.T) {
	quickUnion := NewQuickUnion2(10)
	fmt.Println(quickUnion.GetSize())

	fmt.Println(quickUnion.IsConnected(1,2))
	quickUnion.UnionElements(1,2)
	fmt.Println(quickUnion.IsConnected(1,2))
}

3.5. Rank-Based Optimization

package unionfind

import "fmt"

type QuickUnion3 struct {
	parent []int
	rank   []int
}

func NewQuickUnion3(size int) *QuickUnion3 {
	quickUnion := &QuickUnion3{
		parent: make([]int, size),
		rank:   make([]int, size)}
	for i := 0; i < size; i++ {
		quickUnion.parent[i] = i
		quickUnion.rank[i] = 1
	}
	return quickUnion
}

func (qu *QuickUnion3) GetSize() int {
	return len(qu.parent)
}

// O(h), where h is the height of the tree
// Find the set corresponding to the element with id p
func (qu *QuickUnion3) find(p int) (int, error) {
	if p < 0 || p >= len(qu.parent) {
		return 0, fmt.Errorf("out of bound")
	}

	for p != qu.parent[p] {
		p = qu.parent[p]
	}

	return p, nil
}

// O(h), where h is the height of the tree
// Check whether the elements with ids p and q belong to the same set
func (qu *QuickUnion3) IsConnected(p int, q int) (bool, error) {
	setP, err := qu.find(p)
	if err != nil {
		return false, err
	}
	setQ, err := qu.find(q)
	if err != nil {
		return false, err
	}

	return setQ == setP, nil
}

// O(h), where h is the height of the tree
// Merge the elements with ids p and q into the same set
func (qu *QuickUnion3) UnionElements(p int, q int) error {
	setP, err := qu.find(p)
	if err != nil {
		return err
	}
	setQ, err := qu.find(q)
	if err != nil {
		return err
	}

	if setQ == setP {
		return nil
	}

	// Merge the smaller set into the larger set
	if qu.rank[setP] < qu.rank[setQ] {
		qu.parent[setP] = setQ
	} else if qu.rank[setP] > qu.rank[setQ] {
		qu.parent[setQ] = setP
	} else {
		qu.parent[setQ] = setP
		qu.rank[setP] += 1
	}

	return nil
}

3.5.1. Test

func TestQuickUnion3(t *testing.T) {
	quickUnion := NewQuickUnion3(10)
	fmt.Println(quickUnion.GetSize())

	fmt.Println(quickUnion.IsConnected(1,2))
	quickUnion.UnionElements(1,2)
	fmt.Println(quickUnion.IsConnected(1,2))
}

3.6. Path Compression

package unionfind

import "fmt"

type QuickUnion4 struct {
	parent []int
	rank   []int
}

func NewQuickUnion4(size int) *QuickUnion4 {
	quickUnion := &QuickUnion4{
		parent: make([]int, size),
		rank:   make([]int, size)}
	for i := 0; i < size; i++ {
		quickUnion.parent[i] = i
		quickUnion.rank[i] = 1
	}
	return quickUnion
}

func (qu *QuickUnion4) GetSize() int {
	return len(qu.parent)
}

// O(h), where h is the height of the tree
// Find the set corresponding to the element with id p
func (qu *QuickUnion4) find(p int) (int, error) {
	if p < 0 || p >= len(qu.parent) {
		return 0, fmt.Errorf("out of bound")
	}

	for p != qu.parent[p] {
		qu.parent[p] = qu.parent[qu.parent[p]]
		p = qu.parent[p]
	}

	return p, nil
}

// O(h), where h is the height of the tree
// Check whether the elements with ids p and q belong to the same set
func (qu *QuickUnion4) IsConnected(p int, q int) (bool, error) {
	setP, err := qu.find(p)
	if err != nil {
		return false, err
	}
	setQ, err := qu.find(q)
	if err != nil {
		return false, err
	}

	return setQ == setP, nil
}

// O(h), where h is the height of the tree
// Merge the elements with ids p and q into the same set
func (qu *QuickUnion4) UnionElements(p int, q int) error {
	setP, err := qu.find(p)
	if err != nil {
		return err
	}
	setQ, err := qu.find(q)
	if err != nil {
		return err
	}

	if setQ == setP {
		return nil
	}

	// Merge the smaller set into the larger set
	if qu.rank[setP] < qu.rank[setQ] {
		qu.parent[setP] = setQ
	} else if qu.rank[setP] > qu.rank[setQ] {
		qu.parent[setQ] = setP
	} else {
		qu.parent[setQ] = setP
		qu.rank[setP] += 1
	}

	return nil
}

3.6.1. Test

func TestQuickUnion4(t *testing.T) {
	quickUnion := NewQuickUnion4(10)
	fmt.Println(quickUnion.GetSize())

	fmt.Println(quickUnion.IsConnected(1,2))
	quickUnion.UnionElements(1,2)
	fmt.Println(quickUnion.IsConnected(1,2))
}

Discussion

Sign in with GitHub to comment. Discussions are stored as GitHub Issues.View on GitHub