Introduction

Fig. Each graph consists of vertices and edges. The root vertices are in blue

• Given the vertices and edges between them, how could we quickly check whether two vertices are connected?
• We can do that by using the disjoint set data structure, also known as the union-find data structure
• The primary use of disjoint sets is to address the connectivity between the components of a network

You Will Know

• topic1
• topic2

Why Should You Learn These

Contents

Click cmd/ctrl + option/alt + T to expand all toggles

1. Basic Idea of a Disjoint Set

2. Implementation of Disjoint Set

3. Quick Find

4. Quick Union

5. Union by Rank

6. Path Compression Optimization

7. Optimized Disjoint Set with Path Compression and Union by Rank

8. General Problems

Conclusions

References

• link1

Further Readings

• a further reading for topic 1

Note