filmov
tv
Disjoint-Set Data Structure (Union-Find) | Fast Subset Checking
Показать описание
Problem Statement:
### Terms/Facts
- The disjoint-set structure is a series of directed trees (with all nodes pointing towards the root).
- Each directed tree represents a subset.
- Each node represents an item in a subset.
- The root node of any given subset tree is called the **representative** node and is symbolized by `repr(x)` (”the representative node of the subset `x` is contained in).
- If `repr(x) == repr(y)` then `x` & `y` are in the same subset (the same tree).
- The root node loops back to point to itself as its parent (forming a closed loop).
The disjoint-set structure primes us for fast computation over 2 key operations: `FindRepr(x)` & `Union(x, y)`. Though the structure has 3 operations as follows:
- `MakeSet(x)`: Create a new subset with a single item with value `x`
- `FindRepr(x)`: Find the representative node for the subset containing `x`
- (this primes us for quickly seeing if `x` & `y` are in the same subset)
- `Union(x, y)`: Merge the subset containing `x` with the subset containing `y`
- (if `x` & `y` are in the same subset then no action is necessary)
**Applications**
- We aim to avoid connecting 2 nodes already in the same connected component.
- We only want to expand the Minimum Spanning Tree by connecting 2 disjoint components with the next cheapest edge (the algorithm’s goal).
**References**
Table of Contents:
0:00 - Introduction
1:18 - Trees Review
2:47 - Forests
4:08 - The Core Problem
06:18 - Kruskal’s Algorithm Review
08:01 - Disjoint-Set Operations
08:53 - Subset Representation
10:47 - Operations: MakeSet
11:56 - The Representative Node
12:59 - What Are Subsets in Trees?
13:30 - Operations: FindRepr (unoptimized)
14:55 - FindRepr Worst Case
15:24 - Operations: Union (unoptimized)
17:32 - Optimizing Operations
19:22 - Path Compression
21:49 - Weighted Union
25:01 - Complexities
28:00 - Closing
Socials:
0:05:46
Union Find in 5 minutes — Data Structures & Algorithms
0:26:04
1.12 Disjoint Sets Data Structure - Weighted Union and Collapsing Find
0:05:53
Disjoint Set Data Structure - Union Find Tutorial
0:05:46
Union Find Introduction
0:00:48
Union Find (Disjoint Set Union)
0:08:11
An Animated Introduction to the Union Find (Disjoint Set)
0:10:53
Union Find - Union and Find Operations
0:18:43
Disjoint-Set Data Structure (Union-Find) | Fast Subset Checking
0:08:33
Kruskal's Algorithm | Disjoint Sets | Union By Rank | Path Compression
0:23:46
Grouping elements in no time with the disjoint-set data structure (Union-Find) - Inside code
0:23:33
What is Union-Find Algorithm, Disjoint Set Data Structure?
0:13:33
Disjoint Sets: the Union-Find Data Structure
0:42:15
G-46. Disjoint Set | Union by Rank | Union by Size | Path Compression
0:26:43
Disjoint Set | UNION and FIND
0:05:21
Introduction to Union-find
0:00:49
How much Data Structures Algorithms
0:17:49
Disjoint Sets using union by rank and path compression Graph Algorithm
0:12:38
Disjoint Sets & Union Find Algorithm Simply Explained
0:00:06
Day 24 || Disjoint–Set Data Structure (Union–Find Algorithm)
0:10:58
Union find data structure disjoint sets
0:06:28
Disjoint Set Part 2 - Union Find : Array based implementation
0:34:03
Union Find Disjoint Set - From Scratch
0:10:15
Disjoint Set Operations - Simple Union & Find Algorithms |L-10||DAA|
0:00:39
How I mastered Data Structures and Algorithms #dsa #codinginterview #leetcode
Комментарии