Disjoint Set | Union Find | Cycle Detection| Union By Rank | Path Compression | Graphs
In this video, I have explained Disjoint Set Data Structure. A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
A union-find algorithm is an algorithm that performs two useful operations on such a data structure - Find and Union.
I have explained the naïve implementation as well as the optimized implementation using 2 techniques:
1. Path Compression
2. Union By Rank
Then I discussed how we can detect cycle in a graph using Union-Find.
I have explained using an example and have implemented in C++ as well.
00:00 Introduction
00:09 Topics
00:48 Disjoint Set
01:22 Union Find interface
02:20 Union Find Implementation (Inefficient)
07:50 Union Find optimization
08:41 Path compression
10:43 Union By Rank
14:22 Detect cycle in a graph
16:55 C++ Implementation
19:10 Applications
Source Code: https://github.com/fit-coder/fitcoderyoutube/tree/master/graph
-------------------------------------------------------------
I live in New Delhi and love explaining programming concepts. I have done M.Tech(BITS Pilani) + B.Tech(PEC, Chandigarh) in Computer Science and am currently working as a software engineer in a MNC.
If you like my content, please like, share my videos and subscribe to the channel.
-------------------------------------------------------------
For in-depth Graph theory and implementation details, please refer to the below videos:
Graphs Introduction: https://www.youtube.com/watch?v=4xMsNIPEkwA
Graph representation:
Adjacency Matrix: https://www.youtube.com/watch?v=x6N5FK6ArRk
Adjacency List: https://www.youtube.com/watch?v=3AtEzK4sowk
Incidence Matrix: https://www.youtube.com/watch?v=bP-8P8f8mAY
Traversal techniques:
BFS, Breadth First Search: https://www.youtube.com/watch?v=iYz-pG1CPIM
DFS, Depth First Search: https://www.youtube.com/watch?v=oO1857MQlcs
Shortest Path algorithms:
Dijkstra algorithm: https://www.youtube.com/watch?v=J12sfRYpW-M
Bellman Ford algorithm: https://www.youtube.com/watch?v=iGzZEJc_w3I
Floyd Warshall algorithm: https://www.youtube.com/watch?v=R0Srbd5ALN8
Minimum Spanning Tree:
Kruskal algorithm: https://www.youtube.com/watch?v=dYIWheKq5Xc
Prim algorithm: https://www.youtube.com/watch?v=NCpUwOqt41k
Topological sort (Kahn algorithm): https://www.youtube.com/watch?v=gDNm1m3G4wo
Articulation points / Cut vertices:
Tarjan algorithm: https://www.youtube.com/watch?v=qNVNoZJFp_g
Disjoint Set / Union Find: https://www.youtube.com/watch?v=0JE7hxr8c5c
Maximum Flow Problem:
Ford Fulkerson algorithm: https://www.youtube.com/watch?v=_UcOALraATY
Graph coloring / Chromatic number: https://www.youtube.com/watch?v=oikZlz1GNbo
Hamiltonian cycle: https://www.youtube.com/watch?v=jGRRBJlNtwI
Euler cycle (Fleury algorithm): https://www.youtube.com/watch?v=c0e50JIAMuM
#DataStructure,#Graphs,#FitCoder,#Algorithm,#competitiveprogramming
Видео Disjoint Set | Union Find | Cycle Detection| Union By Rank | Path Compression | Graphs канала Fit Coder
A union-find algorithm is an algorithm that performs two useful operations on such a data structure - Find and Union.
I have explained the naïve implementation as well as the optimized implementation using 2 techniques:
1. Path Compression
2. Union By Rank
Then I discussed how we can detect cycle in a graph using Union-Find.
I have explained using an example and have implemented in C++ as well.
00:00 Introduction
00:09 Topics
00:48 Disjoint Set
01:22 Union Find interface
02:20 Union Find Implementation (Inefficient)
07:50 Union Find optimization
08:41 Path compression
10:43 Union By Rank
14:22 Detect cycle in a graph
16:55 C++ Implementation
19:10 Applications
Source Code: https://github.com/fit-coder/fitcoderyoutube/tree/master/graph
-------------------------------------------------------------
I live in New Delhi and love explaining programming concepts. I have done M.Tech(BITS Pilani) + B.Tech(PEC, Chandigarh) in Computer Science and am currently working as a software engineer in a MNC.
If you like my content, please like, share my videos and subscribe to the channel.
-------------------------------------------------------------
For in-depth Graph theory and implementation details, please refer to the below videos:
Graphs Introduction: https://www.youtube.com/watch?v=4xMsNIPEkwA
Graph representation:
Adjacency Matrix: https://www.youtube.com/watch?v=x6N5FK6ArRk
Adjacency List: https://www.youtube.com/watch?v=3AtEzK4sowk
Incidence Matrix: https://www.youtube.com/watch?v=bP-8P8f8mAY
Traversal techniques:
BFS, Breadth First Search: https://www.youtube.com/watch?v=iYz-pG1CPIM
DFS, Depth First Search: https://www.youtube.com/watch?v=oO1857MQlcs
Shortest Path algorithms:
Dijkstra algorithm: https://www.youtube.com/watch?v=J12sfRYpW-M
Bellman Ford algorithm: https://www.youtube.com/watch?v=iGzZEJc_w3I
Floyd Warshall algorithm: https://www.youtube.com/watch?v=R0Srbd5ALN8
Minimum Spanning Tree:
Kruskal algorithm: https://www.youtube.com/watch?v=dYIWheKq5Xc
Prim algorithm: https://www.youtube.com/watch?v=NCpUwOqt41k
Topological sort (Kahn algorithm): https://www.youtube.com/watch?v=gDNm1m3G4wo
Articulation points / Cut vertices:
Tarjan algorithm: https://www.youtube.com/watch?v=qNVNoZJFp_g
Disjoint Set / Union Find: https://www.youtube.com/watch?v=0JE7hxr8c5c
Maximum Flow Problem:
Ford Fulkerson algorithm: https://www.youtube.com/watch?v=_UcOALraATY
Graph coloring / Chromatic number: https://www.youtube.com/watch?v=oikZlz1GNbo
Hamiltonian cycle: https://www.youtube.com/watch?v=jGRRBJlNtwI
Euler cycle (Fleury algorithm): https://www.youtube.com/watch?v=c0e50JIAMuM
#DataStructure,#Graphs,#FitCoder,#Algorithm,#competitiveprogramming
Видео Disjoint Set | Union Find | Cycle Detection| Union By Rank | Path Compression | Graphs канала Fit Coder
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Prim Algorithm | Minimum Spanning Tree | Greedy Algorithm | GraphsDisjoint Sets using union by rank and path compression Graph AlgorithmKruskal Algorithm | Minimum Spanning Tree | Greedy Algorithm | GraphsUnion-Find Algorithm | Set 1 (Detect Cycle in an Undirected Graph) | GeeksforGeeksTop 5 Most Common Graph Algorithms for Coding InterviewsDisjoint Set Union (DSU) Tutorial with Code | CP Course | EP 85Prim's algorithm in 2 minutes — Review and exampleUnion Find in 5 minutes — Data Structures & AlgorithmsDFS Depth First Search | Graph Traversal | Data StructureSubset sum problem using backtrackingBellman Ford Algorithm | Single Source Shortest Path | Dynamic Programming | Graphs23- Disjoint Set | Graph Theory | PythonC++ Programming Tutorial 75 - Creating a Simple MakefileC++ code for Non-recursive preorder traversalThe Most Difficult Program to Compute? - ComputerphileUnion Find - Union and Find OperationsGraph Coloring Algorithm || Using Adjacency Matrix || Program in C1.12 Disjoint Sets Data Structure - Weighted Union and Collapsing FindDijkstra Algorithm | Single Source Shortest Path | Greedy Algorithm | Graphs