1.12 Disjoint Sets Data Structure - Weighted Union and Collapsing Find

Name: 1.12 Disjoint Sets Data Structure - Weighted Union and Collapsing Find
Uploaded: 2018-04-04T17:51:26.000Z
Duration: 52 min 4 s

Disjoint Sets

In this video, we will learn about disjoint sets and their operations. We will also see how they can be used to detect cycles in non-directed graphs.

What are Disjoint Sets?

A set is said to be disjoint if it has nothing in common with another set.

Disjoint sets are useful for detecting cycles in non-directed graphs.

Operations on Disjoint Sets

The two main operations performed on disjoint sets are Find and Union.

Find operation is used to find out which set an element belongs to.

Union operation is used to connect two sets together.

Detecting Cycles using Disjoint Sets

If an edge connects two vertices that belong to the same set, then there is a cycle in the graph.

Kruskal's algorithm uses disjoint sets to detect cycles in a graph.

Example of Using Disjoint Sets

We can represent each component of a non-connected and non-directed graph as a set.

The purpose of performing Union is to connect two components together when an edge exists between them.

By performing Union, we can detect if there is a cycle in the graph.

Example Graph for Detecting Cycles

We can use disjoint sets to find cycles in a given graph by including edges one by one and forming sets.

Forming Sets

In this section, the speaker explains how to form sets by removing vertices from a universal set and grouping them together.

Removing Vertices and Forming Sets

Remove vertices 5 and 6 from the universal set.

Group vertices 5 and 6 together to form a new set.

Remove vertices 7 and 8 from the universal set.

Group vertices 7 and 8 together to form a new set.

Performing Union on Sets

In this section, the speaker explains how to perform union on sets by combining two sets into one.

Combining Two Sets into One

Combine the set containing vertices 3 and 4 with the set containing vertices 7 and 8 using union.

Combine the resulting set with the set containing vertex 5 using union.

The resulting set contains vertices 1,2,3,4,5,6,7,and 8.

Detecting Cycles in Graphs

In this section, the speaker explains how to detect cycles in graphs using Kruskal's algorithm.

Finding Cycles in Graphs

Remove edges connecting vertices that belong to the same set.

If an edge connects two different sets, perform union on those sets.

If an edge connects two vertices that already belong to the same set, there is a cycle present in the graph.

Representing Sets Graphically

In this section, the speaker explains how to represent sets graphically by assigning parent-child relationships between nodes.

Assigning Parent-Child Relationships Between Nodes

Assign node X1 as parent of set containing vertices 1 and 2.

Assign node X3 as parent of set containing vertices 3 and 4.

Assign node X5 as parent of set containing vertices 5 and 6.

Assign node X7 as parent of set containing vertices 7 and 8.

When an edge connects two different sets, make the parent of one set a child of the other.

Detecting Cycles in Graphs

In this section, the speaker explains how to detect cycles in graphs using disjoint sets. They demonstrate graphically and with an array how to represent sets and perform Union operations.

Representing Sets in an Array

For each vertex, create a single array called "parent" with indices representing the vertices and initialize each value to -1.

To detect a cycle, check if two vertices have the same parent. If they do, it means they belong to the same set and form a cycle.

Demonstration: Edge 1-2 has parents 1 and 2 respectively, so they belong to different sets. Perform Union by selecting one as parent (e.g., 1) and making the other its child (e.g., 2).

Demonstration: Edge 5-6 has parents -1 for both vertices, meaning they are in their own set. Perform Union by selecting one as parent (e.g., 5), making the other its child (e.g., 6), and updating the number of nodes in that set (-2 becomes -6).

Detecting Cycles

Demonstration: Edge 7-8 has parents 7 and 8 respectively. Perform Union by selecting one as parent (e.g., 7), making the other its child (e.g., 8), and updating the number of nodes in that set (-2 becomes -8).

Demonstration: Edge 2-4 has parents 2 and 4 respectively. Find their parents (-1 for both). Perform Union by selecting one as parent (e.g., 1), making the other its child (e.g., 4), and updating the number of nodes in that set (-2 becomes -4).

Demonstration: Edge 2-5 has parents 1 and 1 respectively. Find their parents (-1 for both). Perform Union by selecting one as parent (e.g., 5), making the other its child (e.g., 2), and updating the number of nodes in that set (-2 becomes -6).

Demonstration: Edge 6-8 has parents 6 and 8 respectively. Find their parents (5 and 7 respectively). Perform Union by selecting one as parent (e.g., 7), making the other its child (e.g., 8), and updating the number of nodes in that set (-2 becomes -8).

Demonstration: Edge 1-3 has parents 1 and 3 respectively. Find their parents (-1 for both). Since they have the same parent, they belong to the same set and form a cycle.

Conclusion

Disjoint sets can be used to detect cycles in graphs.

To represent sets, create an array called "parent" with indices representing vertices.

To perform Union operations, select one vertex as parent and make another its child.

To detect a cycle, check if two vertices have the same parent. If they do, it means they belong to the same set and form a cycle.

Weighted Union and Collapsing Find

In this section, the speaker explains the concepts of weighted union and collapsing find in disjoint sets.

Weighted Union

Instead of taking just minus one, ranks or weight are taken into account.

The union is performed based on whoever weight is higher. This is called weighted union.

Collapsing Find

When finding the parent of a set, we may have to take multiple steps along the parent and pair and ampere.

Finally, we will get the root or main parent of a set.

The procedure of directly linking a node to the direct parent of a set is called collapsing find.

We can reduce the time for finding the same value next time by collapsing nodes to their direct parents.

Using Arrays and Linked Lists

Arrays can be used for representing disjoint sets.

For linked lists, nodes are used with index values as node values.